Reverse Bits
You're given a 32-bit unsigned integer n. Reverse the order of its 32 bits, so bit 0 becomes bit 31 and bit 31 becomes bit 0, and return the result as an unsigned integer. In Java, which has no unsigned int, the input and output are signed ints holding the same 32-bit patterns.
Examples
n = 1 returns 2147483648
Only bit 0 is set, so the result has only bit 31 set, which is 2^31. In Java this pattern prints as -2147483648.
n = 6 returns 1610612736
6 has bits 1 and 2 set. They move to bits 30 and 29, and 2^30 + 2^29 = 1610612736.
n = 0 returns 0
No bits are set, so there is nothing to move.
Constraints
- n is a 32-bit unsigned integer: 0 <= n <= 2^32 - 1.
Hints
Read n's bits from the lowest up. Where should the first bit you read end up?
Use shifts and masks: n & 1 reads the lowest bit, and shifting the result left makes room for the next one.
Loop exactly 32 times: result = (result << 1) | (n & 1), then n >>>= 1 (n >>= 1 in Python).
Drill This: Your Approach First
Approach
Build the result one bit at a time. Repeat 32 times: shift result left by one, copy n's lowest bit into it with result | (n & 1), then shift n right by one. The bit read first ends up shifted 31 places, at the top. Always run all 32 rounds, since leading zeros in n become trailing zeros in the result. O(1) time and space.
Time
O(1)
Space
O(1)
Pitfall
Solutions
public class Solution {
public int reverseBits(int n) {
int result = 0;
for (int i = 0; i < 32; i++) {
result = (result << 1) | (n & 1);
n >>>= 1;
}
return result;
}
}class Solution:
def reverseBits(self, n: int) -> int:
result = 0
for _ in range(32):
result = (result << 1) | (n & 1)
n >>= 1
return result