154. Reverse Bits

Pull the bits out of the input one at a time from the least-significant end, and push each one onto the low end of a growing result. Because the result is shifted left on every step, the first bit you extract ends up in the highest position — which is exactly what reversing means.

Idea

Reversing bits means bit i of the input must become bit 31 - i of the output. Instead of computing that index math directly, we build the answer incrementally so the indices take care of themselves.

Keep a result that starts at 0. On each of 32 iterations, do two things in order:

1. Shift result left by one — this opens up a fresh 0 in the lowest bit position and pushes everything already collected one slot higher.
2. Copy in the next input bit — take bit i of n (via (n >> i) & 1) and OR it into that lowest slot.

The bit you read on iteration 0 (the input's LSB) gets shifted left 31 more times, so it lands in bit 31 — the top. The bit you read on iteration 31 (the input's MSB) is added last and stays in bit 0. Every bit ends up mirrored.

Algorithm

1. result = 0.
2. For i from 0 to 31:
   • result = result << 1 — make room in the low bit.
   • result = result | ((n >> i) & 1) — drop in input bit i.
3. Return result.

Worked example: n = 43261596

In binary that is 00000010100101000001111010011100. We walk the input from its lowest bit upward while result grows from the top down. Tracing the first few steps:

After all 32 iterations the accumulated bits spell 00111001011110000010100101000000, which is 964176192 — the input read back to front.

Complexity

• Time: O(32) = O(1) — a fixed 32 iterations regardless of the value.
• Space: O(1) — only the result accumulator.

class Solution {
    // Returns a long so the reversed 32-bit value is printed unsigned. A Java
    // int would render results with bit 31 set as a negative number, diverging
    // from the unsigned answer the problem expects.
    public long reverseBits(int n) {
        long result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | ((n >> i) & 1L);
        }
        return result;
    }
}