Reverse Bits

Clarify the problem:

• The problem requires reversing the bits of a 32-bit unsigned integer.
• We need to implement a function that takes an integer as input and returns another integer with its bits reversed.

Analyze the problem:

• Input: An unsigned 32-bit integer.
• Output: Another unsigned 32-bit integer with its bits reversed.
• Constraints: None given.

Design an algorithm:

• We can use bit manipulation to reverse the bits of the integer.
• We will initialize a variable, result, to 0.
• We will iterate through each bit of the input integer using a loop.
• In each iteration, we will shift the bits of the result variable to the left by 1 and set the least significant bit to the current bit of the input integer.
• To extract the current bit of the input integer, we will use bitwise AND with 1.
• After processing all the bits, we will return the result variable.

Explain your approach:

• We will initialize a variable called result to 0.
• We will iterate through each bit of the input integer using a loop.
• In each iteration, we will shift the bits of the result variable to the left by 1 using the bitwise left shift operator <<.
• To extract the current bit of the input integer, we will use bitwise AND with 1, i.e., n & 1.
• We will set the least significant bit of the result variable to the current bit using the bitwise OR operator |.
• After processing all the bits, we will return the result variable.

Write clean and readable code:

python

def reverseBits(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n = n >> 1
    return result

Test your code:

python

# Test case 1
n = 43261596
# Binary representation of n: 00000010100101000001111010011100
# Binary representation of the reversed bits: 00111001011110000010100101000000
# Reversed bits decimal representation: 964176192
assert reverseBits(n) == 964176192

# Test case 2
n = 4294967293
# Binary representation of n: 11111111111111111111111111111101
# Binary representation of the reversed bits: 10111111111111111111111111111111
# Reversed bits decimal representation: 3221225471
assert reverseBits(n) == 3221225471

I chose these test cases to cover different scenarios:

• Test case 1 checks a random input number with non-zero bits in various positions.
• Test case 2 checks a maximum unsigned 32-bit integer with all bits set to 1.

Optimize if necessary:

• The given solution is already efficient with a time complexity of O(1) since we iterate through a fixed number of bits (32) regardless of the input value.
• There is no further optimization possible for this problem.

Handle error cases:

• The code assumes that the input is a valid 32-bit unsigned integer, but it does not handle cases where the input is not an integer or exceeds the 32-bit range.
• It is important to consider such cases in a real-world scenario.

Discuss complexity analysis:

• The time complexity of the solution is O(1) since we iterate through a fixed number of bits (32) regardless of the input value.
• The space complexity is O(1) as we only use a constant amount of additional space.
• The code solves the problem optimally without any significant trade-offs.