Reverse the bits of a 32-bit unsigned integer n: bit 0 becomes bit 31, bit 1 becomes bit 30, and so on. In the tests n and the answer are plain non-negative numbers between 0 and 2^32 minus 1.
00000010100101000001111010011100 reversed is 00111001011110000010100101000000.- 0 <= n <= 2^32 - 1 (an unsigned 32-bit value)
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Converting to a binary string, padding to 32 characters, reversing and parsing back works but is clumsy. With bit operations, read the bits of n from the lowest one up, and write them into res from the highest one down: each step shifts res left and adds n & 1, then shifts n right. After 32 steps the first bit we read sits at position 31. Java note: Java has no unsigned int, so inputs and outputs above 2^31 minus 1 are stored as negative ints with the same bits. Use >>> (unsigned shift) on n; res simply collects the right 32 bits. Integer.reverse(n) does the same in one call.
Algorithm
- Set
res = 0. - Repeat 32 times:
res = (res << 1) | (n & 1)andn >>= 1(>>>in Java). - Return
res(in Python, it is already in the range 0 to 2^32 minus 1).
O(32) = O(1)Space: O(1)class Solution: def reverseBits(self, n: int) -> int: res = 0 for _ in range(32): res = (res << 1) | (n & 1) # append the lowest bit of n n >>= 1 return res