Question: Given an unsigned Integer, you need to reverse its bits.
There are several methods of reversing the bits of an unsigned integer. Here, we devise an algorithm using the XOR swap trick.
Hint:
How do you swap the ith bit with the jth bit? Try to figure out if you could use the XOR operation to do it.
The XOR swap trick:
Reversing bits could be done by swapping the n/2 least significant bits with its most significant bits. The trick is to implement a function called swapBits(i, j), which swaps the ith bit with the jth bit.
If you still remember how XOR operation works:
0 ^ 0 == 0 1 ^ 1 == 0 0 ^ 1 == 1 1 ^ 0 == 1.
We only need to perform the swap when the ith bit and the jth bit are different. To test if two bits are different, we could use the XOR operation. Then, we need to toggle both ith and jth bits. We could apply the XOR operation again. By XOR-ing the ith and jth bit with 1, both bits are toggled.
typedef unsigned int uint;
uint swapBits(uint x, uint i, uint j)
{
uint lo = ((x >> i) & 1);
uint hi = ((x >> j) & 1);
if (lo ^ hi)
{
x ^= ((1U << i) | (1U << j));
}
return x;
}
uint reverseXor(uint x)
{
uint n = sizeof(x) * 8;
for (uint i = 0; i < n/2; i++)
{
x = swapBits(x, i, n-i-1);
}
return x;
}