Reverse Bits of a Number in DSA Python

Mental Model

Flip the order of bits in a number so the last bit becomes first and the first becomes last.

Analogy: Imagine a row of light switches turned on or off. Reversing bits is like walking from the end of the row back to the start, flipping the order of the switches exactly.

Original bits: 0 0 0 0 1 1 0 1
Reversed bits: 1 0 1 1 0 0 0 0

Dry Run Walkthrough

Input: number = 13 (binary 00001101), reverse all 8 bits

Goal: Get the number whose bits are reversed: 10110000 (binary) = 176 decimal

Step 1: Extract least significant bit (LSB) 1 and add to result

result=1 (binary 00000001), number shifted right to 00000110

Why: Start building reversed number from rightmost bit

Step 2: Shift result left and add next LSB 0

result=2 (binary 00000010), number shifted right to 00000011

Why: Make room for next bit and add it

Step 3: Shift result left and add next LSB 1

result=5 (binary 00000101), number shifted right to 00000001

Why: Add next bit in reversed order

Step 4: Shift result left and add next LSB 1

result=11 (binary 00001011), number shifted right to 00000000

Why: Add next bit; number now zero

Step 5: Shift result left and add 0 (since number is zero, bits are zero)

result=22 (binary 00010110)

Why: Fill remaining bits with zeros

Step 6: Shift result left and add 0

result=44 (binary 00101100)

Why: Continue filling zeros

Step 7: Shift result left and add 0

result=88 (binary 01011000)

Why: Continue filling zeros

Step 8: Shift result left and add 0

result=176 (binary 10110000)

Why: Final reversed bits complete

Result:

Reversed bits: 10110000 (binary) = 176 decimal

Annotated Code

DSA Python

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for _ in range(8):  # fixed 8 bits for this example
            result <<= 1  # shift result left to make room for next bit
            result |= n & 1  # add least significant bit of n to result
            n >>= 1  # shift n right to process next bit
        return result

# Driver code
sol = Solution()
input_number = 13
output = sol.reverseBits(input_number)
print(output)

result <<= 1 # shift result left to make room for next bit

shift reversed bits left to add new bit

result |= n & 1 # add least significant bit of n to result

extract current bit from n and add to result

n >>= 1 # shift n right to process next bit

move to next bit in original number

Output

176

Complexity Analysis

Time: O(k) because we process each of the k bits once (here k=8)

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach might convert to string and reverse, which uses extra space and is slower; bitwise approach is efficient and constant space

Edge Cases

number = 0 (all bits zero)

result is 0 after reversal

DSA Python

for _ in range(8):

number = 255 (all bits one for 8 bits)

result is 255 after reversal (same bits)

DSA Python

for _ in range(8):

number with leading zeros like 1 (00000001)

result reverses bits correctly to 128 (10000000)

DSA Python

for _ in range(8):

When to Use This Pattern

When you need to reverse the order of bits in a number, use bitwise shifting and masking to build the reversed number efficiently.

Common Mistakes

Mistake: Not shifting the result left before adding the new bit, causing bits to overwrite
Fix: Always shift result left before OR-ing the next bit

Mistake: Looping fewer or more times than the bit length, causing incorrect reversal
Fix: Loop exactly the number of bits you want to reverse (e.g., 8 or 32)

Summary

Reverses the bits of a number by shifting and masking each bit.

Use when you need the mirror image of bits in a fixed-size number.

Shift the result left before adding each bit from the original number to build reversed bits.

Practice

1. What does reversing the bits of a number mean in simple terms?

easy

A. Multiplying the number by 2

B. Changing all 0 bits to 1 bits

C. Flipping the order of all bits from left to right

D. Adding 1 to the number

Solution

1. Step 1: Understand bits as binary digits

   Bits are the 0s and 1s that make up a number in binary form.

2. Step 2: Define reversing bits

   Reversing bits means reading the bits from right to left instead of left to right, flipping their order.

3. Final Answer:

   Flipping the order of all bits from left to right -> Option C

4. Quick Check:

   Reverse bits = flip order [OK]

Hint: Think of bits as beads on a string flipped end to end [OK]

Common Mistakes:

• Confusing reversing bits with flipping bits (0 to 1)
• Thinking reversing bits means adding or multiplying
• Assuming reversing bits changes the number's value directly

2. Which of the following Python code snippets correctly reverses the bits of an 8-bit number n?

easy

A. reversed_num = 0
for i in range(8):
reversed_num |= ((n >> i) & 1) << (7 - i)

B. reversed_num = 0
for i in range(8):
reversed_num |= ((n << i) & 1) << i

C. reversed_num = n << 8

D. reversed_num = n >> 8

Solution

1. Step 1: Analyze bit extraction and placement

   reversed_num = 0 for i in range(8): reversed_num |= ((n >> i) & 1) << (7 - i) extracts each bit from right to left and places it reversed from left to right.

2. Step 2: Check other options for correctness

   reversed_num = 0 for i in range(8): reversed_num |= ((n << i) & 1) << i shifts bits incorrectly; C and D just shift without reversing bits.

3. Final Answer:

   Option A code correctly reverses bits -> Option A

4. Quick Check:

   Shift right, mask, shift left reversed position [OK]

Hint: Use bit shifts and masks to pick and place bits reversed [OK]

Common Mistakes:

• Using left shift instead of right shift to extract bits
• Not shifting bits to reversed positions
• Confusing bitwise OR with addition

3. What is the output of the following Python code?

def reverse_bits(n):
    result = 0
    for i in range(4):
        result |= ((n >> i) & 1) << (3 - i)
    return result

print(reverse_bits(13))  # 13 in binary is 1101

medium

A. 13

B. 7

C. 14

D. 11

Solution

1. Step 1: Convert 13 to 4-bit binary and reverse bits

   13 in 4 bits is 1101. Reversing bits: 1011.

2. Step 2: Convert reversed bits back to decimal

   1011 in binary is 8+0+2+1 = 11.

3. Final Answer:

   11 -> Option D

4. Quick Check:

   1101 reversed = 1011 = 11 [OK]

Hint: Reverse bits visually, then convert back to decimal [OK]

Common Mistakes:

• Not reversing bits correctly (reading left to right)
• Confusing binary to decimal conversion
• Using wrong bit length for reversal

4. Find the error in this code that attempts to reverse bits of a 3-bit number n:

def reverse_bits(n):
    result = 0
    for i in range(3):
        bit = (n >> i) & 1
        result |= bit << i
    return result

medium

A. It uses wrong bitwise AND operator

B. It shifts bits to the same position instead of reversed position

C. It does not initialize result to zero

D. It uses range(3) instead of range(4)

Solution

1. Step 1: Check bit shifting logic

   The code shifts extracted bits back to the same position i, not reversed (2 - i).

2. Step 2: Identify correct reversed position

   For 3 bits, reversed position should be (2 - i) to flip bits order.

3. Final Answer:

   It shifts bits to the same position instead of reversed position -> Option B

4. Quick Check:

   Shift bits to reversed index, not original [OK]

Hint: Shift bits to (bit_length - 1 - i) for reversal [OK]

Common Mistakes:

• Shifting bits back to original position
• Forgetting to reverse bit positions
• Incorrect loop range for bit length

5. You want to reverse the bits of a 5-bit number n and then add it to the original number. Which Python code correctly does this?

hard

A. def reverse_bits(n):
result = 0
for i in range(5):
result |= ((n >> i) & 1) << (4 - i)
return result

print(n + reverse_bits(n))

B. def reverse_bits(n):
result = 0
for i in range(5):
result |= ((n << i) & 1) << i
return result

print(n - reverse_bits(n))

C. def reverse_bits(n):
return n << 5

print(n + reverse_bits(n))

D. def reverse_bits(n):
return n >> 5

print(n + reverse_bits(n))

Solution

1. Step 1: Verify bit reversal logic for 5 bits

   def reverse_bits(n): result = 0 for i in range(5): result |= ((n >> i) & 1) << (4 - i) return result print(n + reverse_bits(n)) correctly reverses bits by shifting each bit from position i to (4 - i).

2. Step 2: Check addition of reversed bits to original

   def reverse_bits(n): result = 0 for i in range(5): result |= ((n >> i) & 1) << (4 - i) return result print(n + reverse_bits(n)) prints sum of n and reversed bits, matching the problem requirement.

3. Final Answer:

   Option A code correctly reverses bits and adds to original -> Option A

4. Quick Check:

   Reverse bits with correct shifts, then add [OK]

Hint: Reverse bits by shifting to (bit_length - 1 - i), then add [OK]

Common Mistakes:

• Using left shift instead of right shift for extraction
• Subtracting instead of adding reversed bits
• Incorrect bit length or shift positions