Reverse Bits
EasyBit manipulation
Given an unsigned 32-bit 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 number.
JavaScript has no unsigned 32-bit type, so n arrives as an ordinary number from 0 to 4294967295 (2³² − 1), and the answer must be in that range too. The bitwise operators give signed 32-bit results; x >>> 0 turns one back into an unsigned number.
Examples
Input: n = 1 Output: 2147483648
Bit 0 moves to bit 31: 1 becomes 2³¹ = 2147483648.
Input: n = 6 Output: 1610612736
6 is 110 in binary. Its bits 1 and 2 become bits 30 and 29: 2³⁰ + 2²⁹ = 1610612736.
Constraints
0 ≤ n ≤ 4294967295nis a whole number.
Stuck?
Hint 1
Take the bits of n from the lowest up, and push each onto the result from the right, 32 times in all.
Hint 2
Each step: shift the result left by one, add n & 1 with |, and shift n right with >>>. The last shift can set the sign bit, so finish with >>> 0.
The idea
Take the bits of n from the lowest up and push each one onto the result from the right. The bit taken first has been pushed furthest left by the time all 32 are in, so the order comes out reversed. The bitwise operators give signed results, so the result is turned back into an unsigned number at the end.
Time O(1): 32 stepsExtra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
out collects the reversed bits, starting with none.
function reverseBits(n) { let out = 0; for (let i = 0; i < 32; i++) { out = (out << 1) | (n & 1); n >>>= 1; } return out >>> 0;}The trap
It does all the bit work right but returns out as it stands. << gives a signed 32-bit result, so whenever bit 31 of the answer is set, which happens whenever n is odd, the number comes back negative. Even inputs leave the top bit clear and pass.
function reverseBits(n) { let out = 0; for (let i = 0; i < 32; i++) { out = (out << 1) | (n & 1); n >>>= 1; } return out; // signed: a set top bit comes back negative}