Reverse Bits

Problem Statement

Given a 32-bit unsigned integer n, reverse the bits of the binary representation of n and return the result.

Example 1:

# Input: n = 00000000000000000000000000010101
# Output: 2818572288 (10101000000000000000000000000000)
# Explanation: Reversing 00000000000000000000000000010101, which represents the unsigned integer 21, gives us 10101000000000000000000000000000 which represents the unsigned integer 2818572288.

Example 2:

# Input: n = 43261596
# Output: 964176192
# Explanation: The binary representation of 43261596 is 0000001010010100000111101001100. Reversing this binary string results in 00110010111100001010010100000000, which represents the unsigned integer 964176192.

O(1) time and O(1) space.

Hint 1

Consider the bitwise operations.

Hint 2

Can you reverse the bits in place?

Solution

Brute Force

def reverse_bits(n: int) -> int:
    binary = ""
    for i in range(32):
        if n & (1 << i):
            binary += "1"
        else:
            binary += "0"


    res = 0
    for i, bit in enumerate(binary[::-1]):
        if bit == "1":
            res |= (1 << i)


    return res

Time complexity: O(1) Space complexity: O(1)

Bit Manipulation

def reverse_bits(n: int) -> int:
    res = 0
    for i in range(32):
        bit = (n >> i) & 1
        res += (bit << (31 - i))
    return res

Time complexity: O(1) Space complexity: O(1)

Bit Manipulation (Optimal)

def reverse_bits(n: int) -> int:
    res = n
    res = (res >> 16) | (res << 16) & 0xFFFFFFFF
    res = ((res & 0xff00ff00) >> 8) | ((res & 0x00ff00ff) << 8)
    res = ((res & 0xf0f0f0f0) >> 4) | ((res & 0x0f0f0f0f) << 4)
    res = ((res & 0xcccccccc) >> 2) | ((res & 0x33333333) << 2)
    res = ((res & 0xaaaaaaaa) >> 1) | ((res & 0x55555555) << 1)
    return res & 0xFFFFFFFF

Time complexity: O(1) Space complexity: O(1)