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
- Initialize a variable
reversed_nto store the result, starting with 0. - Iterate over 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 innusing bitwise AND (n & (1 << i)). - Place this extracted bit into its reversed position in
reversed_nby shifting it to the correct position and then performing a bitwise OR. - 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
nis1, the output should be2147483648(binary10000000000000000000000000000000). - Mixed bits: The function handles any combination of bits correctly by reversing their positions.