Reverse Bits (LC 190)

Pattern: Bit Manipulation
Difficulty: Easy
Key Concept: For each bit of n, shift the answer left and merge the next bit from n—you walk n from LSB to MSB while building the reversed word.

Problem Statement

Reverse bits of a given 32-bit unsigned integer.

Input

• n: int whose bits are interpreted as an unsigned 32-bit value

Output

• int — the integer whose binary representation is the reverse of the input’s bits (as unsigned 32-bit)

Note: In Java, return type is int; treat the value as unsigned for the problem’s meaning (LeetCode shows unsigned examples).

Example

• Input (binary) 00000010100101000001111010011100
• Output (binary) 00111001011110000010100101000000

---

1. Algorithm & Pseudocode

Brute force

Convert to a char array of 32 bits (or String), reverse, parse back — heavy allocation.

bits = extract each of 32 bits into list
reverse list
recombine into integer

Optimal

Build result bit by bit:

result = 0
for i from 0 to 31:
    result <<= 1
    result |= (n & 1)
    n >>>= 1
return result

Use >>> so n shifts in zeros from the left (unsigned shift), preserving the “unsigned” story.

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why shift result left first You are constructing the answer from the first picked bit (LSB of original) as the future MSB of the answer—each new bit you grab becomes the next more significant bit of result, so you make room with <<= 1.

2. Why (n & 1) That isolates the current least significant bit of n before you discard it.

3. Why n >>>= 1 Next iteration should look at the next bit toward the MSB. Unsigned right shift fills with zeros on the left, matching 32-bit unsigned semantics.

4. Why not StringBuilder + reverse It works but allocates and is slower; the bit loop is O(1) time (32 steps) and O(1) space.

---

3. The Dry Run

Sample (toy 4-bit version for table): n = 1101 (binary) → reverse → 1011.
(Problem is 32-bit; same logic.)

| Step | n (low bits shown) | n & 1 | result after << then | | |:—:|:—:|:—:|:—:| | init | 1101 | — | 0000 | | 1 | 1101 | 1 | 0001 | | 2 | 0110 | 0 | 0010 | | 3 | 0011 | 1 | 0101 | | 4 | 0001 | 1 | 1011 |

ASCII: bits marching

n (LSB first grab):  1  0  1  1  -> builds result leftward
result growth:       1 -> 10 -> 101 -> 1011

---

4. Java Solution

Brute Force

public class Solution {
    public int reverseBits(int n) {
        char[] bits = new char[32];
        for (int i = 0; i < 32; i++) {
            bits[i] = ((n >> i) & 1) == 1 ? '1' : '0';
        }
        // bits[i] is i-th bit from LSB; reverse string interpretation:
        // MSB of answer is bits[0], next is bits[1], ...
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result <<= 1;
            result |= (bits[i] - '0');
        }
        return result;
    }
}

Time: O(1) — 32 steps.
Space: O(1) — fixed char[32].

Optimal

public class Solution {
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result <<= 1;
            result |= (n & 1);
            n >>>= 1;
        }
        return result;
    }
}

Time: O(1).
Space: O(1).

---

5. The “Java vs. Others” Edge

• >>> is the star Java does not have unsigned int; >>> on int performs logical right shift—essential when treating the word as unsigned while shifting.
• >> would sign-extend For positive-looking high bit patterns, wrong shift can stick 1s on the left and break the reversal.
• C++ Uses uint32_t and ordinary >> on unsigned type = logical shift—Java needs >>> explicitly on int.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute (array of bits)	O(1)	O(1)	32 chars; more moving parts.
Optimal (shift loop)	O(1)	O(1)	32 iterations; use >>>.