Swap every two bits in bytes
The given problem revolves around the concept of swapping adjacent pairs of bits within bytes of an integer. The goal is to exchange every two adjacent bits in the binary representation of a number. This process essentially involves reversing the positions of bits located at even and odd indices. In this article, we will thoroughly explain the problem statement, provide examples, present a solution approach, discuss the algorithm, and finally analyze the time complexity of the code.
Problem Statement
Given an integer 'num', the task is to swap every two adjacent bits in its binary representation.
Example
Let's consider the following examples to understand the problem better:
# Example 1
(22) 00010110
00 01 01 10
00 10 10 01
Result (00101001) (41)
# Example 2
(53) 00110101
00 11 01 01
Swap 00 11 10 10
Result (00111010) (58)
Idea to Solve
The idea to solve this problem involves manipulating the individual bits of the given number. We need to perform the following steps:
- Identify the bits at even and odd positions.
- Swap the adjacent bits at even and odd positions.
- Construct the new number using the swapped bits.
Pseudocode
function swapBits(num):
even_bits = num AND 0xAA // Get even-positioned bits
odd_bits = num AND 0x55 // Get odd-positioned bits
swapped_bits = (even_bits >> 1) OR (odd_bits << 1) // Swap and combine bits
return swapped_bits
Algorithm Explanation
- Start by defining a function
swapBits
that takes an integernum
as its argument. - Use bitwise AND operation to extract the even-positioned bits of
num
using the bitmask 0xAA (10101010 in binary). - Use bitwise AND operation to extract the odd-positioned bits of
num
using the bitmask 0x55 (01010101 in binary). - Right-shift the even bits by 1 position to move them to odd positions.
- Left-shift the odd bits by 1 position to move them to even positions.
- Use bitwise OR operation to combine the shifted even and odd bits, creating the swapped result.
- Return the swapped result.
Code Solution
// C program
// Swap every two bits in bytes
#include <stdio.h>
// Swap the pair of adjacent bits in bytes
void swapBits(int num)
{
// 0xAA (10101010) (170)
// 0x55 (01010101) (85)
// (num & 0xAA) Get the set bits in Even position of num
// (num & 0x55) Get the set bits in Odd position of num
// ((Even active bits) >> 1) shift 1 bits right side
// ((Odd active bits) << 1) shift 1 bits left side
int result = (((num & 0xAA) >> 1) | ((num & 0x55) << 1));
// Display given number
printf("\n Number : %d", num);
// Display calculated result
printf("\n Result : %d", result);
}
int main(int argc, char
const *argv[])
{
// (22) 00010110
// 00 01 01 10
// 00 10 10 01
// Result (00101001) (41)
swapBits(22);
// (53) 00110101
// 00 11 01 01
// Swap 00 11 10 10
// Result (00111010) (58)
swapBits(53);
return 0;
}
Output
Number : 22
Result : 41
Number : 53
Result : 58
/*
Java program
Swap every two bits in bytes
*/
public class BitSwap
{
// Swap the pair of adjacent bits in bytes
public void swapBits(int num)
{
// 0xAA (10101010) (170)
// 0x55 (01010101) (85)
// (num & 0xAA) Get the set bits in Even position of num
// (num & 0x55) Get the set bits in Odd position of num
// ((Even active bits) >> 1) shift 1 bits right side
// ((Odd active bits) << 1) shift 1 bits left side
int result = (((num & 0xAA) >> 1) | ((num & 0x55) << 1));
// Display given number
System.out.print("\n Number : " + num);
// Display calculated result
System.out.print("\n Result : " + result);
}
public static void main(String[] args)
{
BitSwap task = new BitSwap();
// (22) 00010110
// 00 01 01 10
// 00 10 10 01
// Result (00101001) (41)
task.swapBits(22);
// (53) 00110101
// 00 11 01 01
// Swap 00 11 10 10
// Result (00111010) (58)
task.swapBits(53);
}
}
Output
Number : 22
Result : 41
Number : 53
Result : 58
// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Swap every two bits in bytes
*/
class BitSwap
{
public:
// Swap the pair of adjacent bits in bytes
void swapBits(int num)
{
// 0xAA (10101010) (170)
// 0x55 (01010101) (85)
// (num &0xAA) Get the set bits in Even position of num
// (num &0x55) Get the set bits in Odd position of num
// ((Even active bits) >> 1) shift 1 bits right side
// ((Odd active bits) << 1) shift 1 bits left side
int result = (((num & 0xAA) >> 1) | ((num & 0x55) << 1));
// Display given number
cout << "\n Number : " << num;
// Display calculated result
cout << "\n Result : " << result;
}
};
int main()
{
BitSwap task = BitSwap();
// (22) 00010110
// 00 01 01 10
// 00 10 10 01
// Result (00101001) (41)
task.swapBits(22);
// (53) 00110101
// 00 11 01 01
// Swap 00 11 10 10
// Result (00111010) (58)
task.swapBits(53);
return 0;
}
Output
Number : 22
Result : 41
Number : 53
Result : 58
// Include namespace system
using System;
/*
C# program
Swap every two bits in bytes
*/
public class BitSwap
{
// Swap the pair of adjacent bits in bytes
public void swapBits(int num)
{
// 0xAA (10101010) (170)
// 0x55 (01010101) (85)
// (num & 0xAA) Get the set bits in Even position of num
// (num & 0x55) Get the set bits in Odd position of num
// ((Even active bits) >> 1) shift 1 bits right side
// ((Odd active bits) << 1) shift 1 bits left side
int result = (((num & 0xAA) >> 1) | ((num & 0x55) << 1));
// Display given number
Console.Write("\n Number : " + num);
// Display calculated result
Console.Write("\n Result : " + result);
}
public static void Main(String[] args)
{
BitSwap task = new BitSwap();
// (22) 00010110
// 00 01 01 10
// 00 10 10 01
// Result (00101001) (41)
task.swapBits(22);
// (53) 00110101
// 00 11 01 01
// Swap 00 11 10 10
// Result (00111010) (58)
task.swapBits(53);
}
}
Output
Number : 22
Result : 41
Number : 53
Result : 58
<?php
/*
Php program
Swap every two bits in bytes
*/
class BitSwap
{
// Swap the pair of adjacent bits in bytes
public function swapBits($num)
{
// 0xAA (10101010) (170)
// 0x55 (01010101) (85)
// (num & 0xAA) Get the set bits in Even position of num
// (num & 0x55) Get the set bits in Odd position of num
// ((Even active bits) >> 1) shift 1 bits right side
// ((Odd active bits) << 1) shift 1 bits left side
$result = ((($num & 0xAA) >> 1) | (($num & 0x55) << 1));
// Display given number
echo "\n Number : ". $num;
// Display calculated result
echo "\n Result : ". $result;
}
}
function main()
{
$task = new BitSwap();
// (22) 00010110
// 00 01 01 10
// 00 10 10 01
// Result (00101001) (41)
$task->swapBits(22);
// (53) 00110101
// 00 11 01 01
// Swap 00 11 10 10
// Result (00111010) (58)
$task->swapBits(53);
}
main();
Output
Number : 22
Result : 41
Number : 53
Result : 58
/*
Node Js program
Swap every two bits in bytes
*/
class BitSwap
{
// Swap the pair of adjacent bits in bytes
swapBits(num)
{
// 0xAA (10101010) (170)
// 0x55 (01010101) (85)
// (num & 0xAA) Get the set bits in Even position of num
// (num & 0x55) Get the set bits in Odd position of num
// ((Even active bits) >> 1) shift 1 bits right side
// ((Odd active bits) << 1) shift 1 bits left side
var result = (((num & 0xAA) >> 1) | ((num & 0x55) << 1));
// Display given number
process.stdout.write("\n Number : " + num);
// Display calculated result
process.stdout.write("\n Result : " + result);
}
}
function main()
{
var task = new BitSwap();
// (22) 00010110
// 00 01 01 10
// 00 10 10 01
// Result (00101001) (41)
task.swapBits(22);
// (53) 00110101
// 00 11 01 01
// Swap 00 11 10 10
// Result (00111010) (58)
task.swapBits(53);
}
main();
Output
Number : 22
Result : 41
Number : 53
Result : 58
# Python 3 program
# Swap every two bits in bytes
class BitSwap :
# Swap the pair of adjacent bits in bytes
def swapBits(self, num) :
# 0xAA (10101010) (170)
# 0x55 (01010101) (85)
# (num & 0xAA) Get the set bits in Even position of num
# (num & 0x55) Get the set bits in Odd position of num
# ((Even active bits) >> 1) shift 1 bits right side
# ((Odd active bits) << 1) shift 1 bits left side
result = (((num & 0xAA) >> 1) | ((num & 0x55) << 1))
# Display given number
print("\n Number : ", num, end = "")
# Display calculated result
print("\n Result : ", result, end = "")
def main() :
task = BitSwap()
# (22) 00010110
# 00 01 01 10
# 00 10 10 01
# Result (00101001) (41)
task.swapBits(22)
# (53) 00110101
# 00 11 01 01
# Swap 00 11 10 10
# Result (00111010) (58)
task.swapBits(53)
if __name__ == "__main__": main()
Output
Number : 22
Result : 41
Number : 53
Result : 58
# Ruby program
# Swap every two bits in bytes
class BitSwap
# Swap the pair of adjacent bits in bytes
def swapBits(num)
# 0xAA (10101010) (170)
# 0x55 (01010101) (85)
# (num & 0xAA) Get the set bits in Even position of num
# (num & 0x55) Get the set bits in Odd position of num
# ((Even active bits) >> 1) shift 1 bits right side
# ((Odd active bits) << 1) shift 1 bits left side
result = (((num & 0xAA) >> 1) | ((num & 0x55) << 1))
# Display given number
print("\n Number : ", num)
# Display calculated result
print("\n Result : ", result)
end
end
def main()
task = BitSwap.new()
# (22) 00010110
# 00 01 01 10
# 00 10 10 01
# Result (00101001) (41)
task.swapBits(22)
# (53) 00110101
# 00 11 01 01
# Swap 00 11 10 10
# Result (00111010) (58)
task.swapBits(53)
end
main()
Output
Number : 22
Result : 41
Number : 53
Result : 58
/*
Scala program
Swap every two bits in bytes
*/
class BitSwap
{
// Swap the pair of adjacent bits in bytes
def swapBits(num: Int): Unit = {
// 0xAA (10101010) (170)
// 0x55 (01010101) (85)
// (num & 0xAA) Get the set bits in Even position of num
// (num & 0x55) Get the set bits in Odd position of num
// ((Even active bits) >> 1) shift 1 bits right side
// ((Odd active bits) << 1) shift 1 bits left side
var result: Int = (((num & 0xAA) >> 1) | ((num & 0x55) << 1));
// Display given number
print("\n Number : " + num);
// Display calculated result
print("\n Result : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BitSwap = new BitSwap();
// (22) 00010110
// 00 01 01 10
// 00 10 10 01
// Result (00101001) (41)
task.swapBits(22);
// (53) 00110101
// 00 11 01 01
// Swap 00 11 10 10
// Result (00111010) (58)
task.swapBits(53);
}
}
Output
Number : 22
Result : 41
Number : 53
Result : 58
/*
Swift 4 program
Swap every two bits in bytes
*/
class BitSwap
{
// Swap the pair of adjacent bits in bytes
func swapBits(_ num: Int)
{
// 0xAA (10101010) (170)
// 0x55 (01010101) (85)
// (num & 0xAA) Get the set bits in Even position of num
// (num & 0x55) Get the set bits in Odd position of num
// ((Even active bits) >> 1) shift 1 bits right side
// ((Odd active bits) << 1) shift 1 bits left side
let result: Int = (((num & 0xAA) >> 1) | ((num & 0x55) << 1));
// Display given number
print("\n Number : ", num, terminator: "");
// Display calculated result
print("\n Result : ", result, terminator: "");
}
}
func main()
{
let task: BitSwap = BitSwap();
// (22) 00010110
// 00 01 01 10
// 00 10 10 01
// Result (00101001) (41)
task.swapBits(22);
// (53) 00110101
// 00 11 01 01
// Swap 00 11 10 10
// Result (00111010) (58)
task.swapBits(53);
}
main();
Output
Number : 22
Result : 41
Number : 53
Result : 58
/*
Kotlin program
Swap every two bits in bytes
*/
class BitSwap
{
// Swap the pair of adjacent bits in bytes
fun swapBits(num: Int): Unit
{
// 0xAA (10101010) (170)
// 0x55 (01010101) (85)
// (num & 0xAA) Get the set bits in Even position of num
// (num & 0x55) Get the set bits in Odd position of num
// ((Even active bits) >> 1) shift 1 bits right side
// ((Odd active bits) << 1) shift 1 bits left side
var result: Int = (((num and 0xAA) shr 1) or((num and 0x55) shl 1));
// Display given number
print("\n Number : " + num);
// Display calculated result
print("\n Result : " + result);
}
}
fun main(args: Array < String > ): Unit
{
var task: BitSwap = BitSwap();
// (22) 00010110
// 00 01 01 10
// 00 10 10 01
// Result (00101001) (41)
task.swapBits(22);
// (53) 00110101
// 00 11 01 01
// Swap 00 11 10 10
// Result (00111010) (58)
task.swapBits(53);
}
Output
Number : 22
Result : 41
Number : 53
Result : 58
Time Complexity
The time complexity of the provided code is constant or O(1), as the operations performed on the bits are fixed regardless of the size of the input. The bitwise operations take a constant amount of time irrespective of the magnitude of the input number.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment