Reverse bits of a given 32 bits unsigned integer.
Note:
-3
and the output represents the signed integer -1073741825
.Follow up:
If this function is called many times, how would you optimize it?
Example 1:
Input: n = 00000010100101000001111010011100 Output: 964176192 (00111001011110000010100101000000) Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:
Input: n = 11111111111111111111111111111101 Output: 3221225471 (10111111111111111111111111111111) Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.
Constraints:
32
Source
def reverse_bits(n):
"""
Time Complexity O(32)
Space Complexity O(1)
"""
result, power = 0, 31
while n:
result += (n & 1) << power # returns n&1 with the bits shifted to the left by 'power' places.
# + info here: https://wiki.python.org/moin/BitwiseOperators
n = n >> 1 # Returns n with the bits shifted to the right by 1 place
power -= 1
return result
def reverse_bits(n):
"""variations"""
result = 0
for _ in range(32):
result = (result << 1) + (n & 1)
n >>= 1
return result
def reverse_bits(n):
"""variations"""
out = 0
for _ in range(32):
out = (out << 1) ^ (n & 1)
n >>= 1
return out
def reverse_bits(n):
"""variations with O(16) Time Complexity."""
result = 0
for i in range(16):
right_bit = (n >> i) & 1
left_bit = (n >> (31-i)) & 1
result |= right_bit << (31-i) # |= performs an in-place operation
result |= left_bit << i # between pairs of objects
return result