algoadvance

Reverse bits of a given 32 bits unsigned integer.

Example 1:

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

Example 2:

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

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 internal binary representation of the integer 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.

Clarifying Questions

1. Is the input always 32 bits?
   • Yes, the input is always a fixed-width 32-bit unsigned integer.
2. Can the input integer be negative?
   • No, the problem specifies the input is an unsigned integer, so it is always non-negative.
3. Is there a need to handle input and output in formats other than integers?
   • No, input and output are to be handled as integers, even though the problem describes them in binary for clarity.

Strategy

1. Initialize Output: Start with a result variable set to 0.
2. Iterate Over Bits: Iterate over each bit position from 0 to 31:
   • Extract the least significant bit (LSB) from the input number.
   • Append this bit to the result by shifting the result left and adding the extracted bit.
   • Right shift the input number to process the next bit.
3. Return Result: After processing all bits, return the reversed result.

This approach directly manipulates the bits using bitwise operations which is efficient and easy to understand.

Code

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for i in range(32):
            # Extract the LSB of n
            bit = n & 1
            # Shift result left and add the bit
            result = (result << 1) | bit
            # Shift n right to process the next bit
            n >>= 1
        return result

Time Complexity

• Time Complexity: O(1)
  • This is because the number of operations is fixed at 32, regardless of the input value. We always loop exactly 32 times.
• Space Complexity: O(1)
  • The memory usage does not grow with the input size, only a few integer variables are used.

This solution should efficiently handle the reversal of all 32 bits in a fixed time.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?