Reverse Bits - log (n)

Source

Reverse bits of an unsigned integer.

There are several methods of reversing the bits of an unsigned integer. Here, we devise an algorithm using the XOR swap trick, and then optimize it using a divide and conquer methodology.

Hint:
How do you swap the i^th bit with the j^th 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 i^th bit with the j^th bit. If you still remember how XOR operation works: 0 ^ 0 == 0, 1 ^ 1 == 0, 0 ^ 1 == 1, and 1 ^ 0 == 1.

We only need to perform the swap when the i^th bit and the j^th bit are different. To test if two bits are different, we could use the XOR operation. Then, we need to toggle both i^th and j^th bits. We could apply the XOR operation again. By XOR-ing the i^th and j^th bit with 1, both bits are toggled.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

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; }

The run time complexity using the XOR trick to reverse bits is O(n), where n is the total number of bits in an unsigned integer.

The divide and conquer approach:
Remember how merge sort works? Let us use an example of n == 8 (one byte) to see how this works:

      01101001     /         \    0110      1001   /   \     /   \  01   10   10   01  /\   /\   /\   /\ 0 1  1 0  1 0  0 1

The first step is to swap all odd and even bits. After that swap consecutive pairs of bits, and so on…

Therefore, only a total of log(n) operations are necessary.

The below code shows a specific case where n == 32, but it could be easily adapted to larger n‘s as well.

?

1 2 3 4 5 6 7 8 9

uint reverseMask(uint x) { assert(sizeof(x) == 4); // special case: only works for 4 bytes (32 bits). x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1); x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2); x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4); x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8); x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16); return x; }