190. Reverse Bits

Problem Statement in English

You’re given a 32 bit integer n. Your task is to reverse the bits in its binary representation and return the resulting number.

Step 1: Extract last bit from n

• Step 1.1: Use a bitwise AND operation to find if the last bit is $0$ or $1$:
  If we use a bitwise AND between a number and $1$, we end up with $0$ if the last bit of the number is $0$, and $1$ otherwise. For example:

  • 4 & 1 = 0, as $(4)_2 = 100$, and $(1)_2 = 1$. When we use bitwise AND, we get $0$.
  • 7 & 1 = 1, as $(7)_2 = 111$, and $(1)_2 = 1$. When we use bitwise AND, we get $1$.

• Step 1.2: Perform a right shift operation on n:
  This removes the last bit from n.

Step 2: Update buff

• Step 2.1: Use a right shift operation on buff in order to create a vacancy at its LSB (least significant bit):
  When we left shift a number, all its bits move left once, creating a new space at its LSB.

• Step 2.2: Use a bitwise OR to insert the extracted bit from ‘Step 1’ into the newly created space:
  The new LSB will always be $0$, as that’s what happens when you left shift a number. When we use a bitwise OR against that 0:

  • and try to insert a $1$,0 | 1 = 1
  • and try to insert a $0$,0 | 0 = 0

Step 3: Repeat until n is $0$

• Step 3.1: We need to have removed all the bits from n:
  

Step 4: Pad buff to get it to $32$ bits

• Step 4.1: If the number of bits in buff is less than $32$, keep padding with $0$s on the LSB:
  If the input number is, for example, $3$, then we only get 2 bits since $(3)_2 = 11$. But we need to have 32 bits, so we need to left shift buff $30$ more times.

Solution in Python

class Solution:
    def reverseBits(self, n: int) -> int:
        buff = 0
        temp = 0
        done = 0

        while n > 0:
            temp = n & 1
            n = n >> 1

            buff = buff << 1
            buff = buff | temp
            done += 1

        buff = buff << (32 - done)

        return buff

Complexity

• Time: $O(1)$
  Since we only need $32$ left shifts at most for n, and $32$ right shifts at most for buff.

• Space: $O(1)$
  We only use a couple integer variables.

And we are done.