← ~/lc-grind/posts

#190 - Reverse Bits

May 8, 2025

Reverse Bits

Problem Description

Reverse bits of a given 32 bits unsigned integer.

Note:

  • Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Example 1:


Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:


Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Constraints:

  • The input must be a binary string of length 32

Follow up: If this function is called many times, how would you optimize it?

Solution

1. Problem Deconstruction

Rewrite the Problem

  1. Technical:
    Given a 32-bit unsigned integer represented as a binary string of length 32, reverse the order of its bits and return the resulting integer. Handle cases where the integer may be interpreted as signed in certain languages, ensuring bitwise equivalence.

  2. Beginner:
    Flip the order of all 32 binary digits in a given number (e.g., “101” becomes “101” if reversed as 3 bits, but “101000…” becomes “…000101” for 32 bits). Convert this reversed binary string back to a decimal number.

  3. Mathematical:
    For an input integer ( n ), compute ( m ) such that:
    [ m = \sum_{i=0}^{31} \left( \left\lfloor \frac{n}{2^i} \right\rfloor \mod 2 \right) \times 2^{31 - i} ]

Constraint Analysis

  • Binary string of length 32:
    • Limits solutions to fixed-width bit manipulation.
    • Implies edge cases like all zeros, all ones, and leading/trailing zeros.
  • 32-bit unsigned integer:
    • Requires handling of potential overflow in languages with fixed-width integers (not applicable in Python).
    • Hidden edge case: Inputs with the 32nd bit set (e.g., ( 2^{31} )) must not be treated as negative during reversal.

2. Intuition Scaffolding

Analogies

  1. Real-World Metaphor:
    Like flipping a deck of 32 cards end-to-end, where each card’s new position is mirrored from its original.

  2. Gaming Analogy:
    Imagine rearranging a 32-slot inventory grid so the first item moves to the last slot, and vice versa.

  3. Math Analogy:
    Constructing a new number where each coefficient in its binary expansion is permuted inversely.

Common Pitfalls

  1. Partial Reversal: Stopping when ( n ) becomes zero misses trailing zeros.
  2. Sign Extension: Not masking during shifts in languages with signed integers (e.g., Java).
  3. String Conversion: Using string operations for bit reversal, which is inefficient for repeated calls.
  4. Byte vs. Bit Reversal: Swapping bytes instead of individual bits.
  5. Off-by-One Errors: Incorrectly mapping bit positions (e.g., ( 31 - i ) vs. ( 32 - i )).

3. Approach Encyclopedia

Brute Force

  • Pseudocode:
    def reverse_bits(n):  
    result = 0  
    for i in range(32):  
        bit = (n >> i) & 1          # Extract ith bit  
        result |= (bit << (31 - i))  # Set reversed position  
    return result
  • Complexity:
    • Time: ( O(1) ) (32 iterations).
    • Space: ( O(1) ).
  • Visualization:
    Original: [b0, b1, ..., b31]  
Reversed: [b31, b30, ..., b0]

Optimal (Bit Shifting)

  • Pseudocode:
    def reverse_bits(n):  
    n = n & 0xFFFFFFFF  # Mask to 32 bits  
    result = 0  
    for _ in range(32):  
        result = (result << 1) | (n & 1)  
        n >>= 1  
    return result
  • Complexity:
    • Time: ( O(1) ). Each of 32 iterations performs ( O(1) ) operations.
    • Space: ( O(1) ).
  • Visualization:
    Step 1: n = ...b31b30...b1b0  
Step 2: result accumulates bits from LSB to MSB:  
        result = b0 → b0b1 → ... → b0b1...b31

Lookup Table Optimization (Follow-Up)

  • Pseudocode:
    # Precompute reversed bytes (0-255)  
reverse_table = [...]  
def reverse_bits(n):  
    return (reverse_table[(n >> 0) & 0xFF] << 24) | \  
           (reverse_table[(n >> 8) & 0xFF] << 16) | \  
           (reverse_table[(n >> 16) & 0xFF] << 8) | \  
           (reverse_table[(n >> 24) & 0xFF] << 0)
  • Complexity:
    • Precompute: ( O(256) ).
    • Time per call: ( O(1) ).
  • Visualization:
    Split n into 4 bytes: [B3][B2][B1][B0]  
Reversed: reversed(B0) | reversed(B1) << 8 | ...

4. Code Deep Dive

Optimal Solution Code

def reverse_bits(n):  
    n = n & 0xFFFFFFFF  # Ensure 32-bit unsigned  
    result = 0  
    for _ in range(32):  
        result = (result << 1) | (n & 1)  
        n >>= 1  
    return result

Line-by-Line Annotations

  1. n = n & 0xFFFFFFFF: Masks input to 32 bits, handling signed/unsigned ambiguity.
  2. result = 0: Initializes the reversed integer.
  3. for _ in range(32): Iterates over all 32 bits.
  4. result = (result << 1) | (n & 1): Shifts result left and appends LSB of n.
  5. n >>= 1: Discards the processed bit.

Edge Case Handling

  • Example 1:
    Input 43261596 (binary 00000010100101000001111010011100). The loop shifts all 32 bits, capturing trailing zeros.
  • Example 2:
    Input -3 (binary 11111111111111111111111111111101). Masking converts to 4294967293, ensuring correct reversal.

5. Complexity War Room

Hardware-Aware Analysis

  • 32 iterations with bitwise operations use minimal registers (1-2 CPU cycles per operation).
  • Memory usage: 8 bytes for n and result (fits in L1 cache).

Industry Comparison Table

Approach Time Space Readability Interview Viability
Brute Force O(1) O(1) 7/10 ✅
Bit Shifting O(1) O(1) 9/10 ✅ Optimal
Lookup Table O(1) O(1) 6/10 ✅ Follow-Up

6. Pro Mode Extras

Variants

  • Reverse 64 Bits: Extend the loop to 64 iterations.
  • Reverse Arbitrary Bits: Parameterize bit length (e.g., reverse_bits(n, bits=32)).

Interview Cheat Sheet

  • Key Insight: Bitwise operations avoid costly string conversions.
  • Mention First: Always state time/space complexity upfront.
  • Corner Cases: All zeros, all ones, and alternating patterns.