Math & Bit Manipulation · LC #190
Reverse Bits
Reverse all 32 bits of an unsigned integer by iteratively extracting the LSB from the input and feeding it into the MSB position of the result.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Reverse the bits of a given 32-bit unsigned integer and return the result as an unsigned integer.
Sample I/O
Input: n = 00000010100101000001111010011100 (43261596) Output: 00111001011110000010100101000000 (964176192) Input: n = 11111111111111111111111111111101 (4294967293) Output: 10111111111111111111111111111111 (3221225471)
Intuition
How to Think About It
Intuition
Think of two pointers converging from opposite ends of the 32-bit string. Each iteration we peel the last bit off `n` (via `n & 1`) and append it to the front of `result` (via `result << 1 | bit`), then advance both pointers by shifting.
Core Concept
Loop exactly 32 times: `result = (result << 1) | (n & 1); n >>>= 1`. After 32 iterations, `result` holds all bits in reverse order. In JS/TS, use `>>> 0` after each shift to clamp to unsigned 32-bit; in Java, use `>>>` for unsigned right-shift.
When to use
Bit reversal for hardware register manipulation, CRC computation, FFT butterfly operations, network byte-order conversions.
When NOT to use
When you only need bit reversal of a single byte - a lookup table is O(1). When working with arbitrary-length integers - extend the loop or use BigInt.
Key Insights
What to Know Cold
- The loop invariant: after iteration i, the top i bits of `result` are the bottom i bits of the original `n`, reversed.
- In Java and TypeScript, signed integers require `>>>` (unsigned right-shift) - signed `>>` would extend the sign bit.
- `>>> 0` in JS coerces back to unsigned 32-bit after any bitwise op - essential for correct output.
- For the follow-up "called many times on different inputs", cache 8-bit or 16-bit reversal tables and compose.
- The divide-and-conquer approach (swap adjacent bits, then pairs, then nibbles…) reverses in O(log 32) = 5 masks - optimal for hardware.
1 example
Worked Examples
Trace first 4 iterations for n=43261596
Binary: 00000010100101000001111010011100
Peel LSB each step, feed into MSB of result. After 32 steps: 00111001011110000010100101000000.
reverseBits(43261596); // 964176192 // iter 1: result=0, n&1=0 → result=0 // iter 2: result=0, n&1=0 → result=0 // ... LSBs of n become MSBs of result
Demonstrates the invariant: LSBs of n become MSBs of result in reverse order.