The problem
Reverse the order of the 32 bits of the number n, read as an unsigned integer (every bit a digit, none a sign), and return the result.
Examples
01
- Input
n = 43261596
- Output
964176192
02
- Input
n = 4294967293
- Output
3221225471
Constraints
nfits in 32 bits.
The idea
Build the answer one bit at a time. Take n’s lowest bit (n & 1), shift the answer left to make room, and put the bit in at its low end; then shift n right to bring up its next bit.
The bit taken first — n’s lowest — has been shifted left 31 times by the end, so it lands at the top: exactly the reversal. Reading the result as unsigned matters where a language’s int would otherwise call the top bit a minus sign.
- Time
- O(1) — always 32 steps
- Space
- O(1)
Solution · every language run against every case
class Solution: def reverseBits(self, n: int) -> int: out = 0 for _ in range(32): out = (out << 1) | (n & 1) # take n's lowest bit onto out's low end n >>= 1 return out