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.
Recommended Time and Space Complexity
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)