Problem overview
The method reverseBits(long n) receives a number written in binary with exactly 32 bits, leading zeros included. It reverses the order of those 32 bits, so the last bit becomes the first, the second to last becomes the second, and so on, and returns the number the reversed bits form.
For n = 43261596 the 32-bit form is 00000010100101000001111010011100. Reversed, it is 00111001011110000010100101000000, which is 964176192. For n = 1 the only 1 bit moves from the end to the front, and the answer is 2^31 = 2147483648.
The input can be as large as 2^32 - 1, and so can the answer. An int stops at 2^31 - 1, so the lesson uses long for both. The target is O(1) time, one step for each of the 32 bits, and O(1) extra space.
Approach: take bits off one end, push them onto the other
The last bit of n is n & 1. Shifting n right by one drops that bit, so the next bit becomes the last. Taking bits this way visits them from right to left.
The answer is built in result from the other side. In each round result is shifted left by one, which leaves a 0 at its right end, and the bit just taken is put there with OR. Bits taken earlier keep moving left while newer ones arrive behind them. The first bit taken ends up farthest left and the last one ends up on the right, which is exactly the mirror image.
The loop must run exactly 32 times, even after n has become 0. Leading zeros of n are part of the 32 bits, and they become the last bits of the answer. Stopping early would leave the other bits too far to the right.
For n = 6 the first rounds look like this:
i=0 result=0 n=3
i=1 result=1 n=1
i=2 result=11 n=0
i=3 result=110 n=0
After all 32 rounds the result is 1610612736, which is 110 followed by 29 zeros: the bits 110 of 6 now sit at the front.
Step by step
- Create
resultas alongstarting at 0. It collects the bits one at a time. - Write a loop that runs 32 times:
int ifrom 0 whilei < 32. Every bit moves, leading zeros included. - Shift and insert. Shift
resultone place left with<< 1and putn & 1into the free place with|. This line does the reversing. - Drop the bit just used:
n >>= 1. The next bit ofnbecomes the last one. - Return
result. After 32 rounds the bit taken first has moved 31 places left, so every bit sits in its mirrored place.
The solution in Java
class Solution {
public long reverseBits(long n) {
long result = 0;
for (int i = 0; i < 32; i++) {
result = (result << 1) | (n & 1);
n >>= 1;
}
return result;
}
}
The Java details worth a closer look:
- Why
long. The values go up to 4294967295, which anintcan't hold: adding 1 toInteger.MAX_VALUEwraps to -2147483648. Alonghas 64 bits, so 2^32 - 1 fits easily, and the answer forn = 1, 2147483648, prints as a positive number. >>=is safe here. Java's>>copies the sign bit into the freed place, butnis never negative as along, since it is at most 2^32 - 1. Zeros come in from the left.- Precedence.
|has lower precedence than<<and&, so the parentheses aren't required. They make the three steps easy to read. - Assigning to a parameter.
n >>= 1changes only the method's copy ofn.
Complexity
Time: O(1). The loop runs exactly 32 times, whatever n is.
Space: O(1). Two numbers are kept, result and n, plus the loop counter.
Edge cases and common mistakes
- Zero. All 32 bits are 0, so the answer is 0.
- All bits set.
4294967295is 32 ones and reversing it changes nothing, so the answer is 4294967295. - Stopping when
nbecomes 0. Awhile (n != 0)loop would end after the first round forn = 1and return 1 instead of 2147483648, because the single bit would never be moved to the front. - Using an
intresult. The bit pattern would be right, but a value such as 2147483648 would come out as -2147483648. The lesson's tests compare numbers, so the result has to be along. - Shifting
resultafter the OR. The order matters: shift first, then insert the bit. Doing it the other way round moves the bit one place too far. - Forgetting to shift
n. Withoutn >>= 1the same bit is taken 32 times.
Testing
n = 43261596gives 964176192.n = 1gives 2147483648.n = 4294967293gives 3221225471.n = 0gives 0.n = 4294967295gives 4294967295.n = 2147483648gives 1.
