LeetCode 190: Reverse Bits Solution in Python Explained

Problem Statement

In LeetCode 190, you’re given a 32-bit unsigned integer n. Your task is to reverse the order of its bits and return the resulting 32-bit unsigned integer. For example, reversing 00000010100101000001111010011100 (decimal 43261596) yields 00111001011110000010100101000000 (decimal 964176192). This differs from array rotation like LeetCode 189: Rotate Array, focusing on bit-level manipulation rather than element shifting.

Constraints

• Input is a 32-bit unsigned integer (0 to 2³² - 1).
• Output must be a 32-bit unsigned integer.

Example

Let’s see some cases:

Copy codeInput: n = 43261596 (binary: 00000010100101000001111010011100)
Output: 964176192 (binary: 00111001011110000010100101000000)
Explanation: Reverse 32 bits of 43261596.

Copy codeInput: n = 4294967293 (binary: 11111111111111111111111111111101)
Output: 3221225471 (binary: 10111111111111111111111111111111)
Explanation: Reverse 32 bits of 4294967293.

Copy codeInput: n = 0 (binary: 00000000000000000000000000000000)
Output: 0 (binary: 00000000000000000000000000000000)
Explanation: All zeros, no change.

These examples show we’re reversing 32-bit patterns.

Understanding the Problem

How do you solve LeetCode 190: Reverse Bits in Python? Take n = 43261596 (binary: 00000010100101000001111010011100). We need to reverse its 32 bits to get 00111001011110000010100101000000 (decimal 964176192). A naive approach might convert to a string, reverse it, and convert back, but bit manipulation with shifts is more efficient and direct. We need an O(1) time solution (fixed 32 bits), not a stock trading task like LeetCode 188: Best Time to Buy and Sell Stock IV. We’ll use: 1. Bit Manipulation with Shift: O(1) time, O(1) space—our best solution. 2. String Conversion: O(1) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Bit Manipulation with Shift Approach

Explanation

Bit Manipulation with Shift reverses bits by:

• Using a loop over 32 iterations (fixed for 32-bit integer).
• For each bit:
• Shift result left by 1 (result <<= 1).
• Add the least significant bit of n (result |= n & 1).
• Shift n right by 1 (n >>= 1).
• After 32 steps, result holds the reversed bits.

This achieves O(1) time (constant 32 iterations), O(1) space (few variables), and efficiency by directly manipulating bits without string conversion.

For n = 43261596:

• Start: n = 00000010100101000001111010011100, result = 0.
• Iterate 32 times, building 00111001011110000010100101000000.

Step-by-Step Example

Example 1: n = 43261596 (00000010100101000001111010011100)

Goal: Return 964176192 (00111001011110000010100101000000).

• Step 1: Initialize.
• n = 00000010100101000001111010011100, result = 0.
• Step 2: Iterate 32 times (partial steps shown).
• i=0: n & 1 = 0, result = 0, n >>= 1 → 0000001010010100000111101001110.
• i=1: n & 1 = 0, result = 0, n >>= 1 → 000000101001010000011110100111.
• i=2: n & 1 = 1, result = 1, n >>= 1 → 00000010100101000001111010011.
• ...
• i=29: n & 1 = 0, result = 00111001011110000010100101000, n = 000.
• i=30: n & 1 = 0, result = 001110010111100000101001010000.
• i=31: n & 1 = 0, result = 00111001011110000010100101000000.
• Step 3: Finish.
• result = 964176192.

Example 2: n = 0

Goal: Return 0.

• Step 1: n = 00000000000000000000000000000000, result = 0.
• Step 2: 32 iterations, all bits 0, result = 0.
• Finish: Return 0.

How the Code Works (Bit Manipulation with Shift) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef reverseBits(n: int) -> int:
    # Line 1: Initialize result
    result = 0
    # Start with 0 (e.g., 00000000000000000000000000000000)

    # Line 2: Iterate 32 times
    for i in range(32):
        # Fixed 32-bit loop (e.g., 0 to 31)

        # Line 3: Shift result left
        result <<= 1
        # Make room for next bit (e.g., 0 → 0, then 1 → 10)

        # Line 4: Add least significant bit of n
        result |= n & 1
        # OR with n’s LSB (e.g., 0|0=0, 0|1=1)

        # Line 5: Shift n right
        n >>= 1
        # Drop LSB (e.g., 10011100 → 1001110)

    # Line 6: Return reversed bits
    return result
    # e.g., 964176192

This detailed breakdown clarifies how bit manipulation with shifts efficiently reverses bits.

Alternative: String Conversion Approach

Explanation

String Conversion reverses bits by:

• Convert n to 32-bit binary string.
• Reverse the string.
• Convert back to integer.

It’s a practical alternative, O(1) time (fixed 32 bits), O(1) space (fixed-size string), but less efficient due to string operations and not as “bit-level” as the manipulation approach.

For n = 43261596:

• Binary: "00000010100101000001111010011100".
• Reverse: "00111001011110000010100101000000".
• Integer: 964176192.

Step-by-Step Example (Alternative)

For n = 43261596:

• Step 1: Convert to binary string.
• bin(43261596)[2:].zfill(32) → "00000010100101000001111010011100".
• Step 2: Reverse string.
• "00111001011110000010100101000000".
• Step 3: Convert to integer.
• int("00111001011110000010100101000000", 2) → 964176192.
• Finish: Return 964176192.

How the Code Works (String Conversion)

Copy codedef reverseBitsString(n: int) -> int:
    # Convert to 32-bit binary string
    binary = bin(n)[2:].zfill(32)
    # e.g., "00000010100101000001111010011100"

    # Reverse string
    reversed_binary = binary[::-1]
    # e.g., "00111001011110000010100101000000"

    # Convert back to integer
    return int(reversed_binary, 2)
    # e.g., 964176192

Complexity

• Bit Manipulation with Shift:
• Time: O(1) – fixed 32 iterations.
• Space: O(1) – constant space.
• String Conversion:
• Time: O(1) – fixed 32-bit operations.
• Space: O(1) – fixed-size string.

Efficiency Notes

Bit Manipulation with Shift is the best solution with O(1) time and O(1) space, offering efficiency and directness without string overhead—String Conversion matches complexity but uses string operations, making it less efficient and less idiomatic for bit-level tasks, though simpler conceptually.

Key Insights

• Shift: Bit-by-bit build.
• String: Conversion shortcut.
• 32-Bit: Fixed length.

Additional Example

For n = 1 (00000000000000000000000000000001):

• Goal: 2147483648 (10000000000000000000000000000000).
• Shift: Build bit-by-bit → 2147483648.

Edge Cases

• All Zeros: 0 → 0.
• All Ones: 4294967295 → 4294967295.
• Single Bit: 1 → 2147483648.

Both solutions handle these well.

Final Thoughts

LeetCode 190: Reverse Bits in Python is a neat bit-manipulation challenge. The Bit Manipulation with Shift solution excels with its efficiency and elegance, while String Conversion offers a simpler (less efficient) approach. Want more? Try LeetCode 191: Number of 1 Bits for bit counting or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 190 on LeetCode with 43261596, aiming for 964176192—test your skills now!