Swap Adjacent Bits of a Number

Given an integer, swap adjacent bits of it. In other words, swap bits present at even positions with those present in odd positions.

 


For example,


Input:  00101101011001010111000110001001

Output: 00011110100110101011001001000110

Explanation: (Every pair of adjacent bits swapped)

00 10 11 01 01 10 01 01 01 11 00 01 10 00 10 01
00 01 11 10 10 01 10 10 10 11 00 10 01 00 01 10

 


 

The idea is to separate bits present at even positions with bits present at odd positions using the mask 0xAAAAAAAA and 0x55555555 respectively.

  • Mask 0xAAAAAAAA has all its even bits set and its bitwise-AND with n will separate bits present at even positions in n.
     
  • Similarly, mask 0x55555555 has all its odd bits set and its bitwise-AND with n will separate bits present at odd positions in n.

(0xAAAAAAAA)16 = (1010 1010 1010 1010 1010 1010 1010 1010)2
(0x55555555)16 = (0101 0101 0101 0101 0101 0101 0101 0101)2

After separating even and odd bits, we right shift even bits by 1 position and left shift odd bits by 1 position. Now that all even bits are at odd positions and all odd bits are at even positions, we merge them by taking their OR. For example,
 

1. SEPARATE

00101101011001010111000110001001  &    (n)
10101010101010101010101010101010       (0xAAAAAAAA)
————————————————————————————————
00101000001000000010000010001000       (Contains all even bits)
 

00101101011001010111000110001001  &    (n)
01010101010101010101010101010101       (0x55555555)
————————————————————————————————
00000101010001010101000100000001       (Contains all odd bits)
 

2. SHIFT & MERGE

00010100000100000001000001000100  |    (Right shift even bits by 1)
00001010100010101010001000000010       (Left shift odd bits by 1)
————————————————————————————————
00011110100110101011001001000110       (Adjacent bits swapped)

 

 
C++ implementation –
 

Download   Run Code

Output:

761622921 in binary is 00101101011001010111000110001001

After swapping
513454662 in binary is 00011110100110101011001001000110

 

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz