Posted on by Kalkicode
Code Bit Logic

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

1. Define two masks `evenBitsMask` and `oddBitsMask`. These masks will be used to isolate even and odd bits, respectively, in the input number `num`. The `evenBitsMask` has 1s in all even positions, and the `oddBitsMask` has 1s in all odd positions.
2. Use bitwise AND to extract the even bits from the input number `num` and store the result in a variable `evenBits`.
3. Use bitwise AND to extract the odd bits from the input number `num` and store the result in a variable `oddBits`.
4. Right shift the `evenBits` by 1 position and store the result in a variable `shiftedEvenBits`. This will effectively move the even bits to odd positions.
5. Left shift the `oddBits` by 1 position and store the result in a variable `shiftedOddBits`. This will effectively move the odd bits to even positions.
6. Use bitwise OR to combine `shiftedEvenBits` and `shiftedOddBits`, resulting in a new number with adjacent bits swapped. Store this result in a variable `result`.
7. 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)
{
// (37)    100101
//         10 01 01
//         01 10 10
// Result  (011010) (26)
// (216)    11011000
//          11 01 10 00
// Swap     11 10 01 00
// Result  (11100100) (228)
// (42)     101010
//          10 10 10
// Swap     01 01 01
// Result  (010101) (21)
}
}``````

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()
{
// (37)    100101
//         10 01 01
//         01 10 10
// Result  (011010) (26)
// (216)    11011000
//          11 01 10 00
// Swap     11 10 01 00
// Result  (11100100) (228)
// (42)     101010
//          10 10 10
// Swap     01 01 01
// Result  (010101) (21)
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)
{
// (37)    100101
//         10 01 01
//         01 10 10
// Result  (011010) (26)
// (216)    11011000
//          11 01 10 00
// Swap     11 10 01 00
// Result  (11100100) (228)
// (42)     101010
//          10 10 10
// Swap     01 01 01
// Result  (010101) (21)
}
}``````

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()
{
// (37)    100101
//         10 01 01
//         01 10 10
// Result  (011010) (26)
// (216)    11011000
//          11 01 10 00
// Swap     11 10 01 00
// Result  (11100100) (228)
// (42)     101010
//          10 10 10
// Swap     01 01 01
// Result  (010101) (21)
}
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()
{
// (37)    100101
//         10 01 01
//         01 10 10
// Result  (011010) (26)
// (216)    11011000
//          11 01 10 00
// Swap     11 10 01 00
// Result  (11100100) (228)
// (42)     101010
//          10 10 10
// Swap     01 01 01
// Result  (010101) (21)
}
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() :
#  (37)    100101
#          10 01 01
#          01 10 10
#  Result  (011010) (26)
#  (216)    11011000
#           11 01 10 00
#  Swap     11 10 01 00
#  Result  (11100100) (228)
#  (42)     101010
#           10 10 10
#  Swap     01 01 01
#  Result  (010101) (21)

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()
#  (37)    100101
#          10 01 01
#          01 10 10
#  Result  (011010) (26)
#  (216)    11011000
#           11 01 10 00
#  Swap     11 10 01 00
#  Result  (11100100) (228)
#  (42)     101010
#           10 10 10
#  Swap     01 01 01
#  Result  (010101) (21)
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)
// (216)    11011000
//          11 01 10 00
// Swap     11 10 01 00
// Result  (11100100) (228)
// (42)     101010
//          10 10 10
// Swap     01 01 01
// Result  (010101) (21)
}
}``````

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()
{
// (37)    100101
//         10 01 01
//         01 10 10
// Result  (011010) (26)
// (216)    11011000
//          11 01 10 00
// Swap     11 10 01 00
// Result  (11100100) (228)
// (42)     101010
//          10 10 10
// Swap     01 01 01
// Result  (010101) (21)
}
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.

1. For the input number 37, the result is 26. As explained earlier, the adjacent bits have been swapped.
2. 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).
3. 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.

Comment

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.

Categories
Relative Post