Bit swapping O(logN)?

Question

I've been told that reversing bits of an integer in a divide-and-conquer fashion (i.e. by first swapping every two consecutive bits, then swapping 2-bit pairs, and so on until I get the result) is O(logN), but I fail to see how this is O(logN)..

Consider the case when swapping a byte (8 bit): we first swap every two bits together and perform 4 swaps, then we swap 2-bit pairs so we have 2 swaps and then we join everything together in the last swap. Total: 7 swaps, log(N) would have been 3.

Am I right or am I missing something?

Answer 1

The key observation is that some swaps can be done in parallel. To quote your post:

• we first swap every two bits together and perform 4 swaps,
• then we swap 2-bit pairs so we have 2 swaps
• and then we join everything together in the last swap.

Total: 7 swaps, log(N) would have been 3.

Right, it's 7 swaps, but in 3 steps outlined above.

For example, swapping 4 pairs is like x = ((x & 01010101b) << 1) | ((x >> 1) & 01010101b). This way, we take bits 0, 2, 4 and 6 and promote them to positions 1, 3, 5 and 7 (the left half), and simultaneously take bits 1, 3, 5 and 7 and demote them to positions 0, 2, 4 and 6 respectively (the right half).