Problem Statement

Reverse the bits of a given 32-bit unsigned integer.

Example 1:

Input: n = 00000010100101000001111010011100
Output:    964176192
Explanation: The binary representation of 964176192 is 00111001011110000010100101000000

Example 2:

Input: n = 11111111111111111111111111111101
Output:   3221225471
Explanation: The binary representation of 3221225471 is 10111111111111111111111111111111

Constraints:

• The input must be treated as a 32-bit unsigned integer.

---

Intuition

The task is to reverse the binary digits of a 32-bit number.

For example:

If the input binary is:

00000010100101000001111010011100

then the output should be:

00111001011110000010100101000000

That means we need to:

1. Take the last bit of n (using n & 1).
2. Append it to the reversed result (shift result left by 1 and add this bit).
3. Shift n right by 1 to process the next bit.
4. Repeat this process 32 times.

---

Step-by-Step Approach

1. Initialize result = 0.
2. For each bit position i from 0 to 31:
   • Extract the last bit using n & 1.
   • Shift the result left by 1 to make space.
   • Add the extracted bit to result.
   • Shift n right by 1 to move to the next bit.
3. Return result.

This way, bits from the right of n are inserted from the left into result.

---

Java Solution

public class Solution {
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1); // Append the last bit of n to result
            n = n >>> 1; // Unsigned right shift by 1
        }
        return result;
    }
}

---

Explanation of Key Operations

• n & 1 → extracts the last bit.
• result << 1 → makes room for the next bit in result.
• | (bitwise OR) → adds the extracted bit.
• n >>> 1 → shifts bits right (unsigned), filling left with 0.

Unsigned right shift (>>>) is crucial here, because Java’s int is signed, and >> would preserve the sign bit — which we don’t want.

---

Complexity Analysis

• Time Complexity: O(32) = O(1)
  The loop always runs for 32 bits.
• Space Complexity: O(1)
  Uses only a few integer variables.

---

Dry Run

Let’s take a smaller 8-bit example for clarity (actual is 32-bit):

Input: n = 00000101 (decimal 5)

Step	n (binary)	Extracted bit (n & 1)	result (before shift)	result (after update)	n after shift
1	00000101	1	00000000	00000001	00000010
2	00000010	0	00000001	00000010	00000001
3	00000001	1	00000010	00000101	00000000
4–8	00000000	0	00000101	00001010 → 00010100 → …	00000000

After completing 8 iterations:
result = 10100000 (binary) = 160 (decimal)

So, reversing 00000101 gives 10100000.

For 32-bit inputs, the same logic applies — just iterated 32 times.

---

Alternative Approach: Bit Manipulation with Masks (Advanced)

We can reverse bits in O(1) time using bitwise masks and shifts:

public class Solution {
    public int reverseBits(int n) {
        n = (n >>> 16) | (n << 16);
        n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
        n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
        return n;
    }
}

This version flips bits in chunks (16, 8, 4, 2, 1) — often used in performance-critical systems.

---

Key Takeaways

1. The problem is purely bit manipulation.
2. Use >>> for unsigned shifts (not >>).
3. You can reverse bits either:
   • Iteratively in 32 steps, or
   • Using masks and precomputed patterns.
4. The iterative version is simple and works efficiently for all inputs.