Reverse Bits
EasyThe problem
Treat n as a 32-bit number (pad with leading zeros if it is short). Reverse the order of its 32 bits and return the new number.
- Example 1Input: n = 43261596Output: 964176192
43261596 is 00000010100101000001111010011100 in 32 bits. Reversed, that is 00111001011110000010100101000000, which is 964176192.
- Example 2Input: n = 4294967293Output: 3221225471
In 32 bits n is 1111...1101 (only bit 1 is zero). Reversed, the single zero moves to the second-highest bit.
- 0 ≤ n < 2^32, passed as a plain non-negative int
- The result also fits in 32 bits (non-negative)
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Take the lowest bit of n and push it onto the result from the other side, 32 times.
The idea
For 32 iterations: result = (result << 1) | (n & 1); n >>= 1.
Target: O(32) time
Go function shape
func reverseBits(n int) intReference solution
Tested with go test. Try it yourself first, then compare.
// ReverseBits: peel the lowest bit off n and push it onto the result from the right.
func ReverseBits(n uint32) uint32 {
var result uint32
for range 32 {
result = result<<1 | n&1
n >>= 1
}
return result
}