LeetCode 190: Reverse Bits

Problem Restatement

We are given a 32-bit integer n.

We need to reverse its 32 bits and return the integer represented by the reversed bit pattern. The official statement asks us to reverse the bits of a given 32-bit integer.

For example, the binary form of 43261596 is:

00000010100101000001111010011100

After reversing all 32 bits, we get:

00111001011110000010100101000000

That binary value is 964176192.

Input and Output

Example function shape:

def reverseBits(n: int) -> int:
    ...

Examples

Example 1:

n = 43261596

Binary:

00000010100101000001111010011100

Reversed binary:

00111001011110000010100101000000

Output:

964176192

Example 2:

n = 2147483644

Binary:

01111111111111111111111111111100

Reversed binary:

00111111111111111111111111111110

Output:

1073741822

First Thought: Convert to Binary String

A simple way is:

1. Convert n to a binary string.
2. Pad it to length 32.
3. Reverse the string.
4. Convert it back to an integer.

In Python, that could look like this:

bits = bin(n)[2:].zfill(32)
reversed_bits = bits[::-1]
answer = int(reversed_bits, 2)

This works, but it avoids the main idea of the problem. The problem is meant to practice bit manipulation.

We should solve it directly with shifts and bitwise operations.

Key Insight

To reverse bits, we can read bits from right to left in n and build the answer from left to right.

At each step:

1. Take the last bit of n.
2. Append that bit to the right side of ans.
3. Shift n right to expose the next bit.

The last bit of n is obtained by:

n & 1

For example:

To make room in the answer, shift ans left by one:

ans <<= 1

Then add the extracted bit:

ans |= n & 1

Do this exactly 32 times.

Algorithm

1. Initialize ans = 0.
2. Repeat 32 times:
   • Shift ans left by one bit.
   • Add the lowest bit of n into ans.
   • Shift n right by one bit.
3. Return ans.

Correctness

At the first iteration, the least significant bit of n becomes the first bit added to ans.

Since ans is shifted left before each new bit is added, earlier bits move toward more significant positions.

After one iteration, ans contains the original bit 0.

After two iterations, ans contains original bits 0 and 1, in that order.

After all 32 iterations, ans contains all original bits from least significant to most significant.

That is exactly the reverse of the original 32-bit representation.

Because the loop always runs exactly 32 times, leading zeros in the original number are also handled correctly.

Complexity

Although there is a loop, the number of iterations does not grow with input size.

Implementation

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

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

        return ans

Code Explanation

We start with an empty result:

ans = 0

For each of the 32 bit positions:

for _ in range(32):

we first shift the answer left:

ans <<= 1

This creates one empty bit position on the right.

Then we copy the current lowest bit of n into that position:

ans |= n & 1

Finally, we shift n right:

n >>= 1

This removes the bit we just processed and exposes the next bit.

After 32 iterations, every bit has been moved to its reversed position.

Alternative Implementation: Place Each Bit Directly

Another version extracts each bit and places it into its final reversed position.

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

        for i in range(32):
            bit = (n >> i) & 1
            ans |= bit << (31 - i)

        return ans

Here, the bit at position i moves to position 31 - i.

This version mirrors the definition of bit reversal directly.

Testing

def run_tests():
    s = Solution()

    assert s.reverseBits(43261596) == 964176192
    assert s.reverseBits(2147483644) == 1073741822
    assert s.reverseBits(0) == 0
    assert s.reverseBits(1) == 2147483648
    assert s.reverseBits(2) == 1073741824

    print("all tests passed")

run_tests()

Test meaning: