Blind 75Easy

Reverse Bits — Bitwise Swapping

Swap symmetric bit pairs by shifting and masking until you have reversed the 32-bit integer.

Bit Manipulation

View problem on LeetCode

Problem Statement

Reverse the bits of a 32-bit unsigned integer.

Why This Problem Matters

Bit twiddling questions expose your comfort with low-level operations.
Serves as a gateway to more complex bit hacks like reversing bytes.
Encourages thinking about loop iterations and constant-time masks.

Thought Process

Iterate over all 32 bits

Shift the result left and append the least significant bit of the input each iteration.

Use bitwise AND to extract LSB

n & 1 yields the current least significant bit; shift input right afterwards.

Keep unsigned semantics in mind

Use unsigned shift >>> in Java so sign bits do not propagate.

Step-by-Step Reasoning

Initialise result = 0.
Repeat 32 times: shift result left by 1, add (n & 1), then unsigned shift n right.
Return result.

Dry Run

n = 00000010100101000001111010011100₂

After 32 iterations, result equals 00111001011110000010100101000000₂.

n = 11111111111111111111111111111101₂

Result becomes 10111111111111111111111111111111₂.

Complexity Analysis

Time

O(1)

Space

O(1)

Why

Always loops 32 times with constant extra space.

Annotated Solution

JAVA

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

The loop shifts result left and appends each bit from least to most significant, effectively reversing the order.

Common Pitfalls

Using arithmetic shift >> instead of unsigned >>> reintroduces sign bits for negative numbers.
Looping until n becomes zero fails when leading zeros need to be processed.
Forgetting to mask with & 1 results in incorrect appended bits.

Follow-Up Questions

Can you precompute reversed bytes to speed up repeated calls?
How would you generalise to 64-bit values?

Key Takeaways

Unsigned shifts matter whenever sign bits could corrupt the result.

Bit manipulation tasks often rely on simple loops with masking.

Precomputation can optimise repeated bit reversal calls.