The problem is, Given a number of n bits, reverse the bits. Normally, I would have used 2n bitwise operations to do this.
In CSE548, for a problem we reversed a string recursively, by reversing the two halves of the string, and then exchanging the positions of the two reversed halves. A string of bits, is a string after all.
So, we start with reversing the odd-even bits, then reversing pairs of bits, then reversing sets of 4 bits, and so on. So, this requires 3*log(n) bitwise operations, which is better. Here is an efficient implementation for reversing a 32-bit unsigned int.
1 2 3 4 5 6 7 8 9 10 11 12 13 14