Reverse Bits LeetCode 190 Deep Dive

LeetCode 190 — Reverse Bits — gives you a 32-bit unsigned integer and asks you to return the integer formed by reversing its bits. For example, the input 43261596 has the 32-bit binary representation 00000010100101000001111010011100; reversing all 32 bits gives 00111001011110000010100101000000, which is the integer 964176192. Another example: input 4294967293 (11111111111111111111111111111101 in binary) reversed is 10111111111111111111111111111111, which is 3221225471.

The problem is rated Easy but it demands precise bit manipulation. Interviewers use it to check whether you can work directly at the bit level — extracting individual bits, building a result by shifting and ORing, and handling the fixed 32-bit width constraint. Unlike Number of 1 Bits which counts bits, Reverse Bits requires you to reposition every single bit into its mirror position.

The constraints specify that n is treated as an unsigned 32-bit integer. Python integers have unlimited precision, so you must ensure the result is masked to 32 bits with & 0xFFFFFFFF if the computation can produce values wider than 32 bits. Java uses >>> for unsigned right shift to avoid sign extension. The follow-up question asks: if this function is called many times, how would you optimize?

The core idea is to process n one bit at a time from right to left, placing each extracted bit into the mirror position of the result accumulator from left to right. Initialize result = 0. On each of 32 iterations: left-shift result by 1 to make room for the next bit; OR in the least significant bit of n using n & 1; then right-shift n by 1 to expose the next bit. After 32 iterations, result holds the bit-reversed value.

This approach runs in O(32) = O(1) time and O(1) space. It is simple to implement, easy to verify, and handles the 32-bit fixed-width requirement naturally — the loop always runs exactly 32 times regardless of the value of n. The result is built from the most significant position down: the first extracted bit from n (its LSB) becomes the MSB of result, the second extracted bit becomes the second-most-significant bit, and so on.

For an interview this is the expected primary approach. Explain each step: result << 1 makes room, n & 1 extracts the current bit, the OR places it, and n >>= 1 advances to the next bit. All four operations happen in two lines per iteration, making the logic easy to trace on a whiteboard with a small example like reversing 8 bits of the number 6 (00000110 → 01100000 = 96).

The implementation is compact: initialize result = 0, run a loop 32 times, apply the two core operations, and return result. In Python, right-shifting a positive integer with >>= 1 is safe. In Java, use n >>>= 1 (unsigned right shift) to avoid sign extension when n is a negative int value. The final result in Python is naturally a non-negative integer; in Java it is an int (which may appear negative when printed, but the bit pattern is correct).

To verify correctness, trace through a small example. Take n = 0b00000000000000000000000000000001 (the integer 1). After 32 iterations, the single 1-bit that started at position 0 (LSB) is extracted first and placed as the MSB of result. All subsequent iterations extract 0 bits and shift result left without adding anything. Final result = 0b10000000000000000000000000000000 = 2147483648, which is correct.

Edge cases: n = 0 produces result = 0 (all 32 zero bits reversed are still zero). n = 0xFFFFFFFF (all 32 bits set) reversed is still 0xFFFFFFFF. n = 1 reversed is 2147483648 (0x80000000). n = 2147483648 reversed is 1. These symmetric cases are useful sanity checks during an interview.

The divide-and-conquer approach reverses the 32 bits in 5 swap operations rather than 32 iterations. The idea is to split the bits into progressively larger groups and swap each group with its mirror: first swap each bit with its neighbor (swap adjacent pairs), then swap each 2-bit group with its neighbor, then each 4-bit nibble, then each byte, then the two 16-bit halves. After all 5 swaps the bits are fully reversed.

Each swap level uses a bit mask. For adjacent bit swaps: mask = 0x55555555 (alternating 0101...); extract even-position bits with n & mask, odd-position bits with n & ~mask; shift even bits left by 1 and odd bits right by 1; OR together. For 2-bit group swaps: mask = 0x33333333 (0011 0011...); shift by 2. For nibble swaps: mask = 0x0F0F0F0F; shift by 4. For byte swaps: mask = 0x00FF00FF; shift by 8. For half-word swaps: shift by 16 (no mask needed).

This approach completes in exactly 5 operations regardless of input value. It has O(1) time and O(1) space and is significantly faster than the 32-iteration loop for hardware implementations where each operation maps to a single instruction. Many compiler intrinsics and CPU bit-reversal instructions implement this exact divide-and-conquer strategy under the hood.

The follow-up question asks: if reverseBits is called many times, how would you optimize? The answer is to precompute a lookup table of all 256 possible reversed bytes. A byte has 8 bits and 256 possible values (0–255). For each value b, compute reversedByte[b] = the 8-bit reversal of b. This table requires 256 entries and can be computed once at initialization using the bit-by-bit approach applied to 8-bit values.

To reverse a 32-bit integer n using the cache: split n into four bytes (byte0 = n & 0xFF, byte1 = (n >> 8) & 0xFF, byte2 = (n >> 16) & 0xFF, byte3 = (n >> 24) & 0xFF). Look up each byte in the cache. Assemble the result in reverse byte order: result = (reversedByte[byte0] << 24) | (reversedByte[byte1] << 16) | (reversedByte[byte2] << 8) | reversedByte[byte3]. The key insight is that since we reversed the byte order and reversed each byte, the combined effect is a full 32-bit reversal.

This approach has O(1) time per call and O(256) = O(1) space for the cache. Building the cache takes O(256 * 8) = O(1) time upfront. In practice, the cache fits entirely in a CPU cache line and each call requires only four table lookups plus bit shifts — much faster than 32 iterations for systems making millions of calls. This is the expected answer to the follow-up question in an interview setting.

Python — bit-by-bit: def reverseBits(n): result = 0; [code] for _ in range(32): result = (result << 1) | (n & 1); n >>= 1; return result. Python integers have unlimited width, so result may grow beyond 32 bits if intermediate values are very large, but for this problem the output is always at most 32 bits. If you need to guarantee unsigned 32-bit output, add return result & 0xFFFFFFFF. The bit-by-bit version is O(1) time and O(1) space.

Java — bit-by-bit with unsigned right shift: public int reverseBits(int n) { int result = 0; for (int i = 0; i < 32; i++) { result = (result << 1) | (n & 1); n >>>= 1; } return result; }. The key difference from Python is n >>>= 1 (unsigned right shift) instead of n >>= 1. In Java, int is signed 32 bits; >>> fills the vacated high bit with 0 rather than the sign bit, ensuring correct behavior for large inputs. The result is also a signed Java int, but its bit pattern is the correct 32-bit reversal.

Both Python and Java versions share O(1) time and O(1) space complexity. The loop always executes exactly 32 iterations. The divide-and-conquer version completes in 5 operations (also O(1)) and is preferred when performance matters. In an interview, implement the bit-by-bit version first for clarity, then offer the divide-and-conquer optimization as a follow-up, and describe the byte-cache approach in response to the multiple-calls follow-up question.

Number of 1 Bits (LeetCode 191) is the natural companion to Reverse Bits — both operate on 32-bit unsigned integers bit by bit. LeetCode 191 counts set bits using n & 1 and right shift (or Brian Kernighan's n & (n-1) trick), while LeetCode 190 uses the same n & 1 extraction but places each bit into a reversed result with left shift and OR. Mastering both problems gives you the two core 32-bit scanning patterns used throughout bit manipulation interviews.

Counting Bits (LeetCode 338) extends the bit-counting concept to an array: given n, return result[i] = popcount(i) for all i from 0 to n. The optimal DP solution uses result[i] = result[i >> 1] + (i & 1), reducing the problem to a right shift and bit check — directly related to the bit-by-bit scan in Reverse Bits. Sum of Two Integers (LeetCode 371) uses XOR for the sum without carry and AND + left shift for the carry, iterating until carry is zero — another application of bitwise shift and OR.

The bit reversal family — Reverse Bits, Number of 1 Bits, Counting Bits, Sum of Two Integers, and Missing Number — represents the core bit manipulation curriculum for FAANG interviews. Each problem teaches a different facet: bit extraction, bit counting, DP on bits, carry propagation, and XOR identity. Working through all five gives you the vocabulary to tackle nearly any bit manipulation problem in a technical interview.