#190 Reverse Bits

frequently reported atNVIDIA Airbnb Apple Amazon Microsoft

the problem

In plain words

Reverse the bits of a given 32-bit signed integer: bit 0 becomes bit 31, bit 1 becomes bit 30, and so on. In Java the input and output are plain ints holding the 32-bit pattern.

in n = 43261596 (00000010100101000001111010011100)

out 964176192 (00111001011110000010100101000000)

in n = 2147483644 (01111111111111111111111111111100)

out 1073741822 (00111111111111111111111111111110)

0 ≤ n ≤ 2³¹ − 2 and n is even (current version)
Older versions passed any 32-bit unsigned pattern; the code below handles negative ints too

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBit tricks (shift, mask, lowest set bit)

Treat n as a stack of bits. Pop its last bit (n & 1, then n >>>= 1) and push it onto the right of result (result << 1 | bit), 32 times.

solutions

From brute force to optimal

Make a 32-character string, reverse it, parse it back as unsigned.

Pad toBinaryString to 32 chars.
Reverse with StringBuilder.
Integer.parseUnsignedInt(s, 2).

timeO(32) = O(1)

Fixed length, but it allocates strings.

spaceO(32) = O(1)

Two temporary 32-char strings.

java

1class Solution {2    public int reverseBits(int n) {3        String bits = String.format("%32s", Integer.toBinaryString(n)).replace(' ', '0');4        String reversed = new StringBuilder(bits).reverse().toString();5        return Integer.parseUnsignedInt(reversed, 2); // plain parseInt overflows on a leading 16    }7}

Shift result left, OR in n's last bit, shift n right with >>>.

result = 0.
Repeat 32 times: result = (result << 1) | (n & 1); n >>>= 1.
Return result.

timeO(32) = O(1)

Exactly 32 iterations of O(1) work.

spaceO(1)

Two ints.

java

1class Solution {2    public int reverseBits(int n) {3        int result = 0;4        for (int i = 0; i < 32; i++) {5            result = (result << 1) | (n & 1); // append n's last bit to result6            n >>>= 1; // >>> so the sign bit never leaks back in7        }8        return result;9    }10}

sim

Dry run

loading simulation…

java

1class Solution {2    public int reverseBits(int n) {3        int result = 0;4        for (int i = 0; i < 32; i++) {5            result = (result << 1) | (n & 1); // append n's last bit to result6            n >>>= 1; // >>> so the sign bit never leaks back in7        }8        return result;9    }10}

The JDK swaps adjacent bits, then pairs, then nibbles, using masks. That is 5 steps instead of 32.

Return Integer.reverse(n).

timeO(1)

log₂32 = 5 mask-and-shift rounds.

spaceO(1)

Nothing stored.

java

1class Solution {2    public int reverseBits(int n) {3        return Integer.reverse(n); // swaps halves, quarters, ... with masks: O(1)4    }5}

in the room

How to say it in the interview

talk track

Say why the loop must run exactly 32 times. Leading zeros of n become trailing zeros of the result, and they still count.

traps

Stopping when n becomes 0. That loses the zeros that should shift result further left.
Using >> on n, which drags the sign bit in.

what they ask next

Follow-ups

Called many times?

Cache the reversal of each byte (256 entries). Then reverse 4 bytes and put them in the opposite order.

before you submit

Edge cases to test

n = 0 → 0.
Leading zeros count: n = 2 → 2³⁰ = 1,073,741,824.
A 1 in bit 0 lands in the sign bit, so the Java answer can be negative.

practise next