Bit exchange O (logN)?

Question

I was told that the reverse bits of an integer are divided and controlled (i.e., first replacing every two consecutive bits, then changing 2-bit pairs, etc. until I get the result) there is O (logN), but I do not see how it is O (logN) ..

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

Am I right or am I missing something?

Answer 1

You just count something else. If you add up all the “individual swaps,” then there are many swaps. But the whole point of the technique (and many similar methods) is that for the “phase” all swaps in this phase occur with a constant number of steps. For example, the step "swap adjacent bits":

x = ((x & 0x55) << 1) | ((x & 0xAA) >> 1); 

.. or its equivalent delta swap formula, looks like this, regardless of how many swaps there are (the constants change, of course). So this is a constant number of steps right there. (cue complaining that operations on N-bit integers are not single steps, here they are, it's just another way of counting)

To change the byte, 3 delta swaps (or simple swaps as described above) are required.

Answer 2

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

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

Total: 7 swaps, log (N) - 3.

That's right, it has 7 swaps, but in 3 steps described above.

For example, replacing 4 pairs looks like x = ((x & 01010101b) << 1) | ((x >> 1) & 01010101b) x = ((x & 01010101b) << 1) | ((x >> 1) & 01010101b) . Thus, we take bits 0, 2, 4 and 6 and advance them at positions 1, 3, 5 and 7 (the left half) and at the same time take bits 1, 3, 5 and 7 and lower them to positions 0, 2, 4 and 6, respectively (right half).