Reverse Bits

Problem in Plain English

Reverse the order of all 32 bits of an unsigned integer, turning the leftmost bit into the rightmost and vice versa. The mirrored bit string is returned as the unsigned integer it represents.

Problem Statement

Reverse the bits of a given 32-bit unsigned integer n. Every one of the 32 positions moves to its mirror image, so the leftmost bit becomes the rightmost and the rightmost becomes the leftmost, including leading zeros.

In languages without an unsigned type such as Java, the input and output travel as signed int values. The underlying bit pattern is identical either way, so the reversal works on the raw 32 bits and the result is interpreted as unsigned.

Constraints

$0 \le n \le 2^{32}-1$ , a full 32-bit unsigned value.
All 32 bit positions are reversed, including leading zeros.
The reversed value also fits in 32 unsigned bits.

Examples

Example 1

Input: n = 00000010100101000001111010011100
Output: 964176192

The input bits represent 43261596. Mirroring all 32 positions gives 00111001011110000010100101000000, which represents 964176192.

Example 2

Input: n = 11111111111111111111111111111101
Output: 3221225471

The input bits represent 4294967293. The mirrored string is 10111111111111111111111111111111, which represents 3221225471.

Example 3

Input: n = 0
Output: 0

All 32 positions contain zero, so reflecting their positions still produces 32 zeros.

Example 4

Input: n = 1
Output: 2147483648

The only set bit moves from position 0 to position 31. The result is unsigned 2147483648; Java carries that same pattern as signed int -2147483648.

Intuition

Reversal changes positions, not bit values: input position 0 must reach output position 31, and position 31 must reach position 0. For 43261596, keep the six leading zeros as part of the 32-bit input; they become six trailing zeros in 964176192. Either reverse a padded string or read the lowest bit repeatedly while shifting the answer left. The width is fixed even when the remaining input becomes zero.

Approaches

String Conversion

Solution Details

Reveal String Conversion: intuition, complexity, and code

Intuition

Treat the number as a 32-character string, mirror the characters, and parse the result back to an integer. String mirroring is easy to get right but pays for padding and parsing instead of touching bits directly.

Step-by-Step Logic

Convert n = 43261596 to binary, giving 10100101000001111010011100.
Pad on the left with zeros to reach exactly 32 characters: 00000010100101000001111010011100.
Reverse the character order to 00111001011110000010100101000000.
Parse the mirrored string as base 2, which yields 964176192.
Return 964176192.

Why It Works

A padded binary representation contains exactly one character for each of the 32 input positions. Reversing it maps character index i to index 31 - i without changing any character. Parsing base 2 assigns each character its new positional weight, which is exactly the required bit reversal. Padding first prevents leading zeros from disappearing before they can become trailing zeros.

Dry Run

String Conversion: variable states at each step
Stage	Characters / value	Width	Reason
Binary conversion	10100101000001111010011100	26	leading zero positions are omitted
Pad left	00000010100101000001111010011100	32	restore six zero positions
Reverse characters	00111001011110000010100101000000	32	each position maps to its mirror
Unsigned base-2 parse	964176192	32 bits	return Example 1 output

Complexity Analysis

Time Complexity

O(1)

Space Complexity

O(1)

At fixed width 32, conversion, padding, reversal and parsing all do bounded work and allocate bounded storage, hence O(1) time and auxiliary space. For a generalized width w, each is O(w); strings/builders and the JavaScript character array allocate O(w) total storage. The constant-space label here does not mean allocation-free.

Code

Solution.java

1public class Solution {2    // toBinaryString exposes all 32 raw bits even when Java n is negative.3    public int reverseBits(int n) {4        String bits = Integer.toBinaryString(n);5        StringBuilder padded = new StringBuilder();6        for (int i = bits.length(); i < 32; i++) {7            padded.append('0');8        }9        padded.append(bits);10        String reversed = padded.reverse().toString();11        // Unsigned parsing preserves patterns whose top bit is set.12        return Integer.parseUnsignedInt(reversed, 2);13    }14}

Hints

Hint 1

Read the input from the rightmost bit inward: n & 1 exposes the current lowest bit.

Hint 2

Grow the answer from the left by shifting it one place before attaching each exposed bit with |.

Hint 3

Move to the next input bit with an unsigned right shift, and repeat the expose-shift-attach cycle exactly 32 times.

Edge Cases

Input 0 runs all 32 rounds and returns 0 instead of stopping early.
Input 4294967295 with all bits set mirrors to itself and must return 4294967295.
In Java the reversed bits may set the sign bit, so the result must be read back as unsigned.

Common Mistakes and Interview Tips

Using a signed right shift obscures the unsigned stream invariant and is unsafe for variants that stop when n is zero. With exactly 32 rounds, even an arithmetic shift exposes the original 32 low bits, but unsigned shift expresses the intended contract.
Breaking out when n reaches 0, which drops the leading zeros that still need mirroring.
Returning a signed 32-bit value in JavaScript without >>> 0, which can print a negative number.
Interview follow-up: repeated queries can reuse a lookup table of reversed bytes, but that changes the preprocessing and storage tradeoff; the published loop requires no table.

Key Takeaway

Reading bits lowest-first with n & 1 plus an unsigned right shift turns any fixed-width integer into a stream you can rebuild in a new order.