Reverse Bits

1
2
3
4
5
6
7
8
9

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0

        for _ in range(32):
            res = (res<<1) + (n&1)
            n>>=1

        return res

This code is implementing a binary reversal operation. It’s reversing the binary representation of an integer n over 32 bits and storing the result in res. Here’s a step-by-step breakdown:

  1. res = 0: This initializes res, which will hold the reversed binary number.

  2. for _ in range(32): This loop will run 32 times. The number 32 is used because we’re assuming n is a 32-bit integer.

  3. res = (res<<1) + (n&1): This is where the reversal happens. (n&1) gets the least significant bit of n (i.e., the rightmost bit). res<<1 shifts all bits in res one position to the left (equivalent to multiplying res by 2), making room for the new bit on the right. The new bit is added to res using the + operator. This effectively adds the least significant bit of n to the left side of res.

  4. n>>=1: This shifts all bits in n one position to the right (equivalent to integer division by 2), effectively removing the least significant bit. This is done after the least significant bit has been added to res, so that bit isn’t lost.

  5. return res: After the loop has run 32 times, res will hold the binary reversal of n, so res is returned.

So, if n was the binary number 1001 (which is 9 in decimal), res will be 1001 (which is also 9 in decimal). Notice how the least significant bit in n became the most significant bit in res, and the most significant bit in n became the least significant bit in res, which means the binary number was reversed.

Problem Classification

  1. Computer Science Fundamentals: The problem involves fundamental understanding of how computers store and handle data at a low level.

  2. Bit Manipulation: The problem involves understanding and performing operations on binary representations of numbers.

  3. Binary Number Operations: Specifically, the problem deals with reversing the binary representation of an integer.

  4. Bit Shifting and Bitwise Operations: The task requires the understanding and use of bit shifting (right and left) and bitwise operations like bitwise AND.

The specific usage of these concepts might vary depending upon the language and implementation.

Language Agnostic Coding Drills

Breaking down the problem of reversing the bits of a 32-bit unsigned integer into smaller units of learning, we can create the following drills:

  1. Understanding Binary Numbers: Familiarize yourself with binary numbers, their representation, and manipulation. This includes understanding how numbers are represented in bits and how to manually convert a decimal number to binary and vice versa.

  2. Bitwise Operations: Study bitwise operations including AND (&), OR (|), XOR (^), NOT (~), Left Shift (<<) and Right Shift (>>). Understand what these operations do and how they can be used to manipulate the bits in a number.

  3. Left Shift and Right Shift Operations: Dive deeper into shift operations, particularly understanding what happens when you left shift or right shift a number. Experiment with different examples to understand these operations thoroughly.

  4. Bit Masking: Understand the concept of bit masking, i.e., using bitwise operations to manipulate specific bits of a number.

  5. Iteration: Understand the concept of iteration in a loop. Understand the significance of the number of iterations matching the number of bits you are dealing with (32 in this case).

  6. Combining Operations: Practice combining these operations. For instance, shifting bits and then performing a bitwise AND operation.

The final solution combines all these smaller units. It initiates a result with 0 and then goes through a loop 32 times (since the number is a 32-bit integer). In each iteration, it shifts the result to the left by 1 bit (essentially multiplying it by 2), adds the least significant bit of n, and then right shifts n by 1 bit (essentially dividing it by 2). This way, it constructs the reverse of n bit by bit.

Targeted Drills in Python

  1. Understanding Binary Numbers: You can convert decimal to binary using bin and binary to decimal using int function in Python.
1
2
3
4
5
6
7
8
9

# Decimal to binary
decimal_number = 10
binary_number = bin(decimal_number)
print(f"Binary of {decimal_number} is {binary_number}")

# Binary to decimal
binary_number = '0b1010'
decimal_number = int(binary_number, 2)
print(f"Decimal of {binary_number} is {decimal_number}")
  1. Bitwise Operations:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# Declare numbers
a = 10  # Binary: 1010
b = 4   # Binary: 0100

# Bitwise AND
print(f"a & b = {a & b}")

# Bitwise OR
print(f"a | b = {a | b}")

# Bitwise XOR
print(f"a ^ b = {a ^ b}")

# Bitwise NOT
print(f"~a = {~a}")
  1. Left Shift and Right Shift Operations:
1
2
3
4
5
6
7

a = 10  # Binary: 1010

# Left Shift
print(f"a << 1 = {a << 1}")

# Right Shift
print(f"a >> 1 = {a >> 1}")
  1. Bit Masking:
1
2
3
4
5

a = 10  # Binary: 1010
mask = 2  # Binary: 0010

# Bitwise AND with mask
print(f"a & mask = {a & mask}")
  1. Iteration:
1
2
3

# Iterating over range 32 (representing 32 bits)
for i in range(32):
    print(i)
  1. Combining Operations:
1
2
3
4
5
6
7
8

n = 10  # Binary: 1010
res = 0

# Iterating over range 32 (representing 32 bits)
for _ in range(32):
    res = (res << 1) + (n & 1)
    n >>= 1
print(res)

The last example is essentially the solution to the problem. It shows how these individual units combine to solve the problem.