Swap bits in a given number

Given a number x and two positions (from right side) in binary representation of x, write a function that swaps n bits at given two positions and returns the result. It is also given that the two sets of bits do not overlap.

We strongly recommend that you click here and practice it, before moving on to the solution.

Examples:

Let p1 and p2 be the two given positions.

Example 1
Input:
x = 47 (00101111)
p1 = 1 (Start from second bit from right side)
p2 = 5 (Start from 6th bit from right side)
n = 3 (No of bits to be swapped)
Output:
227 (11100011)
The 3 bits starting from the second bit (from right side) are 
swapped with 3 bits starting from 6th position (from right side) 


Example 2
Input:
x = 28 (11100)
p1 = 0 (Start from first bit from right side)
p2 = 3 (Start from 4th bit from right side)
n = 2 (No of bits to be swapped)
Output:
7 (00111)
The 2 bits starting from 0th postion (from right side) are
swapped with 2 bits starting from 4th position (from right side) 

Solution
We need to swap two sets of bits. XOR can be used in a similar way as it is used to swap 2 numbers. Following is the algorithm.

1) Move all bits of first set to rightmost side
   set1 =  (x >> p1) & ((1U << n) - 1)
Here the expression (1U << n) - 1 gives a number that 
contains last n bits set and other bits as 0. We do & 
with this expression so that bits other than the last 
n bits become 0.
2) Move all bits of second set to rightmost side
   set2 =  (x >> p2) & ((1U << n) - 1)
3) XOR the two sets of bits
   xor = (set1 ^ set2) 
4) Put the xor bits back to their original positions. 
   xor = (xor << p1) | (xor << p2)
5) Finally, XOR the xor with original number so 
   that the two sets are swapped.
   result = x ^ xor

[ad type=”banner”]

Implementation:

[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%20%0Aint%20swapBits(unsigned%20int%20x%2C%20unsigned%20int%20p1%2C%20unsigned%20int%20p2%2C%20unsigned%20int%20n)%0A%7B%0A%20%20%20%20%2F*%20Move%20all%20bits%20of%20first%20set%20to%20rightmost%20side%20*%2F%0A%20%20%20%20unsigned%20int%20set1%20%3D%20%20(x%20%3E%3E%20p1)%20%26%20((1U%20%3C%3C%20n)%20-%201)%3B%0A%20%0A%20%20%20%20%2F*%20Moce%20all%20bits%20of%20second%20set%20to%20rightmost%20side%20*%2F%0A%20%20%20%20unsigned%20int%20set2%20%3D%20%20(x%20%3E%3E%20p2)%20%26%20((1U%20%3C%3C%20n)%20-%201)%3B%0A%20%0A%20%20%20%20%2F*%20XOR%20the%20two%20sets%20*%2F%0A%20%20%20%20unsigned%20int%20xor%20%3D%20(set1%20%5E%20set2)%3B%0A%20%0A%20%20%20%20%2F*%20Put%20the%20xor%20bits%20back%20to%20their%20original%20positions%20*%2F%0A%20%20%20%20xor%20%3D%20(xor%20%3C%3C%20p1)%20%7C%20(xor%20%3C%3C%20p2)%3B%0A%20%0A%20%20%20%20%2F*%20XOR%20the%20’xor’%20with%20the%20original%20number%20so%20that%20the%20%0A%20%20%20%20%20%20%20two%20sets%20are%20swapped%20*%2F%0A%20%20%20%20unsigned%20int%20result%20%3D%20x%20%5E%20xor%3B%0A%20%0A%20%20%20%20return%20result%3B%0A%7D%0A%20%0A%2F*%20Drier%20program%20to%20test%20above%20function*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20int%20res%20%3D%20%20swapBits(28%2C%200%2C%203%2C%202)%3B%0A%20%20%20%20printf(%22%5CnResult%20%3D%20%25d%20%22%2C%20res)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”c” highlight=”” provider=”manual”/]

Output:

Result = 7

Following is a shorter implementation of the same logic