190. Reverse Bits - Explanation

Description

Given a 32-bit unsigned integer n, reverse the bits of the binary representation of n and return the result.

Example 1:

Input: n = 00000000000000000000000000010101

Output:    2818572288 (10101000000000000000000000000000)

Explanation: Reversing 00000000000000000000000000010101, which represents the unsigned integer 21, gives us 10101000000000000000000000000000 which represents the unsigned integer 2818572288.

Recommended Time & Space Complexity

You should aim for a solution with O(1) time and O(1) space.

Hint 1

Given a 32-bit integer, what is the position of bit i after reversing the bits? Maybe you should observe the bit positions before and after reversal to find a pattern.

Hint 2

After reversing the bits, the bit at position i moves to position 31 - i. Can you use this observation to construct the reversed number efficiently?

Hint 3

We initialize res to 0 and iterate through the bits of the given integer n. We extract the bit at the i-th position using ((n >> i) & 1). If it is 1, we set the corresponding bit in res at position (31 - i) using (res |= (1 << (31 - i))).

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def reverseBits(self, n: int) -> int:
        binary = ""
        for i in range(32):
            if n & (1 << i):
                binary += "1"
            else:
                binary += "0"

        res = 0
        for i, bit in enumerate(binary[::-1]):
            if bit == "1":
                res |= (1 << i)

        return res

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

2. Bit Manipulation

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for i in range(32):
            bit = (n >> i) & 1
            res += (bit << (31 - i))
        return res

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

3. Bit Manipulation (Optimal)

class Solution:
    def reverseBits(self, n: int) -> int:
        res = n
        res = (res >> 16) | (res << 16) & 0xFFFFFFFF
        res = ((res & 0xff00ff00) >> 8) | ((res & 0x00ff00ff) << 8)
        res = ((res & 0xf0f0f0f0) >> 4) | ((res & 0x0f0f0f0f) << 4)
        res = ((res & 0xcccccccc) >> 2) | ((res & 0x33333333) << 2)
        res = ((res & 0xaaaaaaaa) >> 1) | ((res & 0x55555555) << 1)
        return res & 0xFFFFFFFF

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$