190. Reverse Bits

Reverse Bits looks trivial until Java’s missing unsigned type makes you second-guess the shift operator. The mechanics are pure bit manipulation — read one bit off the bottom, stack it onto the top — and the one nuance worth understanding is why people reach for >>> over >> even when both happen to work.

The problem

You get a 32-bit integer and must return the value whose bits are the input’s bits in reverse order — bit 0 becomes bit 31, bit 1 becomes bit 30, and so on. (Full statement on LeetCode.)

If the low byte of the input is ...00000011, those two set bits end up as the top two bits of the answer. Reversing the order flips their place value completely, so a tiny number can map to a huge one.

Intuition: drain from the bottom, stack on the top

Think of two 32-bit registers. On each step you peel the lowest bit off the input and place it as the newest bit of the result. Because the result gets shifted left first, whatever you placed a moment ago slides one position higher — so the first bit you read ends up highest, the last bit lowest. That’s exactly a reversal.

Two operations do the whole job per iteration:

• n & 1 reads the current lowest bit of the input.
• result = (result << 1) | bit opens a new slot at the bottom of the result and drops the bit in.

Run it 32 times and every bit has crossed to its mirror position. The work is fixed at 32 steps regardless of the value, so the time is $O(32) = O(1)$.

The one detail worth pausing on is the shift on n. Java has no unsigned int, so >> is arithmetic — it copies the sign bit inward, and an input with bit 31 set (a negative int) keeps getting 1s injected from the top. Here that turns out not to matter: the fixed 32-iteration loop only ever reads bit 0, and those low bits shift down the same way no matter what the high bits do, so >> and >>> return the identical answer. The reason to reach for >>>, the logical right shift, is habit and safety — the moment you rewrite this as the common while (n != 0) early-exit loop, an arithmetic shift on a negative int never reaches zero and spins forever, while the logical shift drains it to 0.

Solution

class Solution {
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);  // open a bottom slot, drop in n's low bit
            n >>>= 1;                            // logical shift: feed 0s, no sign extension
        }
        return result;
    }
}

The follow-up asks what to do if this runs a lot. Reversing one bit at a time repeats work; reversing a whole byte at a time and caching it is faster. There are only 256 byte values, so a memoized lookup reverses each of the four bytes and slots them into swapped positions:

class Solution {
    private final Map<Integer, Integer> cache = new HashMap<>();

    public int reverseBits(int n) {
        int result = 0;
        for (int shift = 0; shift < 32; shift += 8) {
            int b = (n >>> shift) & 0xff;                 // grab one byte
            int reversed = cache.computeIfAbsent(b, this::reverseByte);
            result |= reversed << (24 - shift);           // place it at the mirrored byte position
        }
        return result;
    }

    private int reverseByte(int b) {
        int r = 0;
        for (int i = 0; i < 8; i++) {
            r = (r << 1) | (b & 1);
            b >>= 1;
        }
        return r;
    }
}

Across many calls the cache warms up and each reversal becomes four map hits and some shifts.

Complexity

Approach	Time	Space
Bit-by-bit loop	$O(1)$ (32 steps)	$O(1)$
Byte cache	$O(1)$ per call	$O(1)$ (≤ 256 entries)

The width is fixed, so both are constant time in the strict sense. The byte version wins the constant factor when the function is hot, at the cost of a small table.

In an interview

Say the reversal out loud before coding: “I pull the lowest bit and push it onto the result, which I shift left each round, so the first bit read lands highest.” Then write the loop. The single detail worth flagging without prompting is >>> versus >>. In this fixed 32-step loop both actually return the same value, but say why you still default to the logical shift: it keeps a while (n != 0) variant from looping forever on a negative input, and it signals you know Java sign-extends >>. Interviewers who know the language are watching for whether you reach for it deliberately.

If they push on the follow-up, reach for the byte lookup table rather than hand-waving; it’s the concrete answer to “called many times.” This same read-a-bit-with-& 1, shift-with->>> toolkit shows up in Number of 1 Bits and Counting Bits, and the bit manipulation hub collects the rest of the family.

References

• LeetCode 190 — Reverse Bits