How do you approach Reverse Bits?

Loop exactly 32 times regardless of the value - the leading zeros are part of the answer.

What is the time complexity of Reverse Bits?

Time complexity: O(1) - always 32 iterations.. Space complexity: O(1).

What are common mistakes on Reverse Bits?

Shifting by at least the word width, which is undefined or wraps depending on the language. Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends. Precedence: & and | bind more loosely than the comparison operators, so a & 1 == 0 does not mean what it looks like.

gitGood.dev

← Back to problems

Reverse Bits

EasyAlgorithms

Description

Reverse the bits of a given 32-bit unsigned integer and return the result.

Every one of the 32 positions participates, including leading zeros - reversing 1 gives 2147483648, not 1.

Example 1

Input: n = 43261596

Output: 964176192

Example 2

Input: n = 1

Output: 2147483648

Example 3

Input: n = 0

Output: 0

Constraints

- 0 <= n <= 2^31 - 1 (treated as a 32-bit unsigned value) - The reversal is over exactly 32 bit positions, leading zeros included.

Reverse Bits: approach, complexity and pitfalls

An easy bit manipulation problem, graded against 6 test cases (3 of them hidden).

The pattern: Bit Manipulation

XOR, masks, and shifts - constant-space tricks for counting and pairing.

Reach for it when you see: "Appears once/twice", powers of two, or an explicit O(1) space requirement.

If you are stuck

Show the 3-step hint ladder

Loop exactly 32 times regardless of the value - the leading zeros are part of the answer.
Each round: shift the result left by one, OR in the input's lowest bit, then shift the input right by one.
In JavaScript, bitwise operators produce signed 32-bit values, so finish with >>> 0 to reinterpret the result as unsigned.

The optimal approach

Show the approach: Exactly 32 iterations, always

The algorithm mirrors reversing a string: pull bits off the bottom of the input and push them onto the bottom of the output, which shifts previously-placed bits up toward the top.

Each round does three things - shift the result left one position, OR in the input's lowest bit (`n & 1`), then shift the input right one position.

The critical constraint is the fixed 32 iterations. Stopping when the input reaches zero seems like a natural optimization and produces the wrong answer, because the remaining leading zeros still need shifting into place. Reversing `1` must yield `2147483648`: 31 zeros trail the single set bit.

JavaScript needs care because bitwise operators coerce to signed 32-bit, so a result with the top bit set reads as negative. The final `>>> 0` reinterprets it as unsigned. Python has unbounded integers, so the 32-bit width has to be imposed by the loop rather than by the type.

If asked to optimize for many calls, the two standard answers are memoizing byte-sized chunks in a 256-entry lookup table, or the branchless divide-and-conquer swap of adjacent bits, then pairs, then nibbles, bytes, and halves - O(log 32) operations with no loop.

Time: O(1) - always 32 iterations.
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Bit Manipulation mistakes

These apply to the pattern as a whole, not just this problem.

Shifting by at least the word width, which is undefined or wraps depending on the language.
Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends.
Precedence: `&` and `|` bind more loosely than the comparison operators, so `a & 1 == 0` does not mean what it looks like.