4.30.4 — Reverse Bits

LeetCode 190 · Easy · ★ Blind 75

The problem

Reverse the bits of a 32-bit unsigned integer.

n = 00000010100101000001111010011100
  → 00111001011110000010100101000000

The pattern

Do it exactly 32 times, regardless of the value:

• Take the lowest bit of n with n & 1.
• Push it onto the result by shifting the result left and adding that bit.
• Shift n right to expose the next bit.

The first bit taken ends up shifted left 31 times, so it lands at the top. The last bit taken stays at the bottom. That is the reversal.

The loop must run exactly 32 times, not until n becomes 0. Leading zeros in the input become trailing zeros in the output, and stopping early loses them. For n = 1 the answer is 2^{31}, not 1 — and a while n: loop would return 1.

That is the trap in this problem, and it is easy to miss because the small test cases still pass.

The solution

Python

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0

        for _ in range(32):                 # exactly 32, not "while n"
            result = (result << 1) | (n & 1)
            n >>= 1

        return result

TypeScript

function reverseBits(n: number): number {
  let result = 0;

  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>>= 1;                               // UNSIGNED shift
  }

  return result >>> 0;                      // reinterpret as unsigned
}

(result << 1) | (n & 1) in one expression. Shift the accumulated answer up to make room, then place the new bit at the bottom.

In TypeScript, >>> not >>. Bitwise operators coerce to 32-bit signed integers, so >> on a value with the top bit set drags 1s down from the left and the loop never terminates correctly. >>> shifts in zeros.

The final >>> 0 reinterprets the result as unsigned, because << may have produced a negative number. Without it, an answer above 2^{31} prints as negative.

Python has no such issue with >> on a non-negative value, but note that result will simply be a large positive integer rather than a fixed-width one.

Trace

Reversing the 4-bit value 1011 (illustrative — the real problem uses 32):

step	n & 1	result before	result after	n after
1	1	0	1	101
2	1	1	11	10
3	0	11	110	1
4	1	110	1101	0

1011 reversed is 1101 ✓.

Complexity

O(1) — always 32 iterations. O(1) space.

The follow-up: many calls

The problem asks what you would do if the function were called millions of times.

Cache the reversal of each byte. Reverse each of the four bytes with a 256-entry lookup table, then reassemble them in the opposite order:

cache = {}
def reverseByte(b):
    if b not in cache:
        r = 0
        for _ in range(8):
            r = (r << 1) | (b & 1)
            b >>= 1
        cache[b] = r
    return cache[b]

Four lookups instead of 32 iterations, with 256 entries of memory. This is memoisation applied to a bit operation, and it is the same trade as any cache: space for time, worth it only when the function is hot.

There is also a divide-and-conquer version that swaps adjacent bits, then pairs, then nibbles, then bytes — five masked shift-and-or steps with no loop at all:

n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)   # swap adjacent bits
n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)   # swap pairs
n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4)   # swap nibbles
n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8)   # swap bytes
n = (n >> 16) | (n << 16)                               # swap halves

Each mask selects alternating groups of a given size. Beautiful, and impossible to reconstruct from memory — name it, do not write it unless asked specifically.

Where this goes next

• Number of 1 Bits — the same bit-by-bit walk, counting instead of reversing. 4.30.2.
• Reverse Integer — the decimal version, with an overflow check. 4.30.7.
• Byte-order swapping — htonl and friends swap byte order for network transmission, using the same masked shifts. Chapter 5.9 covers why network byte order exists.
• Bit-reversal permutation — the FFT reorders its input by reversing the bit pattern of each index, which is this operation used in earnest.

What the interviewer will push on

"Why exactly 32 iterations?" Leading zeros must become trailing zeros. Give n = 1 → 2^{31}.

"Why >>> in JavaScript?" >> is a signed shift and drags 1s in from the left.

"What if it is called millions of times?" A byte lookup table — four lookups instead of 32 steps.

"Can you do it without a loop?" The five-step masked swap. Say it exists.

"Where does this appear in real code?" Network byte order, and the FFT's bit-reversal permutation.

One thing to volunteer: name the 32-iteration trap before writing the loop. It is the only thing this problem is testing, and stating it first is worth more than the code.

Next: 4.30.5 Missing Number — XOR again, this time cancelling indices against values.