LeetCode 190 - Reverse Bits

LeetCode Problem 190

Difficulty: 🟢 Easy
Topics: Divide and Conquer, Bit Manipulation

Solution

Problem Understanding

The problem asks us to reverse the binary representation of a 32-bit integer. Instead of reversing the decimal digits of a number, we reverse the order of its individual bits.

For example, suppose the binary representation of a number is:

00000010100101000001111010011100

After reversing all 32 bits, it becomes:

00111001011110000010100101000000

The resulting reversed binary value is then converted back into an integer and returned.

A key detail is that we must always treat the input as a 32-bit value, even if leading zeros exist. Normally, binary numbers ignore leading zeros, but in this problem they matter because reversing bits changes their position. For example, reversing 1 is not 1, it becomes:

00000000000000000000000000000001

→ reversed →

10000000000000000000000000000000

This produces a completely different integer.

The input n represents a non-negative integer constrained by:

• 0 <= n <= 2³¹ - 2
• n is guaranteed to be even

Although the prompt mentions a signed integer, the actual operation is purely bit manipulation over a fixed 32-bit representation. Since the input range is bounded and fixed to 32 bits, we know that any efficient solution should ideally process exactly 32 positions.

Several edge cases are important to think about upfront. An input of 0 should remain 0 because every bit is zero. Numbers with only a single set bit, such as powers of two, can move that bit to the opposite side of the 32-bit representation after reversal. Inputs with many leading zeros are also important because those zeros become trailing zeros after reversal, and vice versa. Finally, since the problem always works with exactly 32 bits, forgetting to process all 32 positions would produce incorrect answers.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to first convert the number into a 32-bit binary string, reverse the string, and then convert the reversed binary representation back into an integer.

For example:

1. Convert 43261596 to a 32-character binary string.
2. Reverse the string.
3. Parse the reversed binary string as an integer.

This approach works because reversing the string exactly mirrors the required bit reversal operation. However, string manipulation introduces unnecessary overhead. We are solving a bit manipulation problem, so repeatedly converting between integers and strings is less efficient and less elegant than directly operating on bits.

Since the binary representation always has a fixed length of 32, the brute-force approach still runs in constant time in practice. However, conceptually it performs additional conversion work and uses extra memory.

Optimal Approach

The key insight is that we can construct the reversed number directly using bit manipulation.

We process the bits of n one at a time from right to left. At each step:

• Extract the least significant bit from n
• Shift the result left to make room for the next bit
• Add the extracted bit into the result
• Shift n right to continue processing

Why does this work?

When reversing bits, the least significant bit of the original number becomes the most significant bit of the result. By repeatedly taking bits from right to left and appending them to the left side of the answer, we naturally build the reversed binary representation.

Since the input is always exactly 32 bits, we repeat this process exactly 32 times.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(32)	O(32)	Convert to binary string, reverse it, convert back
Optimal	O(32)	O(1)	Reverse bits directly using bit operations

Even though both are technically constant time because 32 is fixed, the optimal method is preferred because it uses no extra storage and demonstrates proper bit manipulation.

Algorithm Walkthrough

1. Initialize a variable called result to 0. This variable will store the reversed bit sequence as we build it incrementally.
2. Iterate exactly 32 times. We must always process all 32 bits, including leading zeros, because they affect the final reversed result.
3. Extract the least significant bit of n using n & 1. The bitwise AND operation with 1 isolates the rightmost bit.
4. Shift result one position to the left using result << 1. This creates space for the new bit we are about to append.
5. Add the extracted bit into result using bitwise OR (|). This inserts the current bit into the correct position.
6. Shift n one position to the right using n >> 1. This removes the processed bit and moves the next bit into position.
7. After completing all 32 iterations, return result.

The reason this works is that every extracted bit is appended in reverse order. The first bit removed from n becomes the highest-positioned bit in the final answer.

Python Solution

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0

        for _ in range(32):
            bit = n & 1
            result = (result << 1) | bit
            n >>= 1

        return result

The implementation begins by initializing result to 0, which acts as the accumulator for the reversed number.

The loop runs exactly 32 times because the problem explicitly works with a fixed 32-bit representation. During each iteration, we isolate the rightmost bit of n using n & 1.

Next, result is shifted left by one position to create room for the new bit. We then insert the extracted bit using a bitwise OR operation.

Finally, n is shifted right to prepare for the next iteration. This continues until every bit has been processed.

By the end of the loop, the reversed 32-bit integer has been fully reconstructed and returned.

Go Solution

func reverseBits(n int) int {
	result := 0

	for i := 0; i < 32; i++ {
		bit := n & 1
		result = (result << 1) | bit
		n >>= 1
	}

	return result
}

The Go implementation follows exactly the same logic as the Python version. Since Go integers support bitwise operations directly, the implementation remains concise.

One important consideration is integer types. LeetCode's original problem typically uses uint32, but the provided function signature uses int, so we follow it exactly. Since the constraints guarantee a valid 32-bit non-negative number, shifting operations behave safely here.

Unlike Python, Go has fixed-width integer behavior depending on architecture, but because we only process 32 bits and remain within valid ranges, overflow is not an issue.

Worked Examples

Example 1

Input: n = 43261596

Binary form:

00000010100101000001111010011100

We process one bit at a time.

Iteration	Current Bit (n & 1)	Result After Shift and Add	n After Right Shift
1	0	0	21630798
2	0	0	10815399
3	1	1	5407699
4	1	3	2703849
5	1	7	1351924
...	...	...	...
32	Final bit processed	964176192	0

Final result:

00111001011110000010100101000000

Output:

964176192

Example 2

Input: n = 2147483644

Binary form:

01111111111111111111111111111100

We again process all 32 bits.

Iteration	Current Bit (n & 1)	Result After Shift and Add	n After Right Shift
1	0	0	1073741822
2	0	0	536870911
3	1	1	268435455
4	1	3	134217727
5	1	7	67108863
...	...	...	...
32	Final bit processed	1073741822	0

Final reversed binary:

00111111111111111111111111111110

Output:

1073741822

Complexity Analysis

Measure	Complexity	Explanation
Time	O(32)	We always process exactly 32 bits
Space	O(1)	Only a few integer variables are used

Although the algorithm is technically O(32), the number of operations is fixed and independent of input size, making it effectively constant time. The space complexity is constant because no additional data structures proportional to input size are allocated.

Edge Cases

Input Is Zero

If n = 0, all 32 bits are zero. Reversing them still results in zero. A careless implementation might terminate early when the number becomes zero, but our implementation explicitly runs 32 iterations, ensuring correctness.

Number With a Single Set Bit

Consider n = 1.

Binary representation:

00000000000000000000000000000001

After reversal:

10000000000000000000000000000000

This demonstrates why processing all 32 bits is essential. If we only processed until n == 0, we would incorrectly return 1.

Numbers With Leading Zeros

A number such as 8:

00000000000000000000000000001000

becomes:

00010000000000000000000000000000

Leading zeros are significant in this problem because they influence the bit positions after reversal. Our fixed 32-iteration loop guarantees they are handled correctly.

Maximum Constraint Value

For values near the upper limit, such as 2³¹ - 2, many bits are set. Since the algorithm only performs fixed-size bit operations exactly 32 times, performance remains constant and efficient regardless of how many bits are 1.

Follow Up: Optimizing for Many Calls

If this function is called many times, we can optimize by using memoization on bytes. Since a byte has only 256 possible values, we can precompute the reversed version of every 8-bit number.

Then:

1. Split the 32-bit integer into four bytes.
2. Reverse each byte using a lookup table.
3. Reassemble them in reversed order.

This reduces repeated computation and makes frequent calls significantly faster.