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)