190. Reverse Bits

EasyBit ManipulationDivide and Conquer

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a 32-bit signed integer n. Your task is to reverse all the bits in this integer and return the resulting value.

When reversing bits, the bit at position 0 (rightmost/least significant bit) should move to position 31 (leftmost/most significant bit), the bit at position 1 should move to position 30, and so on. Each bit maintains its value (0 or 1) but changes its position to create a mirror image of the original bit pattern.

For example, if you have the binary representation 00000010100101000001111010011100, after reversing the bits, you would get 00111001011110000010100101000000.

The solution works by iterating through all 32 bits of the input number. For each iteration i:

Extract the least significant bit of n using (n & 1)
Place this bit at position (31 - i) in the result using left shift: (n & 1) << (31 - i)
Combine it with the result using the OR operation: ans |= (n & 1) << (31 - i)
Right shift n by 1 to process the next bit: n >>= 1

This process continues for all 32 bits, effectively reversing the entire bit sequence of the input integer.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Math / Bit Manipulation?

This problem maps to Math / Bit Manipulation through a short path in the full flowchart.

Iterate 32 times, shift the result left, OR in the lowest bit of n, then shift n right to move bit i into position 31-i.

Open in Flowchart

Intuition

To reverse the bits of a number, we need to swap the positions of bits symmetrically around the center. The bit at position 0 should go to position 31, the bit at position 1 should go to position 30, and so on.

Think of it like reversing a string - you would take characters from one end and place them at the opposite end. Similarly, with bits, we need to take each bit from its current position and place it at its mirror position.

The key insight is that we can process the bits one by one from right to left (least significant to most significant). As we examine each bit:

We need to extract it from its current position
We need to place it at its new reversed position

To extract the rightmost bit, we use n & 1, which gives us the value (0 or 1) of the least significant bit.

To place this bit at its reversed position, we need to shift it left. If we're processing the i-th bit (counting from 0), its reversed position would be 31 - i. So we shift the extracted bit left by 31 - i positions using << (31 - i).

After processing each bit, we shift n right by 1 position (n >>= 1) to bring the next bit into the least significant position for processing in the next iteration.

By accumulating all these repositioned bits using the OR operation (|=), we build up the reversed number bit by bit. After 32 iterations, we've processed all bits and have our complete reversed result.

This approach is efficient because it processes each bit exactly once and uses simple bitwise operations that are very fast at the hardware level.

Solution Approach

The solution uses bit manipulation to reverse the bits of a 32-bit integer. Let's walk through the implementation step by step:

Algorithm Overview: We iterate through all 32 bits of the input number, extracting each bit from the right side and placing it at the corresponding position on the left side of our result.

Step-by-step Implementation:

Initialize the result variable: Start with ans = 0, which will store our reversed bit pattern.
Loop through 32 bits: Use a for loop with i ranging from 0 to 31 to process each bit position.
Extract and reposition each bit: For each iteration i:
- Extract the rightmost bit of n using n & 1. This AND operation with 1 gives us the value of the least significant bit (either 0 or 1).
- Calculate the reversed position as 31 - i. When i = 0, the bit goes to position 31; when i = 31, the bit goes to position 0.
- Shift the extracted bit to its new position using (n & 1) << (31 - i).
- Combine this bit with our result using the OR operation: ans |= (n & 1) << (31 - i).
Prepare for next bit: After processing the current bit, right shift n by 1 position (n >>= 1) to bring the next bit into the least significant position for the next iteration.

Example Walkthrough: Let's say n = 5 (binary: 00000000000000000000000000000101)

Iteration 0: Extract bit 1, place at position 31 → ans = 10000000000000000000000000000000
Iteration 1: Extract bit 0, place at position 30 → ans = 10000000000000000000000000000000
Iteration 2: Extract bit 1, place at position 29 → ans = 10100000000000000000000000000000
Continue for remaining 29 iterations...

After all 32 iterations, we return ans which contains the reversed bit pattern.

Time Complexity: O(1) - We always iterate exactly 32 times regardless of input. Space Complexity: O(1) - We only use a constant amount of extra space.

Example Walkthrough

Let's walk through a small example with n = 11 (in decimal).

Initial Setup:

Input: n = 11
Binary: 00000000000000000000000000001011
Result: ans = 0

Key Iterations:

Iteration 0 (i=0):

Current n: ...001011
Extract rightmost bit: n & 1 = 1
Place at position 31: 1 << 31
Update result: ans = 10000000000000000000000000000000
Shift n right: n = ...000101

Iteration 1 (i=1):

Current n: ...000101
Extract rightmost bit: n & 1 = 1
Place at position 30: 1 << 30
Update result: ans = 11000000000000000000000000000000
Shift n right: n = ...000010

Iteration 2 (i=2):

Current n: ...000010
Extract rightmost bit: n & 1 = 0
Place at position 29: 0 << 29
Result unchanged: ans = 11000000000000000000000000000000
Shift n right: n = ...000001

Iteration 3 (i=3):

Current n: ...000001
Extract rightmost bit: n & 1 = 1
Place at position 28: 1 << 28
Update result: ans = 11010000000000000000000000000000
Shift n right: n = ...000000

Iterations 4-31:

Since n = 0 after iteration 3, all remaining bits are 0
n & 1 = 0 for all remaining iterations
The result remains: ans = 11010000000000000000000000000000

Final Result:

Binary: 11010000000000000000000000000000
Decimal: 3489660928

The original bits 1011 from the rightmost positions have been moved to the leftmost positions as 1101, effectively reversing the bit pattern across the entire 32-bit integer.

Solution Implementation

1class Solution:
2    def reverseBits(self, n: int) -> int:
3        """
4        Reverse the bits of a 32-bit unsigned integer.
5      
6        Args:
7            n: A 32-bit unsigned integer to reverse
8          
9        Returns:
10            The integer with bits reversed
11        """
12        result = 0
13      
14        # Process all 32 bits
15        for i in range(32):
16            # Extract the least significant bit from n using AND operation
17            # Shift it to its reversed position (31-i) and add to result using OR
18            result |= (n & 1) << (31 - i)
19          
20            # Right shift n by 1 to process the next bit in the next iteration
21            n >>= 1
22          
23        return result
24

1public class Solution {
2    /**
3     * Reverses the bits of a 32-bit unsigned integer.
4     * For example: 00000010100101000001111010011100 becomes 00111001011110000010100101000000
5     * 
6     * @param n - the input integer to reverse (treated as unsigned)
7     * @return the integer with reversed bits
8     */
9    public int reverseBits(int n) {
10        int result = 0;
11      
12        // Process all 32 bits
13        for (int bitPosition = 0; bitPosition < 32 && n != 0; bitPosition++) {
14            // Extract the least significant bit (rightmost) from n
15            int currentBit = n & 1;
16          
17            // Place the extracted bit at the mirrored position from the left
18            // (31 - bitPosition) calculates the reverse position
19            result |= currentBit << (31 - bitPosition);
20          
21            // Right shift n by 1 position (unsigned shift to handle negative numbers correctly)
22            n >>>= 1;
23        }
24      
25        return result;
26    }
27}
28

1class Solution {
2public:
3    uint32_t reverseBits(uint32_t n) {
4        uint32_t result = 0;
5      
6        // Process each bit position (up to 32 bits)
7        // Early termination when n becomes 0 (optimization)
8        for (int i = 0; i < 32 && n != 0; ++i) {
9            // Extract the least significant bit (LSB) of n
10            // Place it at position (31 - i) in the result
11            result |= (n & 1) << (31 - i);
12          
13            // Shift n right by 1 to process the next bit
14            n >>= 1;
15        }
16      
17        return result;
18    }
19};
20

1/**
2 * Reverses the bits of a 32-bit unsigned integer
3 * @param n - A positive integer to reverse bits for
4 * @returns The integer with bits reversed
5 */
6function reverseBits(n: number): number {
7    let result: number = 0;
8  
9    // Process each of the 32 bits
10    for (let i = 0; i < 32 && n > 0; i++) {
11        // Extract the rightmost bit of n using bitwise AND with 1
12        // Then shift it to its reversed position (31 - i) and OR it with result
13        result |= (n & 1) << (31 - i);
14      
15        // Right shift n by 1 to process the next bit
16        n >>= 1;
17    }
18  
19    // Use unsigned right shift to ensure the result is treated as unsigned 32-bit integer
20    return result >>> 0;
21}
22

Time and Space Complexity

The time complexity is O(1), not O(log n) as stated in the reference answer. This is because the loop runs at most 32 iterations for a fixed-width 32-bit integer. Even though the implementation may stop early once the remaining input bits are all zero, the number of operations is bounded by a constant.

The space complexity is O(1), which matches the reference answer. The algorithm only uses a fixed amount of extra space for the variable ans and the loop counter i, regardless of the input size.

The reference answer appears to be incorrect regarding time complexity. For this specific problem of reversing bits in a 32-bit integer, the time complexity should be O(1) since we perform at most 32 iterations. If this were a more general bit reversal problem where the number of bits varied with n, then O(log n) would be appropriate since the number of bits in n is proportional to log n.

Common Pitfalls

1. Unsafe Early Termination Before Positioning Bits

Early termination is safe only if every processed bit has already been shifted into its final reversed position. The provided solution does this with result |= (n & 1) << (31 - i), so stopping after the remaining input bits become zero is harmless.

A buggy early-termination approach builds the reversed bits by shifting the result left each iteration and then stops before padding the remaining zero bits:

# INCORRECT approach
def reverseBits(self, n: int) -> int:
    result = 0
    for i in range(32):
        if n == 0:
            break
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

Why this fails: This version has not placed processed bits into their final 32-bit positions. For n = 1, it returns 1, but the correct 32-bit reversal is 2147483648.

Safe variant: If you shift each bit directly to position 31 - i, then early termination after n becomes zero still produces the correct value because all remaining bits would contribute zero.

2. Using Wrong Shift Direction or Amount

Another pitfall is confusing the shift operations:

# INCORRECT approaches
result |= (n & 1) << i  # Wrong: shifts to wrong position
result |= (n & 1) >> (31 - i)  # Wrong: uses right shift instead of left
result |= (n >> 1) << (31 - i)  # Wrong: extracts wrong bit

Solution: Always remember:

Use n & 1 to extract the rightmost bit
Use << (31 - i) to place it at the reversed position
Use n >>= 1 to move to the next bit

3. Incorrect Bit Position Calculation

Some might incorrectly calculate the reversed position:

# INCORRECT
result |= (n & 1) << (32 - i)  # Wrong: shifts by 32 to 1 instead of 31 to 0
result |= (n & 1) << (30 - i)  # Wrong: incorrect range

Solution: The correct formula is 31 - i because:

Bit positions range from 0 to 31 (total 32 positions)
When i = 0, we want position 31
When i = 31, we want position 0

4. Not Processing All 32 Bits

Processing fewer than 32 bits leads to incomplete reversal:

# INCORRECT
for i in range(16):  # Wrong: only processes half the bits
    result |= (n & 1) << (31 - i)
    n >>= 1

Solution: Always iterate exactly 32 times to ensure all bits are properly reversed, regardless of the input value.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know