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)
	{
		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.

  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.

New Comment





Categories
Relative Post