Reverse Bits

Problem Description

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

Examples

Constraints

• The input must be a binary string of length 32.

Shifting Input and Output Bits in Opposite Directions

To reverse a 32-bit integer, we must read the bits from right to left, and write them into our output from left to right.

We can achieve this by iterating 32 times:

• Initialize our output variable result = 0.
• In each step, shift the output left by one bit: result = result << 1. This makes room for the next bit.
• Read the least significant bit of our input using a bitwise AND mask: bit = n & 1.
• Add this bit to the output using bitwise OR: result = result | bit.
• Shift the input right by one bit: n = n >> 1 (using logical shift to avoid sign replication).

This process reverses the order of the bits in exactly 32 steps.

Solution 1: 32-Bit Bitwise Shifting (Optimal)

Iterate 32 times, shifting the input right and OR-ing its last bit into the left-shifted output.

public class Solution {
    // treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n = n >>> 1; // logical right shift to prevent sign propagation
        }
        return result;
    }
}

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for _ in range(32):
            # shift result left and merge the last bit of n
            result = (result << 1) | (n & 1)
            n = n >> 1
        return result

#include <cstdint>

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

Complexity Analysis:

• Time Complexity: O(1). The loop always runs exactly 32 times.
• Space Complexity: O(1) auxiliary space.

Where it breaks: In Java, integers are signed, so the last bit shift on index 31 updates the sign bit. The result represents the correct reversed bits, but when printed as a signed integer, it may display as a negative decimal number, which is correct according to the LeetCode compiler expectations.

Common Mistakes

• Using arithmetic shift >> in Java instead of logical shift >>>. Using >> on negative integers will duplicate 1s on the left, preventing the input from reaching 0 and corrupting the bit count.
• Running the loop until n == 0 instead of exactly 32 times. If n = 1, running the loop until n == 0 will exit after 1 step, yielding result = 1 instead of 2³¹ (reversing 00...01 must yield 10...00). The loop must run exactly 32 times to handle leading/trailing zero padding.
• Incorrect operator precedence. Write (result << 1) | (n & 1) with parentheses to prevent operators from executing in the wrong order.

Frequently Asked Questions

Why must the loop run exactly 32 times instead of terminating when n is 0? Because a 32-bit reversal must pad the output with zeros. If the input is 1 (00...001), the reversed output must be 2³¹ (100...00). If you stop early, the output will remain 1, which is incorrect.

Is there a way to solve this in O(1) without loops? Yes. You can use divide and conquer to reverse bits in blocks: swap adjacent bits, then swap adjacent 2-bit blocks, then 4-bit blocks, then 8-bit, then 16-bit blocks. This uses precompute masks and runs in 5 lines of bitwise equations, which is highly efficient but hard to write from memory.

What does this problem test in interviews? It tests your understanding of bitwise shift directions, logical vs arithmetic right shifts, and the importance of loop constraints on fixed-width integers.

← All Problems