Reverse Bits
Reverse 32 bits of an unsigned int — shift the result left and OR with the low bit of the input each step.
2 min read
bit-manipulation
Problem#
Reverse the bits of a 32-bit unsigned integer.
Examples#
00000010100101000001111010011100→00111001011110000010100101000000(i.e.,43261596→964176192).11111111111111111111111111111101→10111111111111111111111111111111.
Constraints#
- Input is a 32-bit unsigned integer.
Approach#
Loop 32 times: shift ans left by 1, OR in the low bit of n, shift n right by 1.
Solution#
class Solution {public: uint32_t reverseBits(uint32_t n) { uint32_t ans = 0; for (int i = 0; i < 32; ++i) { ans = (ans << 1) | (n & 1u); n >>= 1; } return ans; }};func reverseBits(n uint32) uint32 { var ans uint32 = 0 for i := 0; i < 32; i++ { ans = (ans << 1) | (n & 1) n >>= 1 } return ans}class Solution: def reverseBits(self, n: int) -> int: ans = 0 for _ in range(32): ans = (ans << 1) | (n & 1) n >>= 1 return ansfunction reverseBits(n) { let ans = 0; for (let i = 0; i < 32; i++) { ans = (ans << 1) | (n & 1); n >>>= 1; } return ans >>> 0;}public class Solution { public int reverseBits(int n) { int ans = 0; for (int i = 0; i < 32; i++) { ans = (ans << 1) | (n & 1); n >>>= 1; } return ans; }}function reverseBits(n: number): number { let ans = 0; for (let i = 0; i < 32; i++) { ans = (ans << 1) | (n & 1); n >>>= 1; } return ans >>> 0;}Editorial#
This is a “feed the bits in reverse order” pattern. Each iteration consumes the LSB of input and deposits it as the LSB of output, then both shift — exactly mirroring the bit order. A divide-and-conquer mask-swap version reverses in five O(1) steps for the speed-conscious.
Complexity#
- Time:
O(32)constant. - Space:
O(1).
Concept revision#
Related#