Swap all adjacent bits in given number
The given problem aims to swap all adjacent bits in a given number. In other words, we need to swap the bits at even positions with the bits at odd positions. This can be achieved using bitwise operations in C programming.
Explanation with an Example
Let's consider the number 37 (binary representation: 100101) as an example.
The binary representation of 37 can be broken down into pairs of adjacent bits as follows:
- 10 01 01
Now, we need to swap the bits at even positions with the bits at odd positions:
- 01 10 10
The resulting binary representation is 011010, which is equivalent to the decimal number 26. Therefore, when we apply
the swapBits
function to 37, it correctly swaps the adjacent bits and gives us the result 26.
Pseudocode
Before delving into the algorithm, let's write a pseudocode to better understand the steps involved in swapping adjacent bits.
FUNCTION swapBits(num):
SET evenBitsMask = 0xAAAAAAAA (binary: 10101010101010101010101010101010)
SET oddBitsMask = 0x55555555 (binary: 01010101010101010101010101010101)
SET evenBits = num AND evenBitsMask
SET oddBits = num AND oddBitsMask
SET shiftedEvenBits = evenBits RIGHT SHIFT 1
SET shiftedOddBits = oddBits LEFT SHIFT 1
SET result = shiftedEvenBits OR shiftedOddBits
RETURN result
END FUNCTION
Algorithm Explanation
- Define two masks
evenBitsMask
andoddBitsMask
. These masks will be used to isolate even and odd bits, respectively, in the input numbernum
. TheevenBitsMask
has 1s in all even positions, and theoddBitsMask
has 1s in all odd positions. - Use bitwise AND to extract the even bits from the input number
num
and store the result in a variableevenBits
. - Use bitwise AND to extract the odd bits from the input number
num
and store the result in a variableoddBits
. - Right shift the
evenBits
by 1 position and store the result in a variableshiftedEvenBits
. This will effectively move the even bits to odd positions. - Left shift the
oddBits
by 1 position and store the result in a variableshiftedOddBits
. This will effectively move the odd bits to even positions. - Use bitwise OR to combine
shiftedEvenBits
andshiftedOddBits
, resulting in a new number with adjacent bits swapped. Store this result in a variableresult
. - Return the
result
.
Code Solution
Here given code implementation process.
// C program
// Swap all adjacent bits in given number
#include <stdio.h>
// Swap the pair of adjacent bits
void swapBits(int num)
{
// 0xAAAAAAAA (10101010101010101010101010101010) (2863311530)
// 0x55555555 (01010101010101010101010101010101) (1431655765)
// (num & 0xAAAAAAAA) Get the set bits in Even position of num
// (num & 0x55555555) 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 & 0xAAAAAAAA) >> 1) | ((num & 0x55555555) << 1));
// Display given number
printf("\n Number : %d",num);
// Display calculated result
printf("\n Result : %d",result);
}
int main(int argc, char const *argv[])
{
// (37) 100101
// 10 01 01
// 01 10 10
// Result (011010) (26)
swapBits(37);
// (216) 11011000
// 11 01 10 00
// Swap 11 10 01 00
// Result (11100100) (228)
swapBits(216);
// (42) 101010
// 10 10 10
// Swap 01 01 01
// Result (010101) (21)
swapBits(42);
return 0;
}
Output
Number : 37
Result : 26
Number : 216
Result : 228
Number : 42
Result : 21
/*
Java program
Swap all adjacent bits in given number
*/
public class BitSwap
{
// Swap the pair of adjacent bits
public void swapBits(int num)
{
// 0xAAAAAAAA (10101010101010101010101010101010) (2863311530)
// 0x55555555 (01010101010101010101010101010101) (1431655765)
// (num & 0xAAAAAAAA) Get the set bits in Even position of num
// (num & 0x55555555) 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 & 0xAAAAAAAA) >> 1) | ((num & 0x55555555) << 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();
// (37) 100101
// 10 01 01
// 01 10 10
// Result (011010) (26)
task.swapBits(37);
// (216) 11011000
// 11 01 10 00
// Swap 11 10 01 00
// Result (11100100) (228)
task.swapBits(216);
// (42) 101010
// 10 10 10
// Swap 01 01 01
// Result (010101) (21)
task.swapBits(42);
}
}
Output
Number : 37
Result : 26
Number : 216
Result : 228
Number : 42
Result : 21
// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Swap all adjacent bits in given number
*/
class BitSwap
{
public:
// Swap the pair of adjacent bits
void swapBits(int num)
{
// 0xAAAAAAAA (10101010101010101010101010101010) (2863311530)
// 0x55555555 (01010101010101010101010101010101) (1431655765)
// (num &0xAAAAAAAA) Get the set bits in Even position of num
// (num &0x55555555) 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 &0xAAAAAAAA) >> 1) | ((num &0x55555555) << 1));
// Display given number
cout << "\n Number : " << num;
// Display calculated result
cout << "\n Result : " << result;
}
};
int main()
{
BitSwap task = BitSwap();
// (37) 100101
// 10 01 01
// 01 10 10
// Result (011010) (26)
task.swapBits(37);
// (216) 11011000
// 11 01 10 00
// Swap 11 10 01 00
// Result (11100100) (228)
task.swapBits(216);
// (42) 101010
// 10 10 10
// Swap 01 01 01
// Result (010101) (21)
task.swapBits(42);
return 0;
}
Output
Number : 37
Result : 26
Number : 216
Result : 228
Number : 42
Result : 21
// Include namespace system
using System;
/*
C# program
Swap all adjacent bits in given number
*/
public class BitSwap
{
// Swap the pair of adjacent bits
public void swapBits(int num)
{
// 0xAAAAAAAA (10101010101010101010101010101010) (2863311530)
// 0x55555555 (01010101010101010101010101010101) (1431655765)
// (num & 0xAAAAAAAA) Get the set bits in Even position of num
// (num & 0x55555555) 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
long result = (((num & 0xAAAAAAAAL) >> 1) | ((num & 0x55555555L) << 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();
// (37) 100101
// 10 01 01
// 01 10 10
// Result (011010) (26)
task.swapBits(37);
// (216) 11011000
// 11 01 10 00
// Swap 11 10 01 00
// Result (11100100) (228)
task.swapBits(216);
// (42) 101010
// 10 10 10
// Swap 01 01 01
// Result (010101) (21)
task.swapBits(42);
}
}
Output
Number : 37
Result : 26
Number : 216
Result : 228
Number : 42
Result : 21
<?php
/*
Php program
Swap all adjacent bits in given number
*/
class BitSwap
{
// Swap the pair of adjacent bits
public function swapBits($num)
{
// 0xAAAAAAAA (10101010101010101010101010101010) (2863311530)
// 0x55555555 (01010101010101010101010101010101) (1431655765)
// (num & 0xAAAAAAAA) Get the set bits in Even position of num
// (num & 0x55555555) 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 & 0xAAAAAAAA) >> 1) | (($num & 0x55555555) << 1));
// Display given number
echo "\n Number : ". $num;
// Display calculated result
echo "\n Result : ". $result;
}
}
function main()
{
$task = new BitSwap();
// (37) 100101
// 10 01 01
// 01 10 10
// Result (011010) (26)
$task->swapBits(37);
// (216) 11011000
// 11 01 10 00
// Swap 11 10 01 00
// Result (11100100) (228)
$task->swapBits(216);
// (42) 101010
// 10 10 10
// Swap 01 01 01
// Result (010101) (21)
$task->swapBits(42);
}
main();
Output
Number : 37
Result : 26
Number : 216
Result : 228
Number : 42
Result : 21
/*
Node Js program
Swap all adjacent bits in given number
*/
class BitSwap
{
// Swap the pair of adjacent bits
swapBits(num)
{
// 0xAAAAAAAA (10101010101010101010101010101010) (2863311530)
// 0x55555555 (01010101010101010101010101010101) (1431655765)
// (num & 0xAAAAAAAA) Get the set bits in Even position of num
// (num & 0x55555555) 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 & 0xAAAAAAAA) >> 1) | ((num & 0x55555555) << 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();
// (37) 100101
// 10 01 01
// 01 10 10
// Result (011010) (26)
task.swapBits(37);
// (216) 11011000
// 11 01 10 00
// Swap 11 10 01 00
// Result (11100100) (228)
task.swapBits(216);
// (42) 101010
// 10 10 10
// Swap 01 01 01
// Result (010101) (21)
task.swapBits(42);
}
main();
Output
Number : 37
Result : 26
Number : 216
Result : 228
Number : 42
Result : 21
# Python 3 program
# Swap all adjacent bits in given number
class BitSwap :
# Swap the pair of adjacent bits
def swapBits(self, num) :
# 0xAAAAAAAA (10101010101010101010101010101010) (2863311530)
# 0x55555555 (01010101010101010101010101010101) (1431655765)
# (num & 0xAAAAAAAA) Get the set bits in Even position of num
# (num & 0x55555555) 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 & 0xAAAAAAAA) >> 1) | ((num & 0x55555555) << 1))
# Display given number
print("\n Number : ", num, end = "")
# Display calculated result
print("\n Result : ", result, end = "")
def main() :
task = BitSwap()
# (37) 100101
# 10 01 01
# 01 10 10
# Result (011010) (26)
task.swapBits(37)
# (216) 11011000
# 11 01 10 00
# Swap 11 10 01 00
# Result (11100100) (228)
task.swapBits(216)
# (42) 101010
# 10 10 10
# Swap 01 01 01
# Result (010101) (21)
task.swapBits(42)
if __name__ == "__main__": main()
Output
Number : 37
Result : 26
Number : 216
Result : 228
Number : 42
Result : 21
# Ruby program
# Swap all adjacent bits in given number
class BitSwap
# Swap the pair of adjacent bits
def swapBits(num)
# 0xAAAAAAAA (10101010101010101010101010101010) (2863311530)
# 0x55555555 (01010101010101010101010101010101) (1431655765)
# (num & 0xAAAAAAAA) Get the set bits in Even position of num
# (num & 0x55555555) 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 & 0xAAAAAAAA) >> 1) | ((num & 0x55555555) << 1))
# Display given number
print("\n Number : ", num)
# Display calculated result
print("\n Result : ", result)
end
end
def main()
task = BitSwap.new()
# (37) 100101
# 10 01 01
# 01 10 10
# Result (011010) (26)
task.swapBits(37)
# (216) 11011000
# 11 01 10 00
# Swap 11 10 01 00
# Result (11100100) (228)
task.swapBits(216)
# (42) 101010
# 10 10 10
# Swap 01 01 01
# Result (010101) (21)
task.swapBits(42)
end
main()
Output
Number : 37
Result : 26
Number : 216
Result : 228
Number : 42
Result : 21
/*
Scala program
Swap all adjacent bits in given number
*/
class BitSwap
{
// Swap the pair of adjacent bits
def swapBits(num: Int): Unit = {
// 0xAAAAAAAA (10101010101010101010101010101010) (2863311530)
// 0x55555555 (01010101010101010101010101010101) (1431655765)
// (num & 0xAAAAAAAA) Get the set bits in Even position of num
// (num & 0x55555555) 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 & 0xAAAAAAAA) >> 1) | ((num & 0x55555555) << 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();
// (37) 100101
// 10 01 01
// 01 10 10
// Result (011010) (26)
task.swapBits(37);
// (216) 11011000
// 11 01 10 00
// Swap 11 10 01 00
// Result (11100100) (228)
task.swapBits(216);
// (42) 101010
// 10 10 10
// Swap 01 01 01
// Result (010101) (21)
task.swapBits(42);
}
}
Output
Number : 37
Result : 26
Number : 216
Result : 228
Number : 42
Result : 21
/*
Swift 4 program
Swap all adjacent bits in given number
*/
class BitSwap
{
// Swap the pair of adjacent bits
func swapBits(_ num: Int)
{
// 0xAAAAAAAA (10101010101010101010101010101010) (2863311530)
// 0x55555555 (01010101010101010101010101010101) (1431655765)
// (num & 0xAAAAAAAA) Get the set bits in Even position of num
// (num & 0x55555555) 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 & 0xAAAAAAAA) >> 1) | ((num & 0x55555555) << 1));
// Display given number
print("\n Number : ", num, terminator: "");
// Display calculated result
print("\n Result : ", result, terminator: "");
}
}
func main()
{
let task: BitSwap = BitSwap();
// (37) 100101
// 10 01 01
// 01 10 10
// Result (011010) (26)
task.swapBits(37);
// (216) 11011000
// 11 01 10 00
// Swap 11 10 01 00
// Result (11100100) (228)
task.swapBits(216);
// (42) 101010
// 10 10 10
// Swap 01 01 01
// Result (010101) (21)
task.swapBits(42);
}
main();
Output
Number : 37
Result : 26
Number : 216
Result : 228
Number : 42
Result : 21
Time Complexity
The time complexity of this algorithm is O(1) because the number of operations is constant and independent of the size of the input number.
Output Explanation:
Let's now go through the output of the provided code for the given example numbers.
- For the input number 37, the result is 26. As explained earlier, the adjacent bits have been swapped.
- For the input number 216, the result is 228. The adjacent bits have been swapped, and the new number is 11100100 in binary (228 in decimal).
- For the input number 42, the result is 21. The adjacent bits have been swapped, and the new number is 010101 in binary (21 in decimal).
In conclusion, the provided codes which successfully swaps all adjacent bits in the given numbers, and the output confirms that the adjacent bits have been correctly swapped as expected. The algorithm is efficient with a constant time complexity, making it suitable for practical use.
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