Domain 1EasyCORE

Reverse Bits

The problem requires reversing the bits of a given 32-bit unsigned integer. The input is a binary string representing an unsigned integer, and the output should be the reversed binary string interpreted as an unsigned integer.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Bit Manipulation

190. Reverse Bits

Model: qwen2.5-coder:14b
Topics: Bit Manipulation
FAANG asked: 1
Acceptance rate: 42.6%


Problem Breakdown

The problem requires reversing the bits of a given 32-bit unsigned integer. The input is a binary string representing an unsigned integer, and the output should be the reversed binary string interpreted as an unsigned integer.

Inputs:

  • A 32-bit unsigned integer n.

Outputs:

  • A 32-bit unsigned integer with its bits reversed.

Implicit Constraints/Tricky Edge Cases:

  • The input is always a 32-bit number.
  • In languages like Java, the integer is represented in two’s complement form, but this should not affect the bit manipulation since we are dealing with unsigned integers internally.
  • The function should handle cases where all bits are zero or all bits are one.

Intuition

A brute-force approach would involve converting the integer to a binary string, reversing that string, and then converting it back to an integer. However, this approach is inefficient in terms of both time and space complexity due to multiple conversions.

The key insight is to use bit manipulation techniques to reverse the bits directly without converting to strings. This can be achieved by iterating through each bit position from 0 to 31 (since we are dealing with 32-bit numbers). For each bit position i, extract the bit at that position in n using bitwise AND (n & (1 << i)). Place this extracted bit into its reversed position in reversed_n by shifting it to the correct position and then performing a bitwise OR.

Approach

  1. Initialize a variable reversed_n to store the result, starting with 0.
  2. Iterate over each bit position from 0 to 31 (since we are dealing with 32-bit numbers).
  3. For each bit position i, extract the bit at that position in n using bitwise AND (n & (1 << i)).
  4. Place this extracted bit into its reversed position in reversed_n by shifting it to the correct position and then performing a bitwise OR.
  5. After processing all bits, return reversed_n.

Complexity Analysis

  • Time Complexity: O(1) - The algorithm iterates a fixed number of times (32 iterations), regardless of the input size.
  • Space Complexity: O(1) - Only a constant amount of extra space is used.

Solution

def reverseBits(n):
    reversed_n = 0
    for i in range(32):
        # Extract the bit at position i
        bit = (n >> i) & 1
        # Place it into its reversed position in reversed_n
        reversed_n |= (bit << (31 - i))
    return reversed_n

Edge Cases Handled

  • All bits are zero: The function will correctly return 0.
  • All bits are one: The function will correctly return the maximum 32-bit unsigned integer value, which is 4294967295.
  • Single bit set: For example, if n is 1, the output should be 2147483648 (binary 10000000000000000000000000000000).
  • Mixed bits: The function handles any combination of bits correctly by reversing their positions.