EasyBlind75Bit Manipulation
Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
Examples
Input
n = 43261596 (binary 00000010100101000001111010011100)
Output
964176192 (binary 00111001011110000010100101000000)
The binary representation of 43261596 reversed is 964176192.
Input
n = 4294967293 (binary 11111111111111111111111111111101)
Output
3221225471 (binary 10111111111111111111111111111111)
The binary representation reversed is 10111111111111111111111111111111.
Constraints
- •
The input must be a binary string of length 32
Approaches
Convert to binary string, reverse, and convert back.
CodeT: O(32) = O(1) | S: O(1)
def reverse_bits(n):
result = 0
for i in range(32):
result = (result << 1) | (n & 1)
n >>= 1
return resultProcess bits from both ends and swap.
CodeT: O(32) = O(1) | S: O(1)
def reverse_bits(n):
result = 0
for i in range(32):
result <<= 1
result |= n & 1
n >>= 1
return resultReverse bits in chunks using bit manipulation tricks.
Diagram
n = 43261596 (00000010100101000001111010011100)
Swap 1-bit chunks: 00000001010010100000111101001110
Swap 2-bit chunks: 01000000100101010000111011001101
Swap 4-bit chunks: 01000010010101000011101100110111
Swap 8-bit chunks: 01000010010101000011101100110111
Swap 16-bit chunks: 00111001011110000010100101000000
Result: 964176192
CodeT: O(log 32) = O(1) | S: O(1)
def reverse_bits(n):
n = ((n & 0x55555555) << 1) | ((n & 0xAAAAAAAA) >> 1)
n = ((n & 0x33333333) << 2) | ((n & 0xCCCCCCCC) >> 2)
n = ((n & 0x0F0F0F0F) << 4) | ((n & 0xF0F0F0F0) >> 4)
n = ((n & 0x00FF00FF) << 8) | ((n & 0xFF00FF00) >> 8)
n = ((n & 0x0000FFFF) << 16) | ((n & 0xFFFF0000) >> 16)
return nComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| String Conversion | O(32) = O(1) | O(1) | Convert to binary string, reverse, and convert back. |
| Bit Shifting | O(32) = O(1) | O(1) | Process bits from both ends and swap. |
| Divide and Conquer | O(log 32) = O(1) | O(1) | Reverse bits in chunks using bit manipulation tricks. |
String Conversion
T: O(32) = O(1)S: O(1)
Convert to binary string, reverse, and convert back.
Bit Shifting
T: O(32) = O(1)S: O(1)
Process bits from both ends and swap.
Divide and Conquer
T: O(log 32) = O(1)S: O(1)
Reverse bits in chunks using bit manipulation tricks.
Common Mistakes
Not handling unsigned integers correctly
Forgetting that the result should be a 32-bit unsigned integer
Using string operations instead of bit operations