How do you solve Reverse Bits?

Iterate over all 32 bit positions. For each position i, extract the bit at i by shifting n right by i and masking with 1. Then shift this bit left by (31 - i) to place it in the reversed position and combine it into the result using bitwise OR. After processing all bits, return the accumulated result. This approach runs in O(1) time since the bit width is fixed and uses O(1) space.

Reverse Bits

Q: What is the time complexity of Reverse Bits?

O(1). The algorithm performs a fixed 32-iteration loop regardless of input size, so the time complexity is constant.

Q: What pattern does Reverse Bits use?

The Pattern: Bit Manipulation (Bitwise Position Reversal) The Heuristic: When reversing bits, treat the problem as a fixed positional mapping where each bit's index i maps to 31 - i; extract and reposition bits using shifts and masks without converting to strings.

Easy Bit Manipulation

Problem

Given a 32-bit unsigned integer n, return the integer obtained by reversing its bits.

The input is a 32-bit unsigned integer.
The output must also be a 32-bit unsigned integer.

Example

Input: n = 43261596

Output: 964176192

The binary representation of 43261596 is 00000010100101000001111010011100. Reversing the bits yields 00111001011110000010100101000000, which corresponds to 964176192 in decimal. The algorithm iterates over each bit position i from 0 to 31, extracts the bit at position i, and sets it at position 31 - i in the result. This systematic reversal ensures the bits are flipped in order.

Approach

Straightforward Solution

A naive approach might convert the integer to a 32-character binary string, reverse the string, and convert back to an integer. This approach is inefficient due to string manipulation overhead and does not leverage bitwise operations.

Core Observation

Reversing bits is a positional transformation where the bit at index i in the input moves to index 31 - i in the output. This is a fixed mapping independent of the bit values themselves.

Path to Optimal

Preview

The key insight is to use bitwise operations to extract and reposition bits directly. By iterating over each bit position, the algorithm extracts the bit using a right shift and bitwise AND, then places it in the reversed position using a left shift and bitwise OR…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate over all 32 bit positions. For each position i, extract the bit at i by shifting n right by i and masking with 1…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(1)

The algorithm performs a fixed 32-iteration loop regardless of input size, so the time complexity is constant.

Space

O(1)

Only a fixed number of integer variables are used, with no additional data structures proportional to input size.

Pattern Spotlight

Bit Manipulation (Bitwise Position Reversal)

When reversing bits, treat the problem as a fixed positional mapping where each bit's index i maps to 31 - i; extract and reposition bits using shifts and masks without converting to strings.

Solution

Python

1class Solution:
  def reverseBits(self, n: int) -> int:
      res = 0
      for i in range(32):
          bit = (n >> i) & 1
          res = res | (bit << (31 - i))
      return res

Step-by-Step Solution

Initialize Result Accumulator

3 res = 0

Objective

To prepare a variable to accumulate the reversed bits as they are computed.

Key Insight

Starting with zero ensures that the result has no bits set initially. As bits are extracted and repositioned, they are combined into this accumulator using bitwise OR, building the reversed bit pattern incrementally.

Interview Quick-Check

Core Logic

Initialize the result to zero to serve as a clean slate for accumulating reversed bits.

Common Pitfalls & Bugs

Failing to initialize the result to zero can lead to incorrect results due to residual bits.

Extract and Reposition Each Bit in a Fixed Loop

To iterate over each bit position, extract the bit, and place it in the reversed position within the result.

Return the Fully Reversed Bit Integer

To output the integer representing the reversed bit pattern after processing all bits.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 6 Critical

res = res | (bit << (31 - i))

Shift the extracted bit to its reversed position and combine it into the result using bitwise OR.

Shifting the bit left by (31 - i) repositions it to the reversed index, and bitwise OR merges it into the result without altering previously set bits, cumulatively building the reversed bit pattern.

Full line-by-line criticality + rationale for all 5 lines available on Pro.

Test Your Understanding

Why is it necessary to shift the extracted bit to position (31 - i) before OR-ing it into the result?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Reverse Bits from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Reverse Bits drill

or drill a free problem

1	`class Solution:`
2	`def reverseBits(self, n: int) -> int:`
3	`res = 0`
4	`for i in range(32):`
5	`bit = (n >> i) & 1`
6	`res = res \| (bit << (31 - i))`
7	`return res`