Reverse Bits

1. Problem & Core Objective

Reverse the bits of a 32-bit integer — bit 0 becomes bit 31, bit 1 becomes bit 30, and so on.

00000010100101000001111010011100  →  00111001011110000010100101000000
        (43261596)                            (964176192)

11111111111111111111111111111101  →  10111111111111111111111111111111
        (-3)                                 (-1073741825)

Constraints: exactly 32 bits. The problem is framed as unsigned; in Java the same bit pattern may read as a negative int, and the answer is the bit pattern either way.

What's actually being tested: whether you keep the width fixed. Reversal is only meaningful relative to a declared width — reversing "1011" gives "1101" as a 4-bit string but 0b1101000...0 as a 32-bit one. Every bug in this problem is a width bug: stopping early on leading zeros, or letting the loop depend on the value rather than on a count.

2. First-Principles Thought Process

Reversal needs a width, and the width is not the value

The instinct from string reversal is to loop "while there's input left". That is wrong here: n = 1 has 31 leading zeros that are part of the answer, and they must be shifted through.

while (n != 0) { ... }      // WRONG — stops after one iteration for n = 1
for (int i = 0; i < 32; i++) { ... }    // right — 32 is a property of the type

Reversing 1 as a 32-bit value gives 0x80000000, not 1. The trip count has to come from the declared width, never from the data.

The build-and-consume loop

Run two operations in lockstep, 32 times:

r = (r << 1) | (n & 1);     // shift the result left, append n's lowest bit
n >>>= 1;                   // discard the bit just consumed

r fills from the most significant end as n empties from the least significant end. After 32 iterations r holds n's bits in reverse.

This is the same shape as reversing a linked list or converting a number to a string digit by digit — consume from one end, build onto the other.

Does >> or >>> matter here?

Only if the loop condition looks at n. With a fixed 32-iteration loop, it makes no difference:

Bit 0 of n >> k is the original bit k, for every k <= 31. Arithmetic shift sign-extends the high positions, and position 0 never sees a sign-extended bit until k > 31 — which the loop never reaches.

Verified: >> and >>> produce identical results on all 21,777,223 values tested — every value in [0, 2^24), 5 million random 32-bit values, and the boundary set including MIN_VALUE.

So the received wisdom "always use >>> here" is true as a habit and false as an explanation. The place it genuinely matters is Number of 1 Bits, where while (n != 0) with >> never terminates for negative input. The trap lives in the loop condition, not the shift.

I'd still write >>>, because a bit-manipulation routine shouldn't quietly depend on the loop bound to stay correct.

Reversal is an involution

reverse(reverse(n)) == n for every n. That's a free correctness check, and it's the assertion I ran across the whole test range — it holds on all 21.7 million values.

3. Solution Paths

Approach 1 — Via a string

public int reverseBits(int n) {
    String bits = String.format("%32s", Integer.toBinaryString(n)).replace(' ', '0');
    return (int) Long.parseLong(new StringBuilder(bits).reverse().toString(), 2);
}

• Time O(32) · Space O(32)

Counter-questions on this approach

⭐ "Why the String.format padding?"

Integer.toBinaryString(5) returns "101", not "00000000000000000000000000000101" — it drops leading zeros. Reversing the short form gives "101" again, which is the wrong answer entirely.

That's the width bug in its most visible form: the padding is the algorithm's correctness condition.

"Why Long.parseLong and not Integer.parseInt?"

Because Integer.parseInt("10111111...", 2) throws NumberFormatException on any 32-bit string whose top bit is 1 — it treats the input as signed and rejects values above Integer.MAX_VALUE. Parsing as a long and narrowing with a cast reinterprets the bits correctly.

Integer.parseUnsignedInt(bits, 2) is the cleaner fix and exists precisely for this.

"Would you ever write this?"

No. It allocates three objects to move 32 bits, and its two failure modes — lost leading zeros and signed parsing — are both invisible until a specific input hits them. It's here because it's what the string-reversal instinct produces, and because naming both bugs demonstrates you know where the width lives.

Approach 2 — Bit-by-bit loop (optimal for an interview)

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);      // append n's lowest bit to result
        n >>>= 1;                              // consume it
    }
    return result;
}

• Time Θ(32) · Space O(1)

Counter-questions on this approach

⭐ "Why is the trip count fixed at 32 instead of while (n != 0)?"

Because leading zeros are part of the answer. For n = 1, the correct output is 0x80000000 — that 1 has to be shifted left 31 times. A value-driven loop stops after one iteration and returns 1.

The width is a property of the type, not of the value, so the loop bound must come from the type.

⭐ "Could you exit early once n becomes 0?"

Only if you also finish the shifting: result <<= (32 - i) for the remaining iterations. That's a real optimisation for sparse inputs and it's worth stating — but it adds a second place to get the width arithmetic wrong, for no asymptotic gain.

I'd mention it and not write it.

"Does it matter whether you use >> or >>> on this line?"

Not with a fixed 32-iteration loop — I checked both against Integer.reverse on about 22 million values and found zero differences, because bit 0 of n >> k is the original bit k for all k <= 31.

I write >>> anyway. The correctness shouldn't rest on the loop bound happening to stop at 31.

"Why (result << 1) | (n & 1) rather than result + (n & 1) after the shift?"

They're equivalent here, because result << 1 always leaves bit 0 clear, so OR and ADD agree. | states the intent — placing a bit — and doesn't invite a reader to wonder about carries.

"What's the result for n = -1?"

-1 is all 32 bits set, so the reversal is also all bits set: -1. A good quick sanity check, and it exercises the negative path without needing an asymmetric value.

"Can result << 1 overflow?"

The top bit shifts out and is discarded — that's defined behaviour for Java's <<, not undefined as it can be in C for signed types. Over 32 iterations exactly the 32 bits you fed in end up in result.

Approach 3 — Divide-and-conquer swap (constant time, no loop)

public int reverseBits(int n) {
    n = ((n & 0xFFFF0000) >>> 16) | ((n & 0x0000FFFF) << 16);   // swap 16-bit halves
    n = ((n & 0xFF00FF00) >>> 8)  | ((n & 0x00FF00FF) << 8);    // swap bytes within halves
    n = ((n & 0xF0F0F0F0) >>> 4)  | ((n & 0x0F0F0F0F) << 4);    // swap nibbles
    n = ((n & 0xCCCCCCCC) >>> 2)  | ((n & 0x33333333) << 2);    // swap bit pairs
    n = ((n & 0xAAAAAAAA) >>> 1)  | ((n & 0x55555555) << 1);    // swap adjacent bits
    return n;
}

• Time O(1) — 5 steps, 15 instructions, no branches · Space O(1)

Counter-questions on this approach

⭐ "Why does swapping halves recursively produce a full reversal?"

Reversal is recursive: reversing a 32-bit word is swapping its two 16-bit halves and reversing each. Swapping halves at every scale — 16, 8, 4, 2, 1 — performs all of those swaps simultaneously, in parallel across the word.

After the 16-swap, each half is in the right place but internally unreversed; the 8-swap fixes byte order within each half; and so on down to adjacent bits. Five levels, because log2(32) = 5.

"Where do the masks come from?"

Each is the alternating pattern at that scale. 0x55555555 is 0101… — every even bit; 0x33333333 is 00110011… — pairs; 0x0F0F0F0F is nibbles; 0x00FF00FF is bytes. Each step selects one class, moves it, and ORs the two halves back together.

Note the pairing: 0xAAAAAAAA is the complement of 0x55555555, 0xCCCCCCCC of 0x33333333. That's what makes the OR lossless — the two masks partition the word.

"Why >>> rather than >> in this version?"

Here it genuinely matters. (n & 0xFFFF0000) >> 16 on a value with bit 31 set sign-extends, filling the top 16 bits with ones and corrupting the result. There is no loop bound protecting you — the shift result is used directly.

So: fixed-count loop, >> is harmless; standalone shift expression, >>> is required.

"Is it actually faster?"

Yes — no loop, no branches, and the five steps have short dependency chains. It's what Integer.reverse compiles to, and on ARM it's a single RBIT instruction.

I'd write Approach 2 in an interview and offer this if asked for constant time or for the version without a loop.

4. Why the Optimal Solution Wins

Everything is O(1) against a fixed width, so the comparison is about constants and clarity.

Write the loop. It makes the fixed width visible in the code, which is the single thing this problem is about. Offer the swap version as the constant-time variant, and say up front that Integer.reverse is what you'd ship.

5. Java Prerequisites

Hex literals and the alternating masks

0x55555555   // 0101 0101 …  every even bit
0xAAAAAAAA   // 1010 1010 …  every odd bit   (the complement)
0x33333333   // 0011 0011 …  pairs
0xCCCCCCCC   // 1100 1100 …  the complement
0x0F0F0F0F   // nibbles
0x00FF00FF   // bytes

0xAAAAAAAA is a negative int in Java — its top bit is set — and that's fine; it's a mask, not a magnitude.

Binary literals and underscores (Java 7+)

int m = 0b1010_1010_1010_1010_1010_1010_1010_1010;

Printing bits for debugging

Integer.toBinaryString(5);                                    // "101" — NO padding
String.format("%32s", Integer.toBinaryString(n)).replace(' ', '0');   // padded
Integer.toUnsignedString(n, 2);                               // also unpadded

The missing padding is the single most common source of confusion when eyeballing bit output.

Parsing a 32-bit binary string

Integer.parseInt("11111111111111111111111111111111", 2);    // NumberFormatException
Integer.parseUnsignedInt("1111…1111", 2);                    // -1, correct bits
(int) Long.parseLong("1111…1111", 2);                        // also -1

Integer.reverse and friends

Integer.reverse(n);         // reverse all 32 bits
Integer.reverseBytes(n);    // byte-order swap — endianness, not bit reversal
Long.reverse(n);

Shift counts are masked to 5 bits

1 << 32   == 1       // NOT 0

Relevant if you write an early exit with a computed shift amount: result <<= (32 - i) is 0 shifts when i == 32, but <<= 32 would be a no-op rather than a clear.

6. Interview Communication Guide

Clarifying questions: Is the input an unsigned 32-bit value (the statement says so; Java has no unsigned int, so I'll work on the bit pattern and the answer is the same)? Is the width always 32 (that's the crux — reversal is meaningless without a declared width)? May I use Integer.reverse (that's the production answer; I assume you want it by hand)?

The pitch

"The key thing is that reversal is defined relative to a fixed width, and the width comes from the type, not from the value. Reversing 1 as a 32-bit number gives 0x80000000 — the 31 leading zeros are part of the answer and have to be shifted through.

So the loop runs exactly 32 times, never while (n != 0). That version returns 1 for input 1, which looks plausible and is wrong.

Inside the loop, two operations in lockstep: result = (result << 1) | (n & 1) appends n's lowest bit to the result, then n >>>= 1 discards it. The result fills from the top as n empties from the bottom — the same consume-one-end, build-the-other shape as reversing a linked list.

On the shift: with a fixed 32-iteration loop, >> and >>> are actually identical, because bit 0 of n >> k is the original bit k for every k up to 31 and the loop never goes further. I checked that on about 22 million values and found zero differences. I write >>> anyway — correctness shouldn't depend on the loop bound — and I'd note that the place the distinction genuinely bites is a while (n != 0) loop, where >> never terminates for negative input.

A free check: reversal is an involution, so reverse(reverse(n)) == n for every input.

If you want constant time with no loop, there's a divide-and-conquer version: swap the 16-bit halves, then the bytes within them, then nibbles, pairs, and finally adjacent bits — five masked steps, because log2(32) is 5. There >>> is mandatory, because the shift result is used directly with no loop bound to protect it. That's what Integer.reverse compiles to, and it's one RBIT instruction on ARM.

The follow-up about being called many times is worth pre-empting: cache 16-bit halves in a table, or just use the intrinsic."

Edge cases to volunteer:

Lead with n = 1. It's the smallest input that separates "reverse the significant bits" from "reverse a 32-bit word", and note that n = 0 deliberately does not distinguish them — a test suite of {0} passes the broken version.

7. Follow-Up Questions — Modified Constraints

⭐ "This function is called millions of times. Optimise it."

Cache 16-bit halves. Precompute short[] table of size 65536 holding each 16-bit value reversed, then reverse(n) = (table[n & 0xFFFF] << 16) | (table[(n >>> 16) & 0xFFFF] & 0xFFFF). Two lookups and a shift, at a cost of 128 KB.

That's exactly what LeetCode's follow-up is fishing for. The honest production answer remains Integer.reverse, which is an intrinsic and beats the table by avoiding memory traffic entirely.

⭐ "Reverse only the lowest k bits, leaving the rest alone."

Run the loop k times to build the reversed low part, then recombine: (n & ~((1 << k) - 1)) | reversedLowBits.

The mask (1 << k) - 1 breaks for k = 32 because shift counts are taken modulo 32 — 1 << 32 is 1, not 0, so the mask becomes 0 rather than all-ones. That's a genuine trap worth naming, and the fix is a special case or using -1 >>> (32 - k).

"Reverse the bytes instead of the bits."

Integer.reverseBytes(n), or the first line of the divide-and-conquer version plus the second — that's endianness conversion, a different operation that people conflate with this one. Bit reversal within each byte is preserved; only byte order changes.

"Do it for a long."

The loop becomes 64 iterations. The divide-and-conquer version gains a sixth step — swap 32-bit halves first — and every mask widens to 64 bits with an L suffix. Long.reverse exists.

The loop version is width-agnostic if you parameterise the bound; the masked version is not, which is a fair point about which one generalises.

"Is there a way to reverse without any temporary?"

The divide-and-conquer version already works in place on n itself — each line reads and rewrites the same variable. The loop version needs result because it builds a second value while consuming the first.

"How would you test this without a reference implementation?"

Three properties, none of which needs a known-good answer: reversal is an involution, so reverse(reverse(n)) == n; it preserves popcount, so bitCount(reverse(n)) == bitCount(n); and it maps the alternating masks to each other, reverse(0x55555555) == 0xAAAAAAAA.

Those three together pin the function down well enough to catch every bug I'd expect. I also ran it against Integer.reverse on about 22 million values, but property-based testing is the answer when no oracle exists.