Reverse Bits

Problem

https://leetcode.com/problems/reverse-bits/

Reverse bits of a given 32 bits unsigned integer.

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.

Pattern

Bit Manipulation

Approaches

Bit Manipulation

Explanation

We can reverse the bits by extracting the bit at each position \(i`\), then setting the \(32 - i`th bit in our reversed integer to that value. To extract the :math:`i`th bit is set we can use ``(i << 1) & n`\) which creates a bit string that is 0 everywhere except at position \(i\) by bitshifting, then bitwise ands it with \(n\). The result is 0 if \(n\) is 1 at bit \(i\) or \(2^i\) otherwise. If the result was positive, we can set the \(32 - i`th bit using ``ans |= i << (31 - i)`\) which moves 1 to position \(31 - i\) (or \(32 - i\) using 1 indexing) and bitwise ors it with the answer. The result is the original binary representation of ans with 1 at position \(31 - i\).

Code

def reverseBits(n: int) -> int:
    """Reverse the bits of a 32-bit unsigned integer."""
    result = 0
    for i in range(32):
        if (1 << i) & n:
            result |= 1 << (31 - i)
    return result

Test

>>> from reverse_bits__bit_manipulation import reverseBits
>>> reverseBits(43261596)
964176192
>>> reverseBits(4294967293)
3221225471

Complexity

\(n\) is the number of elements in nums

Measure	Complexity	Notes
Time	\(O(1)\)	integer only contains 32 integers
Auxiliary Space	\(O(1)\)	no variables other the arguments, loop variable, and return value

reverse_bits__bit_manipulation.reverseBits(n: int) → int: Reverse the bits of a 32-bit unsigned integer.