{x}
blog image

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

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 integer's internal binary representation 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.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • The input must be a binary string of length 32

 

Follow up: If this function is called many times, how would you optimize it?

Solution Explanation: Reversing Bits of an Integer

This problem requires reversing the bits of a 32-bit unsigned integer. The solutions presented utilize bit manipulation techniques for efficiency.

Approach:

The core idea is to iterate through the bits of the input integer, extracting each bit individually and placing it in its reversed position in the output integer.

  1. Initialization: We initialize a variable ans to 0. This variable will store the reversed bits.

  2. Iteration: The code iterates 32 times (since we have 32 bits). In each iteration:

    • (n & 1): This extracts the least significant bit (LSB) of n. The bitwise AND operation (&) with 1 isolates the LSB.

    • << (31 - i): This left-shifts the LSB by (31 - i) positions. This places the extracted bit in its correct reversed position in ans. The 31 - i calculation ensures that the LSB of n becomes the MSB of ans, the second LSB of n becomes the second MSB of ans, and so on.

    • ans |= ...: The bitwise OR operation (|=) combines the new bit with the existing bits in ans.

    • n >>= 1: This right-shifts n by one position. This effectively discards the processed LSB and moves the next bit to the LSB position for the next iteration. The >>= operator is a shorthand for n = n >> 1. Note that the unsigned right shift (>>>=) is crucial in Java and JavaScript to handle the sign bit correctly.

Time and Space Complexity:

  • Time Complexity: O(1) or O(n) where n is the number of bits (32 in this case). The loop iterates a fixed number of times (32), making the time complexity constant. Strictly speaking, it's O(log n) because the number of bits is proportional to the logarithm of the number. However, since the number of bits is fixed at 32, it's effectively O(1).

  • Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input size.

Code Examples:

The provided code examples demonstrate the approach in several programming languages. They all follow the same fundamental logic, differing only in syntax and data type handling. Key differences include using >>>= (unsigned right shift) in Java and JavaScript to avoid sign extension. C++ and Go naturally handle unsigned integers efficiently. Python uses integers and handles the bit manipulation implicitly. Rust leverages its unsigned integer type u32.

Optimization for Multiple Calls:

The follow-up question asks about optimization if the function is called many times. One optimization strategy would be to precompute the reversed bits for all possible 32-bit integers and store them in a lookup table. This would reduce the time complexity to O(1) for subsequent calls, trading off space complexity for time efficiency. However, this lookup table would require a significant amount of memory (232 entries). The practicality of this optimization depends on the constraints of memory usage.