Skip to content

177 — Reverse Bits

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

177 — Reverse Bits

LeetCode 190 · Easy. Reverse the bits of a given 32-bit unsigned integer.

🍽️ Intuition

Write the number's 32 bits out on a strip of paper, left to right, most-significant bit first. Reversing the bits just means turning that strip of paper around — the bit that was on the far left is now on the far right, and vice versa. The most literal way to do that in code is to actually peel every bit off into an array in its natural left-to-right order, then read that array back-to-front to build the reversed number. But you don't strictly need the intermediate strip of paper: since you're going to read every bit exactly once no matter what, you can just as easily strip bits off one at a time from the original number's low end and feed them straight into the result's low end — building the reversal in a single pass, with no scratch storage at all.

n = 0b00000000000000000000000000001011   (11)

peel LSB -> feed into result's LSB, then shift result left, repeat 32 times:

step   bit peeled   result (after shift-and-OR)
1      1            ...00000001
2      1            ...00000011
3      0            ...00000110
4      1            ...00001101
...    0            ...
32     0            11010000000000000000000000000000

🚩 Pattern-Recognition Cue

"Reverse the bits of a fixed-width integer" signals a shift-and-mask pass: whenever every bit needs to move to a mirrored position across a known, fixed width, you can build the answer by repeatedly pulling one bit off one end and pushing it onto the other, rather than materializing an intermediate representation of the whole number first.

🐢 Brute Force

Peel off all 32 bits into an array in their natural most-significant-to-least-significant order, then rebuild the result by reading that array back-to-front.

func reverseBitsBruteForce(_ n: UInt32) -> UInt32 {
    var bits = [UInt32](repeating: 0, count: 32)

    // peel off bits in order, from the most-significant (bit 31) down to the least-significant (bit 0)
    for i in 0..<32 {
        let shiftAmount = 31 - i
        bits[i] = (n >> shiftAmount) & 1
    }
    // bits[0] = original bit 31 (MSB) ... bits[31] = original bit 0 (LSB)

    // rebuild by reading the array back-to-front, so the original LSB becomes the new MSB
    var result: UInt32 = 0
    for i in stride(from: 31, through: 0, by: -1) {
        result = (result << 1) | bits[i]
    }

    return result
}

// smoke test
print(reverseBitsBruteForce(43_261_596))   // 964176192
print(reverseBitsBruteForce(1))            // 2147483648
print(reverseBitsBruteForce(0))            // 0

Big-O: O(1) time and space in practice, since the width is fixed at 32 — expressed generally, O(b) time and O(b) extra space for the array, where b is the bit width.

🚀 Optimal

Shift and mask in a single pass: pull the lowest bit off n, push it into result from the low end, and shift both, 32 times — no intermediate array needed.

func reverseBits(_ n: UInt32) -> UInt32 {
    var n = n
    var result: UInt32 = 0

    for _ in 0..<32 {
        result = (result << 1) | (n & 1)
        n >>= 1
    }

    return result
}

// smoke test — same cases as the brute force
print(reverseBits(43_261_596))   // 964176192
print(reverseBits(1))            // 2147483648
print(reverseBits(0))            // 0

Big-O: O(1) time in practice (always exactly 32 iterations) — expressed generally, O(b) time. O(1) extra space — just the two 32-bit accumulators, no array.

🔑 The Key Insight

The brute force's array is only ever used to hold bits temporarily between "peel them off in order" and "read them back in the opposite order" — but shifting result left every time a new bit is appended already reverses the arrival order for free. Feeding n's bits into result from the low end, one at a time, means the first bit peeled off ends up shifted furthest to the left by the time the loop finishes — exactly where a full reversal would put it. The array was never structurally necessary; it was just a scratchpad standing in for what the shift-and-OR does directly.

🔗 Related Chapters

  • Arrays and Strings — the brute force's array-of-bits scratch space, filled in one order and read back in the reverse order.
  • Bit Manipulation Tricks — the shift-and-mask trick (result = (result << 1) | (n & 1); n >>= 1) the optimal solution runs on.

🧸 Memory Sentence

Reverse Bits is turning a strip of 32 bits around — shift-and-mask builds the reversal directly, one bit at a time, without ever needing to write the strip down first.

✅ Check Your Understanding

  1. In the optimal loop, why does peeling the lowest bit off n and pushing it into the lowest position of result (before shifting result left) end up reversing the bit order, rather than preserving it?
  2. Trace reverseBits by hand for n = 0b100 (4) and confirm it produces 0b00100000...0 (536870912).
  3. Why does the brute force need to build bits in most-significant-to-least-significant order and then read it back-to-front, instead of just peeling bits off in least-significant-first order to begin with?
  4. Both solutions run their loop exactly 32 times regardless of how many bits are actually set. Why doesn't Brian Kernighan's n & (n - 1) trick from Number of 1 Bits help speed this problem up?

⬅️ Previous: Counting Bits · Next: Missing Number ➡️

Clone this wiki locally