Reverse Bits

EasyBit Manipulation🧩 Bit Manipulation LeetCode #190 ↗Updated Oct 30, 2026

Problem

You get a number n viewed as a pattern of exactly 32 bits. Return the number whose bit pattern is that sequence read backwards: bit 0 swaps with bit 31, bit 1 with bit 30, and so on. Leading zeros count, so a small input can become a huge output. (Java has no unsigned int, so the bits are simply carried in an int.)

Inputn = 43261596 (00000010100101000001111010011100)Output964176192 (00111001011110000010100101000000)

Inputn = 2147483644 (0111...11100)Output1073741822 (00111...1110)

Inputn = 1Output-2147483648 (only bit 31 set)

Input is any 32-bit pattern · Follow-up: if the function is called many times, how would you make it faster?

Try it yourself

Java

class Solution {
    public int reverseBits(int n) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Reversing 32 bits is the same as swapping the two 16-bit halves, then the bytes inside each half, then the nibbles, pairs and single bits — 5 masked swaps instead of 32 single-bit moves.

PatternBit Manipulation

Instinct Pairs that cancel, counting 1s, powers of two, subsets as numbers, or 'no + or - allowed' - drop to binary and use XOR, AND, OR and shifts.

Memory hack XOR is a forgetful twin detector - see something twice and it vanishes; n & (n-1) snips off the last lit bulb.

Open the Bit Manipulation guide →

Approaches

Brute ForceBinary String, Reverse, Parse

Time O(32)Space O(32)

Write n as a binary string, left-pad it to 32 characters so leading zeros are not lost, reverse the string and parse it back. Parsing goes through a long because a pattern starting with 1 overflows Integer.parseInt.

Java

public int reverseBits(int n) {
    String bits = String.format("%32s", Integer.toBinaryString(n)).replace(' ', '0');
    String reversed = new StringBuilder(bits).reverse().toString();
    return (int) Long.parseLong(reversed, 2); // long: top bit may be 1
}

Correct and readable, but allocates strings and ignores how bits actually work.

BetterShift Bits One at a Time

Time O(32)Space O(1)

Peel the lowest bit off n and push it onto the low end of result, 32 times. The first bit peeled ends up shifted 31 places left, which is exactly the mirror position. Use >>> so the sign bit is not copied in.

Java

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1); // append the lowest bit of n
        n >>>= 1;                         // unsigned shift
    }
    return result;
}

No allocation, constant space — the standard interview answer.

OptimalDivide & Conquer Mask Swaps

Time O(1) — 5 stepsSpace O(1)

Swap halves, then swap neighbouring blocks of 8, 4, 2 and 1 bits using masks that select the left or right block of every pair. After swapping at every scale, each bit has moved to its mirror position. This is log₂(32) = 5 rounds with no loop.

Java

public int reverseBits(int n) {
    n = (n >>> 16) | (n << 16);                               // swap 16-bit halves
    n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);   // swap bytes
    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 single bits
    return n;
}

Branch-free and loop-free — answers the “called many times” follow-up.

Pro tip

Another follow-up answer: cache the reversal of all 256 bytes, then reverse a word as 4 table lookups. Integer.reverse uses the mask-swap idea.

At a glance

Level	Approach	Time	Space
Brute Force	Binary String, Reverse, Parse	`O(32)`	`O(32)`
Better	Shift Bits One at a Time	`O(32)`	`O(1)`
Optimal	Divide & Conquer Mask Swaps	`O(1) — 5 steps`	`O(1)`

Common pitfalls

Using >> instead of >>> — negative inputs keep refilling with 1s.
Stopping when n == 0 — the remaining zero bits still have to shift result left.
Forgetting to pad the binary string to 32 chars, which drops leading zeros.

Interview tips

Clarify that the input is a 32-bit pattern and that Java returns it in a signed int.
Write the shift loop first, then raise the follow-up and show the mask swaps or a byte table.
Check 1 → Integer.MIN_VALUE and -1 → -1 out loud.

Pattern

Bit-by-bit shifting / masked swaps → reorder, count or mirror the bits of a fixed-width integer.

My notes saved in this browser