Can someone explain why this works?

  • 0

  • 1

    It swaps bits pairwise first. Then it swaps neighboring pairs. Then it swaps neighboring “quadruples” (corresponding to hex digits), then it finally reverses bytes.

    The first steps look like this for a single byte:

    1. b7 b6 | b5 b4 | b3 b2 | b1 b0 -> b6 b7 | b4 b5 | b2 b3 | b0 b1
    2. b6 b7 | b4 b5 | b2 b3 | b0 b1 -> b4 b5 b6 b7 | b0 b1 b2 b3
    3. b4 b5 b6 b7 | b0 b1 b2 b3 -> b0 b1 b2 b3 b4 b5 b6 b7

    Since you do it to every byte, reversing bytes in the end gives you the whole reversed integer.

    I recommend Hacker's Delight book on this kind of tricks. It's a whole book of such things, very handy even if you don't manage to actually read it.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.