#190

Easy

auto_awesomeDivide and Conquer plus Bit Manipulation

LeetCode Problem Workspace

Reverse Bits

Reverse a 32-bit unsigned integer by manipulating bits efficiently using a divide and conquer approach with careful bit shifts.

divide and conquer bit manipulation

Problem Statement

Given a 32-bit unsigned integer n, reverse all its bits and return the resulting integer. The input is guaranteed to be within the range of 0 to 2^31 - 2, and n is even, ensuring predictable behavior for bit manipulation operations.

For example, if n = 43261596, the reversed bits produce 964176192. If n = 2147483644, reversing its bits yields 1073741822. Implement a solution that leverages divide and conquer plus bit manipulation to achieve the reversal efficiently and correctly.

Examples

Example 1

Input: n = 43261596

Output: 964176192

Example 2

Input: n = 2147483644

Output: 1073741822

Constraints

0 <= n <= 231 - 2
n is even.

Solution Approach

Iterative Bit Swapping

Split the 32-bit integer into smaller segments, swap pairs of bits, then nibbles, bytes, and finally halves. Apply masks and shift operations at each level of the divide and conquer process to build the reversed integer progressively.

Recursive Divide and Conquer

Recursively divide the integer into left and right halves, reverse each half, then merge using bit shifts. This emphasizes understanding the hierarchical structure of bits and ensures correctness at each recursion depth.

Optimized Lookup Table

Precompute reversed values for 8-bit blocks and process the 32-bit integer in four chunks. This approach reduces repeated bitwise operations and aligns with the divide and conquer principle by handling smaller subproblems efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the chosen approach: iterative and recursive divide-and-conquer methods run in O(1) since the bit length is fixed at 32, while the lookup table method also achieves O(1) with faster constant-time operations. Space complexity varies: iterative uses O(1), recursive uses O(log32)=O(1) stack, and lookup table uses O(256) for precomputation.

What Interviewers Usually Probe

Expect candidates to recognize bit-level patterns and swap sequences.
Look for proper handling of masks and shifts without off-by-one errors.
Assess whether the candidate applies divide and conquer to sub-bit blocks correctly.

Common Pitfalls or Variants

Common pitfalls

Incorrectly swapping bits without using proper masks leading to wrong output.
Forgetting to handle all 32 bits consistently in iterative or recursive steps.
Misaligning left and right halves when merging, producing off-by-one bit errors.

Follow-up variants

Reverse bits for integers of arbitrary bit lengths, not limited to 32 bits.
Count the number of 1s after reversing bits to combine bit manipulation patterns.
Perform in-place bit reversal for arrays of integers using the same divide and conquer principle.

FAQ

What is the fastest way to reverse bits for a 32-bit integer?

Use a combination of divide and conquer with masks and shifts, or precompute a lookup table for 8-bit blocks to reduce operations.

Does the input always need to be even in the Reverse Bits problem?

The problem statement guarantees even integers, which simplifies some bit shift calculations, but solutions should still handle all 32 bits.

Can recursive approaches be used without hitting stack limits?

Yes, since the recursion depth is bounded by the fixed 32-bit length, stack usage remains minimal and safe.

What common mistakes should I avoid when reversing bits?

Avoid misaligned shifts, off-by-one swaps, and forgetting to handle all bit segments consistently in iterative or recursive merges.

How does divide and conquer specifically help in Reverse Bits?

It allows breaking the integer into smaller blocks, reversing each independently, and then combining them correctly, reducing mental and operational complexity.

terminal

Solution

Solution 1: Bit Manipulation

We can extract each bit of $n$ from the lowest bit to the highest bit, and then place it at the corresponding position of $\textit{ans}$.

1

2

3

4

5

6

7

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

Continue Practicing

#191 number of 1 bits #187 repeated dna sequences #201 bitwise and of numbers range