147.Reverse Bits

Intuition

Turn the number into its 32-character binary string (padding with leading zeros), reverse the string, and parse it back as an unsigned base-2 number.

Algorithm

1. s = Integer.toBinaryString(n), left-padded with '0' to length 32.
2. Reverse s.
3. Return Integer.parseUnsignedInt(reversed, 2) (handles results with the top bit set).

Visualization

n = 43261596
padded  : 00000010100101000001111010011100
reversed: 00111001011110000010100101000000 → 964176192

Code

class Solution {
    public int reverseBits(int n) {
        String bits = Integer.toBinaryString(n);
        // pad with leading zeros so all 32 positions are reversed
        String padded = "0".repeat(32 - bits.length()) + bits;
        String reversed = new StringBuilder(padded).reverse().toString();
        // parseUnsignedInt accepts values up to 2^32 - 1 (top bit set → negative int)
        return Integer.parseUnsignedInt(reversed, 2);
    }
}

Complexity

• Time: O(32) = O(1), but with string allocation and parsing overhead.
• Space: O(32) = O(1) for the strings.

Intuition

Read n from its least significant bit upward, and build result by shifting it left and appending each bit. After 32 steps, the bit that was read first (bit 0) has been shifted all the way to bit 31.

Algorithm

1. result = 0.
2. Repeat 32 times:
   • result = (result << 1) | (n & 1) — append n's lowest bit.
   • n >>>= 1 — move to the next bit.
3. Return result.

Dry Run (8-bit illustration)

n = 1011 0010, result = 0000 0000
step 1: bit 0 → result = 0000 0000   n = 0101 1001
step 2: bit 1 → result = 0000 0001   n = 0010 1100
step 3: bit 0 → result = 0000 0010   n = 0001 0110
step 4: bit 0 → result = 0000 0100   n = 0000 1011
step 5: bit 1 → result = 0000 1001   n = 0000 0101
step 6: bit 1 → result = 0001 0011   n = 0000 0010
step 7: bit 0 → result = 0010 0110   n = 0000 0001
step 8: bit 1 → result = 0100 1101   → reversed!

Code

class Solution {
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1); // append n's lowest bit
            n >>>= 1;                         // unsigned shift to the next bit
        }
        return result;
    }
}

Complexity

• Time: O(32) = O(1) — exactly 32 iterations.
• Space: O(1).

Intuition

Reversing a sequence equals reversing the order of its two halves and then reversing each half. Apply that recursively, but on all groups in parallel using masks:

1. Swap the 16-bit halves.
2. Swap adjacent 8-bit bytes (mask 0xff00ff00 / 0x00ff00ff).
3. Swap adjacent 4-bit nibbles (0xf0f0f0f0 / 0x0f0f0f0f).
4. Swap adjacent 2-bit pairs (0xcccccccc / 0x33333333).
5. Swap adjacent single bits (0xaaaaaaaa / 0x55555555).

Each step keeps the "high" group, shifts it right, keeps the "low" group, shifts it left, and ORs them. Five steps instead of 32 — which is the answer to the follow-up (alternatively, cache the reversal of each byte in a 256-entry table).

Algorithm

1. n = (n >>> 16) | (n << 16).
2. For each (mask, shift) in (0xff00ff00, 8), (0xf0f0f0f0, 4), (0xcccccccc, 2), (0xaaaaaaaa, 1): n = ((n & mask) >>> shift) | ((n & ~mask) << shift).
3. Return n.

Dry Run

The same idea on 8 bits (three swap levels instead of five):

Code

class Solution {
    public int reverseBits(int n) {
        n = (n >>> 16) | (n << 16);                                // swap 16-bit halves
        n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);   // swap bytes
        n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);   // swap nibbles
        n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);   // swap bit pairs
        n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);   // swap single bits
        return n;
    }
}

Complexity

• Time: O(1) — five constant mask/shift steps (this is what Integer.reverse does internally).
• Space: O(1).