190. Reverse Bits

Reformulated question¶

Reverse the order of the bits in the 32-bit binary representation of n and return the resulting integer.

Example:

n = 43261596
32-bit: 00000010100101000001111010011100
rev  : 00111001011110000010100101000000
out = 964176192

Key trick¶

Build the answer bit by bit:

Take the current least significant bit with n & 1
Shift the answer left
Append that bit
Shift n right
Repeat exactly 32 times

Trap¶

Forgetting this is a fixed 32-bit problem, so leading zeroes matter
Stopping when n == 0 instead of looping 32 times
Confusing signed integer wording with Python integers; here just treat n as a 32-bit bit pattern

Why is this question interesting?¶

It checks whether you really understand bit manipulation, fixed-width representation, and how to construct a result incrementally with shifts and masks.

Solve the problem with idiomatic Python¶

class Solution:
    def reverseBits(self, n: int) -> int:
        # Build the reversed 32-bit number from left to right.
        ans = 0
        for _ in range(32):
            # Make room for the next bit.
            ans <<= 1
            # Append n's current last bit.
            ans |= n & 1
            # Move to the next bit in n.
            n >>= 1
        return ans

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("n", "expected"),
    [
        (0, 0),
        (1, 2147483648),
        (2, 1073741824),
        (43261596, 964176192),
        (2147483644, 1073741822),
        (2**32 - 1, 2**32 - 1),
        (0b00000000000000000000000000001010, 0b01010000000000000000000000000000),
    ],
)
def test_reverse_bits(n, expected):
    assert Solution().reverseBits(n) == expected

Comment my solution¶

Your solution is correct and idiomatic.

Good:
Exact 32 iterations
Correct use of n & 1, left shift, and right shift
Linear time and constant space
Small improvement:
Use | instead of + to emphasize bit assembly

n_rev = (n_rev << 1) | right

Minor comment fix:
Leading zeroes matter
Trailing zeroes also matter indirectly because all 32 positions are reversed

## Solution

import pytest

class Solution:
    def reverseBits(self, n: int) -> int:
        # we look at the 32 bits representation of `n`.
        # this means 0s at the beginning of this representation matter.
        # But the 0s at the end of this representation don't.
        n_rev = 0
        for _ in range(32):
          right = n & 1
          n_rev = (n_rev << 1) + right
          n >>= 1
        return n_rev

@pytest.mark.parametrize(
    ("n", "bit_reversed_n"),
    [(43261596, 964176192), (2147483644, 1073741822)]
)
def test_reverseBits(n, bit_reversed_n):
    assert Solution().reverseBits(n) == bit_reversed_n

format(43261596, "b")  # '10100101000001111010011100'
format(964176192, "b") # '111001011110000010100101000000'

# n         -> 32 bits
# 43261596  -> 00000010100101000001111010011100
# 964176192 -> 00111001011110000010100101000000

0 >> 0
1 >> 1 # 0
2 >> 1 # 1
format(2**32 - 1, "b") # '11111111111111111111111111111111'
len(format(2**32 - 1, "b")) # 32
(2**32 - 1) >> 31 # 1
(2**32 - 1) >> 32 # 0
0 << 1 # 0
1 << 1 # 2
1 << 2 # 4

bin(11) # "0b1011"
0b1101 # 13
bin(5) # "0b101"

Code¶

import pytest


class Solution:
    def reverseBits(self, n: int) -> int:
        # Reverse exactly 32 bits: leading zeroes are part of the input.
        ans = 0
        for _ in range(32):
            # Shift result left to make room for the next extracted bit.
            ans <<= 1
            # Copy n's least significant bit into the result.
            ans |= n & 1
            # Drop the bit we just used.
            n >>= 1
        return ans


@pytest.mark.parametrize(
    ("n", "expected"),
    [
        (0, 0),
        (1, 2147483648),
        (2, 1073741824),
        (43261596, 964176192),
        (2147483644, 1073741822),
        (2**32 - 1, 2**32 - 1),
        (0b00000000000000000000000000001010, 0b01010000000000000000000000000000),
    ],
)
def test_reverse_bits(n, expected):
    assert Solution().reverseBits(n) == expected


# Interactive examples
s = Solution()

s.reverseBits(43261596)   # 964176192
s.reverseBits(2147483644) # 1073741822
s.reverseBits(0)          # 0
s.reverseBits(1)          # 2147483648

format(43261596, "032b")
format(964176192, "032b")
format(s.reverseBits(0b1010), "032b")