Loading…

easyBit ManipulationLC #190Sometimes asked

Reverse Bits

Q: How do you solve Reverse Bits using the Bit-by-Bit — Shift In, Shift Out approach?

When to use it: The clean default everyone should produce first. 'Pop the low bit of n, push it onto result, repeat 32 times.' Build the answer bit by bit. Each iteration: read the lowest bit of `n` with `n & 1`, shift `result` left by one to open a slot, OR the bit into that slot, then shift `n` right to expose the next bit. After 32 iterations the bits have been transferred in mirror order. **Why the two shifts mirror each other.** You consume `n` from its *low* end (`n & 1` then `n >>= 1`) and you grow `result` at its *low* end (`result << 1 | bit`). The first bit you read becomes the most significant bit of `result` because it gets shifted left 31 more times as later bits arrive. That is precisely the position-`i` → position-`31 - i` mapping the problem asks for. **Why exactly 32 iterations, never early-exit.** If you stop when `n` becomes `0`, you skip the input's leading zeros — but those zeros must become trailing zeros in the output, and equivalently the set bits they precede must be shifted to their correct high positions. Running the full 32 steps guarantees every bit, including zeros, lands where it belongs. Example: `n = 1` needs all 32 left-shifts of `result` to push that single bit to position 31. **Why unsigned shifts matter.** In Java, `n >>= 1` on a negative value copies the sign bit downward, injecting phantom 1s and corrupting the reversal. `n >>>= 1` pulls in `0`, treating the value as the unsigned 32-bit pattern the problem specifies. In Python the *build* never exceeds 32 bits, but if you shift a wider intermediate you mask with `& 0xFFFFFFFF` to clamp back into the 32-bit window. Time complexity: O(32) = O(1). Space complexity: O(1).

Q: How do you solve Reverse Bits using the Byte Cache — Reverse and Reorder Bytes (Optimal for Repeated Calls) approach?

When to use it: The follow-up answer for 'called many times'. 'Precompute reversed bytes once; each call reverses 4 bytes and swaps their order.' Decompose the 32-bit number into four 8-bit bytes. Reverse each byte using a precomputed lookup table, then place the reversed byte into the *opposite* byte position: byte 0 → byte 3, byte 1 → byte 2, and so on. The concatenation of the reversed bytes in swapped order is the fully reversed integer. **Why reversing bytes then swapping their order works.** Bit reversal is symmetric: the lowest 8 bits of the input become the highest 8 bits of the output, *and* within that group the bits are themselves reversed. So 'reverse each byte' handles the within-byte mirroring and 'swap byte positions' handles the across-byte mirroring. Do both and every bit reaches position `31 - i`. **Why caching pays off.** A byte has only 256 possible values, so all reversed bytes can be precomputed once. Then each call is four lookups instead of 32 iterations — and across millions of calls that table is built a single time. This directly answers the 'called many times' follow-up. **Unsigned handling, again.** In Java extract each byte with `(n >>> (8 * i)) & 0xFF` — the unsigned shift plus the `& 0xFF` mask isolate a clean 0–255 byte even from a negative `n`. In Python the same `& 0xFF` extraction works, and the final assembled value is naturally a non-negative 32-bit integer; mask the result with `& 0xFFFFFFFF` if any intermediate widened. Time complexity: O(1) — 4 lookups/call. Space complexity: O(256).

LCPractice

Bit Manipulation · 4 of 20 · 7 min

Reverse the bits of a given 32-bit unsigned integer.

Note: in some languages (such as Java) there is no unsigned integer type, so the input and output are given as signed integers — they should not affect your implementation, as the internal binary representation is the same whether signed or unsigned.

Follow-up: if this function is called many times, how would you optimize it?

In plain English

Take a 32-bit number and produce the number whose binary digits are in the exact reverse order — bit at position 0 goes to position 31, bit 1 to bit 30, and so on. Leading zeros matter: they become trailing zeros after the flip, so the width is fixed at 32.

Examples

Example 1

Input: n = 43261596 (00000010100101000001111010011100)
Output: 964176192 (00111001011110000010100101000000)
Note: Reading the input right-to-left gives the output left-to-right — the bit string is mirrored.

Example 2

Input: n = 4294967293 (11111111111111111111111111111101)
Output: 3221225471 (10111111111111111111111111111111)
Note: Only bit 1 is 0; after reversal that 0 sits at position 30. All-ones-but-one flips to all-ones-but-one on the other side.

Example 3

Input: n = 1 (00000000000000000000000000000001)
Output: 2147483648 (10000000000000000000000000000000)
Note: The single set bit at position 0 moves to position 31. Demonstrates why all 32 iterations matter.

Constraints

The input is a 32-bit unsigned integer
In Java the value is given as a signed int (same bit pattern)
Output is the bit-reversed 32-bit value
Follow-up: optimize for many repeated calls (caching)

Clarifying questions4First question: Is the width fixed at 32 bits?Explore questions

Q1.Is the width fixed at 32 bits?
Yes. That matters because leading zeros must be reversed too — a 1 at position 0 must land at position 31 even if the higher bits are all zero.
Q2.How do I handle the lack of unsigned ints in Java?
Use the unsigned right shift `>>>` when consuming bits so the sign bit doesn't propagate. The 32-bit pattern is identical regardless of signedness.
Q3.In Python, won't the integer grow beyond 32 bits?
Python ints are arbitrary-precision. The bit-by-bit build naturally stays within 32 bits, but if I right-shift a wider value I mask with & 0xFFFFFFFF to stay in the 32-bit window.
Q4.Will this be called repeatedly?
The follow-up says yes. Then I'd precompute reversed bytes (256-entry table) and reverse the number by reversing and reordering its four bytes.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Reverse the 32 bits of an unsigned integer. Build the answer one bit at a time: pull the lowest bit of the input with `n & 1`, append it to the result with `result = (result << 1) | bit`, then drop it from the input with an UNSIGNED shift. For repeated calls, cache reversed bytes and stitch four of them together.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can manipulate bits at fixed positions and — critically — handle unsignedness correctly in a language without unsigned types (Java's signed int, Python's unbounded int).

Where candidates slip

Using a signed right shift in Java (corrupts negatives), stopping the loop early instead of a full 32 iterations (drops leading-zero handling), or in Python letting the int grow past 32 bits without masking.

How to stand out

Name the read-bit / write-bit symmetry, state that position i maps to 31 - i, handle unsigned correctly without prompting, and offer the byte-cache optimisation for the 'called many times' follow-up.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Bit-by-Bit — Shift In, Shift Out	`O(32) = O(1)`	`O(1)`	The clean default everyone should produce first. 'Pop the low bit of n, push it onto result, repeat 32 times.'	Read
2	Byte Cache — Reverse and Reorder Bytes (Optimal for Repeated Calls)Optimal	`O(1) — 4 lookups/call`	`O(256)`	The follow-up answer for 'called many times'. 'Precompute reversed bytes once; each call reverses 4 bytes and swaps their order.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewReverse 32 bitsCalled once or many times?OnceMany timesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Bit-by-Bit — Shift In, Shift Out

TimeO(32) = O(1)SpaceO(1)

The clean default everyone should produce first. 'Pop the low bit of n, push it onto result, repeat 32 times.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you read the input's bits from the lowest upward, and write them into the result from the lowest upward, what order does the result end up in?

2Hint 2Explore hint

Each step: take the lowest bit of n (n & 1), and append it to result by shifting result left and OR-ing the bit in.

3Hint 3Explore hint

Then shift n right (UNSIGNED in Java) to expose the next bit. Do this exactly 32 times so leading zeros are placed too.

A · Core idea

Build the answer bit by bit. Each iteration: read the lowest bit of n with n & 1, shift result left by one to open a slot, OR the bit into that slot, then shift n right to expose the next bit. After 32 iterations the bits have been transferred in mirror order.

Why the two shifts mirror each other. You consume n from its low end (n & 1 then n >>= 1) and you grow result at its low end (result << 1 | bit). The first bit you read becomes the most significant bit of result because it gets shifted left 31 more times as later bits arrive. That is precisely the position-i → position-31 - i mapping the problem asks for.

Why exactly 32 iterations, never early-exit. If you stop when n becomes 0, you skip the input's leading zeros — but those zeros must become trailing zeros in the output, and equivalently the set bits they precede must be shifted to their correct high positions. Running the full 32 steps guarantees every bit, including zeros, lands where it belongs. Example: n = 1 needs all 32 left-shifts of result to push that single bit to position 31.

Why unsigned shifts matter. In Java, n >>= 1 on a negative value copies the sign bit downward, injecting phantom 1s and corrupting the reversal. n >>>= 1 pulls in 0, treating the value as the unsigned 32-bit pattern the problem specifies. In Python the build never exceeds 32 bits, but if you shift a wider intermediate you mask with & 0xFFFFFFFF to clamp back into the 32-bit window.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 0b101 (only low 3 bits shown of 32)

Interactive diagram

First bit read becomes the top bit

step 1

Active call / nodeSupporting contextReturned stateNot active

Reading from n's low end and writing to result's low end mirrors the bit order.

Final result0b101 reversed within 32 bits → 1010...0 (bit that was at pos 0 is now at pos 31)

C · Code with teaching comments

Reference implementation previewpublic int reverseBits(int n) { int result = 0; for (int i = 0; i < 32; i++) { result = (result << 1) | (n & 1); n >>>= 1;Explore the full code

solution.javaJava

Bit-by-Bit — Shift In, Shift Out — reference

2 teaching notes

1
public int reverseBits(int n) {
2
    int result = 0;
3
    for (int i = 0; i < 32; i++) {
4
        // Open a low slot in result (<<1) and drop in n's current lowest bit (n & 1).
5
        result = (result << 1) | (n & 1);
6
        // UNSIGNED shift: expose the next bit without sign-extending. Plain >> would
7
        // inject 1s on a negative input.
8
        n >>>= 1;
9
    }
10
    return result;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(32) = O(1) timeO(1) spaceOpen the invariant and proofExplore the proof

Reversal is just two coordinated queues: you dequeue bits from the bottom of n and enqueue them onto the bottom of result. Because result keeps shifting left, the earliest-dequeued bit floats to the top — a stack/queue intuition expressed in pure bit ops.

ComplexityO(32) = O(1) time, O(1) space — Exactly 32 iterations of constant-time bit ops regardless of input, so O(1) time. Only the result accumulator is stored — O(1) space.

E · Edge cases and pitfalls5n = 0 — Every bit read is 0; result stays 0 through all 32 shifts → returns 0.Explore edge cases

Edge cases handled

n = 0Every bit read is 0; result stays 0 through all 32 shifts → returns 0.
n = -1 (0xFFFFFFFF)All 32 bits are 1; with >>> each is read and re-placed → returns -1 (0xFFFFFFFF). With >> the loop would still read 1s but on a single sign-extended value.

Pitfalls

Using >> instead of >>> in Java — corrupts the high bits of a negative input.
Stopping the loop when n == 0 — drops leading zeros and leaves set bits at the wrong positions.
In Python, right-shifting a value wider than 32 bits without `& 0xFFFFFFFF` — lets the int grow unbounded.

03.2

Approach 2 of 2 · Optimal

Byte Cache — Reverse and Reorder Bytes (Optimal for Repeated Calls)

TimeO(1) — 4 lookups/callSpaceO(256)

The follow-up answer for 'called many times'. 'Precompute reversed bytes once; each call reverses 4 bytes and swaps their order.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you'll reverse millions of numbers, what work can you do ONCE and reuse? A 32-bit int is just 4 bytes.

2Hint 2Explore hint

Reversing the whole number = reverse each of the 4 bytes individually, then put the bytes in the opposite order (byte 0 ↔ byte 3, byte 1 ↔ byte 2).

3Hint 3Explore hint

Precompute a 256-entry table of reversed bytes. Per call: split n into 4 bytes, look up each reversed byte, and shift it to its mirrored byte position.

A · Core idea

Decompose the 32-bit number into four 8-bit bytes. Reverse each byte using a precomputed lookup table, then place the reversed byte into the opposite byte position: byte 0 → byte 3, byte 1 → byte 2, and so on. The concatenation of the reversed bytes in swapped order is the fully reversed integer.

Why reversing bytes then swapping their order works. Bit reversal is symmetric: the lowest 8 bits of the input become the highest 8 bits of the output, and within that group the bits are themselves reversed. So 'reverse each byte' handles the within-byte mirroring and 'swap byte positions' handles the across-byte mirroring. Do both and every bit reaches position 31 - i.

Why caching pays off. A byte has only 256 possible values, so all reversed bytes can be precomputed once. Then each call is four lookups instead of 32 iterations — and across millions of calls that table is built a single time. This directly answers the 'called many times' follow-up.

Unsigned handling, again. In Java extract each byte with (n >>> (8 * i)) & 0xFF — the unsigned shift plus the & 0xFF mask isolate a clean 0–255 byte even from a negative n. In Python the same & 0xFF extraction works, and the final assembled value is naturally a non-negative 32-bit integer; mask the result with & 0xFFFFFFFF if any intermediate widened.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n with bytes [B0, B1, B2, B3] (low to high)

Interactive diagram

Picking the right approach

extract B0

Active call / nodeSupporting contextReturned stateNot active

Bit-by-bit is the clean default; the byte cache wins when the function is hammered repeatedly.

Final resultrev(B0)<<24 | rev(B1)<<16 | rev(B2)<<8 | rev(B3)

C · Code with teaching comments

solution.javaJava

Byte Cache — Reverse and Reorder Bytes (Optimal for Repeated Calls) — optimal

3 teaching notes

1
private final int[] table = buildTable();
2
 
3
private int[] buildTable() {
4
    int[] t = new int[256];
5
    // Build the reversed-byte table ONCE — 256 possible byte values.
6
    for (int b = 0; b < 256; b++) {
7
        int rev = 0, x = b;
8
        for (int i = 0; i < 8; i++) {
9
            rev = (rev << 1) | (x & 1);
10
            x >>= 1;
11
        }
12
        t[b] = rev;
13
    }
14
    return t;
15
}
16
 
17
public int reverseBits(int n) {
18
    int result = 0;
19
    for (int i = 0; i < 4; i++) {
20
        // Unsigned shift + mask isolates byte i (0-255) even from a negative n.
21
        int b = (n >>> (8 * i)) & 0xFF;
22
        // Reversed byte i goes to mirrored byte position 3 - i.
23
        result |= table[b] << (8 * (3 - i));
24
    }
25
    return result;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(1) — 4 lookups/call timeO(256) spaceOpen the invariant and proofExplore the proof

Trading a fixed 256-entry table for a 8× reduction in per-call work is the classic precompute-and-lookup move. The same divide-into-bytes idea scales: reverse 16-bit halves with a 65536-entry table for even fewer lookups, trading more memory for less time.

ComplexityO(1) — 4 lookups/call time, O(256) space — After the one-time 256-entry table build, each call does 4 mask-lookup-shift operations — constant time. The table is fixed 256 entries → O(256) = O(1) space, amortised across all calls.

E · Edge cases and pitfalls5n = 0 — Every byte is 0, table[0] = 0 → result 0.Explore edge cases

Edge cases handled

n = 0Every byte is 0, table[0] = 0 → result 0.
n = 0xFFFFFFFFEach byte is 0xFF, table[0xFF] = 0xFF, reassembled to 0xFFFFFFFF. Masking keeps Python's result in range.

Pitfalls

Reversing the bytes but forgetting to swap their positions (or vice versa) — both transforms are required.
Rebuilding the 256-entry table inside reverseBits on every call — defeats the caching; build it once.
In Python, omitting `& 0xFFFFFFFF` on the result so a widened intermediate yields a value above 2³²−1.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewprivate final int[] table = buildTable(); private int[] buildTable() { int[] t = new int[256]; for (int b = 0; b < 256; b++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Signed shift corrupts negative inputs (Java)

`>>` copies the sign bit into the top, so the bits you read back are no longer the original 32-bit pattern. The reversal comes out wrong for any n with the top bit set.

Explore the code comparison

Don't write this

for (int i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>= 1;   // sign-extends: injects phantom 1s
}

Write this instead

for (int i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>>= 1;  // logical shift over the unsigned pattern
}

Stopping early when n becomes 0

Leading zeros of the input must become trailing zeros of the output, which means result still needs the remaining left-shifts. Exiting early leaves the set bits at the wrong positions.

Explore the code comparison

Don't write this

while n:                       # stops as soon as n's high bits are gone
    result = (result << 1) | (n & 1)
    n >>= 1
return result

Write this instead

for _ in range(32):            # always 32 iterations
    result = (result << 1) | (n & 1)
    n >>= 1
return result

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Bit-by-bit reversal (shift in, shift out)

Code pattern to memorize

result = 0
for _ in range(32):
    result = (result << 1) | (n & 1)  # append low bit of n
    n >>= 1                            # drop it (unsigned in Java)
return result

Rules to remember

1Mirror the two shifts: read the low bit of n (n & 1), write it to the low end of result (result << 1 | bit).
2Always loop exactly 32 times — leading zeros of the input become trailing zeros of the output and must be preserved.
3In Java use the unsigned shift n >>>= 1; >> sign-extends and corrupts the high bits of a negative input.
4In Python, mask intermediates with `& 0xFFFFFFFF` when you right-shift or you'll carry an ever-growing arbitrary-precision int; the bit-by-bit build stays in range naturally.
5Position i of the input maps to position 31 - i of the output — that symmetry is the whole problem.

Use this pattern when

Reverse / mirror the bit order of a fixed-width integer
Endian-style transforms or bit-level serialization
The function is called repeatedly → cache reversed bytes/nibbles
Any 'flip position i to position width-1-i' transformation

Choose another pattern when

You only need to count bits, not reorder them → Brian Kernighan (Number of 1 Bits)
Reversing the decimal digits, not the binary bits → that's an integer-math problem, not bitwise
The width isn't fixed → 'reverse 32 bits' assumes exactly 32; a variable width changes the loop bound
You want individual bit access, not a full mirror → mask the specific position

Interview takeaway

Reverse Bits is the canonical 'consume from one end, build at the other' bit loop. The trap isn't the algorithm — it's unsigned handling: Java needs `>>>`, Python needs `& 0xFFFFFFFF` on shifts. Get the masking right and the rest is a 32-step mirror.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBit-by-bit reversal (consume low, build low). Recognise it for any fixed-width bit-reordering task. The deeper lesson is unsigned discipline: Java needs >>>, Python needs & 0xFFFFFFFF — the same care Sum of Two Integers demands.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of 1 Bits
Same per-bit loop, but count set bits instead of repositioning them.
Reverse Integer
Coming soon
Reverse decimal digits, not bits — pop with % 10, push with * 10, watch for overflow.
Sum of Two Integers
Another fixed-width bit problem where Python needs & 0xFFFFFFFF masking to emulate 32-bit ints.
Counting Bits
Bit DP over a range — builds each answer from a right-shifted smaller number.

Same pattern

←

Counting Bits

Continue · Next problem

Missing Number

easyBit ManipulationLC #190Sometimes asked

Reverse Bits

LCPractice

Bit Manipulation · 4 of 20 · 7 min

Reverse the bits of a given 32-bit unsigned integer.

Follow-up: if this function is called many times, how would you optimize it?

In plain English

Examples

Example 1

Input: n = 43261596 (00000010100101000001111010011100)
Output: 964176192 (00111001011110000010100101000000)
Note: Reading the input right-to-left gives the output left-to-right — the bit string is mirrored.

Example 2

Input: n = 4294967293 (11111111111111111111111111111101)
Output: 3221225471 (10111111111111111111111111111111)
Note: Only bit 1 is 0; after reversal that 0 sits at position 30. All-ones-but-one flips to all-ones-but-one on the other side.

Example 3

Input: n = 1 (00000000000000000000000000000001)
Output: 2147483648 (10000000000000000000000000000000)
Note: The single set bit at position 0 moves to position 31. Demonstrates why all 32 iterations matter.

Constraints

The input is a 32-bit unsigned integer
In Java the value is given as a signed int (same bit pattern)
Output is the bit-reversed 32-bit value
Follow-up: optimize for many repeated calls (caching)

Clarifying questions4First question: Is the width fixed at 32 bits?Explore questions

Q1.Is the width fixed at 32 bits?
Yes. That matters because leading zeros must be reversed too — a 1 at position 0 must land at position 31 even if the higher bits are all zero.
Q2.How do I handle the lack of unsigned ints in Java?
Use the unsigned right shift `>>>` when consuming bits so the sign bit doesn't propagate. The 32-bit pattern is identical regardless of signedness.
Q3.In Python, won't the integer grow beyond 32 bits?
Python ints are arbitrary-precision. The bit-by-bit build naturally stays within 32 bits, but if I right-shift a wider value I mask with & 0xFFFFFFFF to stay in the 32-bit window.
Q4.Will this be called repeatedly?
The follow-up says yes. Then I'd precompute reversed bytes (256-entry table) and reverse the number by reversing and reordering its four bytes.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can manipulate bits at fixed positions and — critically — handle unsignedness correctly in a language without unsigned types (Java's signed int, Python's unbounded int).

Where candidates slip

How to stand out

Name the read-bit / write-bit symmetry, state that position i maps to 31 - i, handle unsigned correctly without prompting, and offer the byte-cache optimisation for the 'called many times' follow-up.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Bit-by-Bit — Shift In, Shift Out	`O(32) = O(1)`	`O(1)`	The clean default everyone should produce first. 'Pop the low bit of n, push it onto result, repeat 32 times.'	Read
2	Byte Cache — Reverse and Reorder Bytes (Optimal for Repeated Calls)Optimal	`O(1) — 4 lookups/call`	`O(256)`	The follow-up answer for 'called many times'. 'Precompute reversed bytes once; each call reverses 4 bytes and swaps their order.'	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Bit-by-Bit — Shift In, Shift Out

TimeO(32) = O(1)SpaceO(1)

The clean default everyone should produce first. 'Pop the low bit of n, push it onto result, repeat 32 times.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you read the input's bits from the lowest upward, and write them into the result from the lowest upward, what order does the result end up in?

2Hint 2Explore hint

Each step: take the lowest bit of n (n & 1), and append it to result by shifting result left and OR-ing the bit in.

3Hint 3Explore hint

Then shift n right (UNSIGNED in Java) to expose the next bit. Do this exactly 32 times so leading zeros are placed too.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 0b101 (only low 3 bits shown of 32)

Interactive diagram

First bit read becomes the top bit

step 1

Active call / nodeSupporting contextReturned stateNot active

Reading from n's low end and writing to result's low end mirrors the bit order.

Final result0b101 reversed within 32 bits → 1010...0 (bit that was at pos 0 is now at pos 31)

C · Code with teaching comments

Reference implementation previewpublic int reverseBits(int n) { int result = 0; for (int i = 0; i < 32; i++) { result = (result << 1) | (n & 1); n >>>= 1;Explore the full code

solution.javaJava

Bit-by-Bit — Shift In, Shift Out — reference

2 teaching notes

1
public int reverseBits(int n) {
2
    int result = 0;
3
    for (int i = 0; i < 32; i++) {
4
        // Open a low slot in result (<<1) and drop in n's current lowest bit (n & 1).
5
        result = (result << 1) | (n & 1);
6
        // UNSIGNED shift: expose the next bit without sign-extending. Plain >> would
7
        // inject 1s on a negative input.
8
        n >>>= 1;
9
    }
10
    return result;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(32) = O(1) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(32) = O(1) time, O(1) space — Exactly 32 iterations of constant-time bit ops regardless of input, so O(1) time. Only the result accumulator is stored — O(1) space.

E · Edge cases and pitfalls5n = 0 — Every bit read is 0; result stays 0 through all 32 shifts → returns 0.Explore edge cases

Edge cases handled

n = 0Every bit read is 0; result stays 0 through all 32 shifts → returns 0.
n = -1 (0xFFFFFFFF)All 32 bits are 1; with >>> each is read and re-placed → returns -1 (0xFFFFFFFF). With >> the loop would still read 1s but on a single sign-extended value.

Pitfalls

Using >> instead of >>> in Java — corrupts the high bits of a negative input.
Stopping the loop when n == 0 — drops leading zeros and leaves set bits at the wrong positions.
In Python, right-shifting a value wider than 32 bits without `& 0xFFFFFFFF` — lets the int grow unbounded.

03.2

Approach 2 of 2 · Optimal

Byte Cache — Reverse and Reorder Bytes (Optimal for Repeated Calls)

TimeO(1) — 4 lookups/callSpaceO(256)

The follow-up answer for 'called many times'. 'Precompute reversed bytes once; each call reverses 4 bytes and swaps their order.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you'll reverse millions of numbers, what work can you do ONCE and reuse? A 32-bit int is just 4 bytes.

2Hint 2Explore hint

Reversing the whole number = reverse each of the 4 bytes individually, then put the bytes in the opposite order (byte 0 ↔ byte 3, byte 1 ↔ byte 2).

3Hint 3Explore hint

Precompute a 256-entry table of reversed bytes. Per call: split n into 4 bytes, look up each reversed byte, and shift it to its mirrored byte position.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n with bytes [B0, B1, B2, B3] (low to high)

Interactive diagram

Picking the right approach

extract B0

Active call / nodeSupporting contextReturned stateNot active

Bit-by-bit is the clean default; the byte cache wins when the function is hammered repeatedly.

Final resultrev(B0)<<24 | rev(B1)<<16 | rev(B2)<<8 | rev(B3)

C · Code with teaching comments

solution.javaJava

Byte Cache — Reverse and Reorder Bytes (Optimal for Repeated Calls) — optimal

3 teaching notes

1
private final int[] table = buildTable();
2
 
3
private int[] buildTable() {
4
    int[] t = new int[256];
5
    // Build the reversed-byte table ONCE — 256 possible byte values.
6
    for (int b = 0; b < 256; b++) {
7
        int rev = 0, x = b;
8
        for (int i = 0; i < 8; i++) {
9
            rev = (rev << 1) | (x & 1);
10
            x >>= 1;
11
        }
12
        t[b] = rev;
13
    }
14
    return t;
15
}
16
 
17
public int reverseBits(int n) {
18
    int result = 0;
19
    for (int i = 0; i < 4; i++) {
20
        // Unsigned shift + mask isolates byte i (0-255) even from a negative n.
21
        int b = (n >>> (8 * i)) & 0xFF;
22
        // Reversed byte i goes to mirrored byte position 3 - i.
23
        result |= table[b] << (8 * (3 - i));
24
    }
25
    return result;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(1) — 4 lookups/call timeO(256) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5n = 0 — Every byte is 0, table[0] = 0 → result 0.Explore edge cases

Edge cases handled

n = 0Every byte is 0, table[0] = 0 → result 0.
n = 0xFFFFFFFFEach byte is 0xFF, table[0xFF] = 0xFF, reassembled to 0xFFFFFFFF. Masking keeps Python's result in range.

Pitfalls

Reversing the bytes but forgetting to swap their positions (or vice versa) — both transforms are required.
Rebuilding the 256-entry table inside reverseBits on every call — defeats the caching; build it once.
In Python, omitting `& 0xFFFFFFFF` on the result so a widened intermediate yields a value above 2³²−1.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewprivate final int[] table = buildTable(); private int[] buildTable() { int[] t = new int[256]; for (int b = 0; b < 256; b++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Signed shift corrupts negative inputs (Java)

`>>` copies the sign bit into the top, so the bits you read back are no longer the original 32-bit pattern. The reversal comes out wrong for any n with the top bit set.

Explore the code comparison

Don't write this

for (int i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>= 1;   // sign-extends: injects phantom 1s
}

Write this instead

for (int i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>>= 1;  // logical shift over the unsigned pattern
}

Stopping early when n becomes 0

Leading zeros of the input must become trailing zeros of the output, which means result still needs the remaining left-shifts. Exiting early leaves the set bits at the wrong positions.

Explore the code comparison

Don't write this

while n:                       # stops as soon as n's high bits are gone
    result = (result << 1) | (n & 1)
    n >>= 1
return result

Write this instead

for _ in range(32):            # always 32 iterations
    result = (result << 1) | (n & 1)
    n >>= 1
return result

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Bit-by-bit reversal (shift in, shift out)

Code pattern to memorize

result = 0
for _ in range(32):
    result = (result << 1) | (n & 1)  # append low bit of n
    n >>= 1                            # drop it (unsigned in Java)
return result

Rules to remember

1Mirror the two shifts: read the low bit of n (n & 1), write it to the low end of result (result << 1 | bit).
2Always loop exactly 32 times — leading zeros of the input become trailing zeros of the output and must be preserved.
3In Java use the unsigned shift n >>>= 1; >> sign-extends and corrupts the high bits of a negative input.
4In Python, mask intermediates with `& 0xFFFFFFFF` when you right-shift or you'll carry an ever-growing arbitrary-precision int; the bit-by-bit build stays in range naturally.
5Position i of the input maps to position 31 - i of the output — that symmetry is the whole problem.

Use this pattern when

Reverse / mirror the bit order of a fixed-width integer
Endian-style transforms or bit-level serialization
The function is called repeatedly → cache reversed bytes/nibbles
Any 'flip position i to position width-1-i' transformation

Choose another pattern when

You only need to count bits, not reorder them → Brian Kernighan (Number of 1 Bits)
Reversing the decimal digits, not the binary bits → that's an integer-math problem, not bitwise
The width isn't fixed → 'reverse 32 bits' assumes exactly 32; a variable width changes the loop bound
You want individual bit access, not a full mirror → mask the specific position

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of 1 Bits
Same per-bit loop, but count set bits instead of repositioning them.
Reverse Integer
Coming soon
Reverse decimal digits, not bits — pop with % 10, push with * 10, watch for overflow.
Sum of Two Integers
Another fixed-width bit problem where Python needs & 0xFFFFFFFF masking to emulate 32-bit ints.
Counting Bits
Bit DP over a range — builds each answer from a right-shifted smaller number.

Same pattern

←

Counting Bits

Continue · Next problem

Missing Number