Reverse Bits
Problem statement
You are given a number n and should treat it as exactly 32 bits, padding with leading zeros if needed. Reverse the order of those 32 bits — the last bit becomes the first, the second-to-last becomes the second, and so on — and return the number the reversed bits represent.
n is between 0 and 2³¹ − 2 and is always even. Because its lowest bit is 0, the highest bit of the answer is 0 too, so the answer always fits in a normal signed 32-bit integer.
Examples
Example 1
Input: n = 43261596
Output: 964176192
Explanation: In 32 bits, 43261596 is 00000010100101000001111010011100. Read backwards, that is 00111001011110000010100101000000, which is 964176192.
Example 2
Input: n = 2147483644
Output: 1073741822
Explanation: 2147483644 is a 0, then twenty-nine 1s, then two 0s. Reversed, it becomes two 0s, twenty-nine 1s and a 0, which is 1073741822.
Hints
Approach
Optimal: Bit-by-bit shifting
Intuition
Think of taking cards off the bottom of one stack and putting them on top of another: the order flips. Here, the "bottom card" of n is its lowest bit, which n & 1 reads. Moving it onto result means shifting result left by one (making an empty slot at the bottom) and putting the bit there with |. Then n >> 1 throws away the bit we just used, so the next bit becomes the lowest.
After 32 rounds, the bit that was lowest in n has been shifted up 31 places to the top of result, and the bit that was highest in n sits at the bottom. That is the reversed number. We always do exactly 32 rounds — not "until n is 0" — so the leading zeros of n become trailing zeros of the answer.
Steps
- Set
result = 0. - Repeat 32 times:
- Shift
resultleft by 1. - Set the lowest bit of
resultton & 1(using|). - Shift
nright by 1.
- Shift
- Return
result.
Dry run
Shown on a 4-bit example so it fits: n = 1011 (reversed should be 1101).
| round | n & 1 | result after | n after |
|---|---|---|---|
| 1 | 1 | 0001 | 0101 |
| 2 | 1 | 0011 | 0010 |
| 3 | 0 | 0110 | 0001 |
| 4 | 1 | 1101 | 0000 |
The real code does the same for 32 rounds. Edge case: n = 0 gives 32 zeros → 0. Because the loop count is fixed, a small n like 2 correctly becomes 1073741824, with its 1 bit moved to position 30.
Complexity
Time O(1) - The loop always runs exactly 32 times, and each round does three tiny bit operations: an AND, and two shifts. That is about 100 machine operations per call, with no strings at all. If the width were b bits it would be O(b), but the width is fixed at 32.
Space O(1) - Only two numbers are kept: what is left of `n` and the `result` being built. Nothing else is allocated.
class Solution:
def reverseBits(self, n: int) -> int:
result = 0
for _ in range(32):
result = (result << 1) | (n & 1)
n >>= 1
return result
if __name__ == "__main__":
print(Solution().reverseBits(43261596)) # 964176192
print(Solution().reverseBits(2147483644)) # 1073741822RecapThe whole problem in a few lines, for the night before
- Spot it: reverse the 32 bits of an unsigned integer
- Idea: loop 32 times: shift the result left, add the lowest bit of n, then shift n right
- Cost: O(1) time (32 steps), O(1) space
- Trap: always do all 32 steps, even when the leading bits are zero, and use an unsigned shift in Java (>>>)
Interview follow-ups
This function is called millions of times. How would you speed it up?
Precompute a table of the reversed value for all 256 possible bytes. To reverse 32 bits, split
ninto its 4 bytes, look each one up, and put the reversed bytes back in the opposite order. That is 4 lookups instead of 32 loop rounds. The table costs 256 entries of memory, built once. This is the follow-up LeetCode itself asks.Reverse the bits of a 64-bit number instead.
Loop 64 times instead of 32, and use a 64-bit unsigned type (
longwith>>>in Java,uint64_tin C++). In Python, the same loop withrange(64)works as is. The time stays O(1) for a fixed width. With the byte table, it becomes 8 lookups.Reverse the order of the bytes, not the bits (endianness conversion).
Take the 4 bytes of
nwith shifts and masks —(n >> 24) & 0xFF,(n >> 16) & 0xFF, and so on — and put them back in the opposite order. Most languages have this built in:Integer.reverseBytesin Java,__builtin_bswap32in GCC and Clang, andint.from_bytes/to_bytesin Python. This is what network code does when converting between host order and network (big-endian) order.
Frequently asked questions
Stopping when n reaches 0 skips n's leading zeros. Those zeros must become the trailing zeros of the answer, which pushes the other bits up into the right places. With n = 2 (10), stopping early gives 01 = 1, while the correct 32-bit answer is 1073741824. A fixed 32 rounds always places every bit correctly.
In Java, >> copies the sign bit when shifting right, so a negative number would fill up with 1s; >>> always fills with 0s. In C++, shifting a signed value into or out of the top bit can be undefined behaviour, so the code works on an unsigned 32-bit copy and converts back at the end. With this problem's inputs the top bit is never set, but using the safe form avoids bugs if the limits change.
Yes: you can swap halves of the bits in 5 rounds — swap the two 16-bit halves, then the 8-bit halves inside each, then 4-bit, 2-bit and 1-bit — using masks like 0x55555555. It is clever but hard to explain and easy to get wrong in an interview. The 32-step loop is what interviewers expect; mention the mask version only as an extra.
A binary string from the language (like bin(2) or Integer.toBinaryString(2)) leaves out leading zeros, so it can be shorter than 32 characters. Reversing a short string puts the bits in the wrong positions. Padding to exactly 32 characters first makes every bit's position correct.
Bit order matters wherever data crosses a wire or a disk format. Some network protocols and checksums, such as the common CRC-32 used in Ethernet and zip files, process bits in reversed order, and bit-reversal is part of implementing them. More generally, it checks that you are comfortable with masks and shifts, which show up in IP subnet math, permission bits and feature-flag bitmaps.