Reverse Bits of a Number in DSA Python - Execution Trace

Concept Flow - Reverse Bits of a Number

Start with number n

↓

Initialize result = 0

↓

Repeat for each bit position i from 0 to 31

↓

Extract bit at position i from n

↓

Shift result left by 1

↓

Add extracted bit to result

↓

Move to next bit

↓

After 32 bits, return result

We take each bit from the original number starting from the least significant bit, and build the reversed number by shifting and adding bits one by one.

Execution Sample

DSA Python

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

This code reverses the bits of a 32-bit unsigned integer by extracting each bit and building the reversed number.

Execution Table

Step	Operation	Bit Extracted	Result Before	Result After	Visual State (bits)
1	Extract bit 0	1	00000000000000000000000000000000	00000000000000000000000000000001	00000000000000000000000000000001
2	Extract bit 1	0	00000000000000000000000000000010	00000000000000000000000000000010	00000000000000000000000000000010
3	Extract bit 2	1	00000000000000000000000000000101	00000000000000000000000000000101	00000000000000000000000000000101
4	Extract bit 3	0	00000000000000000000000000001010	00000000000000000000000000001010	00000000000000000000000000001010
5	Extract bit 4	1	00000000000000000000000000010101	00000000000000000000000000010101	00000000000000000000000000010101
6	Extract bit 5	0	00000000000000000000000000101010	00000000000000000000000000101010	00000000000000000000000000101010
7	Extract bit 6	0	00000000000000000000000001010100	00000000000000000000000001010100	00000000000000000000000001010100
8	Extract bit 7	0	00000000000000000000000010101000	00000000000000000000000010101000	00000000000000000000000010101000
9	Extract bit 8	0	00000000000000000000000101010000	00000000000000000000000101010000	00000000000000000000000101010000
10	Extract bit 9	0	00000000000000000000001010100000	00000000000000000000001010100000	00000000000000000000001010100000
11	Extract bit 10	0	00000000000000000000010101000000	00000000000000000000010101000000	00000000000000000000010101000000
12	Extract bit 11	0	00000000000000000000101010000000	00000000000000000000101010000000	00000000000000000000101010000000
13	Extract bit 12	0	00000000000000000001010100000000	00000000000000000001010100000000	00000000000000000001010100000000
14	Extract bit 13	0	00000000000000000010101000000000	00000000000000000010101000000000	00000000000000000010101000000000
15	Extract bit 14	0	00000000000000000101010000000000	00000000000000000101010000000000	00000000000000000101010000000000
16	Extract bit 15	0	00000000000000001010100000000000	00000000000000001010100000000000	00000000000000001010100000000000
17	Extract bit 16	0	00000000000000010101000000000000	00000000000000010101000000000000	00000000000000010101000000000000
18	Extract bit 17	0	00000000000000101010000000000000	00000000000000101010000000000000	00000000000000101010000000000000
19	Extract bit 18	0	00000000000001010100000000000000	00000000000001010100000000000000	00000000000001010100000000000000
20	Extract bit 19	0	00000000000010101000000000000000	00000000000010101000000000000000	00000000000010101000000000000000
21	Extract bit 20	0	00000000000101010000000000000000	00000000000101010000000000000000	00000000000101010000000000000000
22	Extract bit 21	0	00000000001010100000000000000000	00000000001010100000000000000000	00000000001010100000000000000000
23	Extract bit 22	0	00000000010101000000000000000000	00000000010101000000000000000000	00000000010101000000000000000000
24	Extract bit 23	0	00000000101010000000000000000000	00000000101010000000000000000000	00000000101010000000000000000000
25	Extract bit 24	0	00000001010100000000000000000000	00000001010100000000000000000000	00000001010100000000000000000000
26	Extract bit 25	0	00000010101000000000000000000000	00000010101000000000000000000000	00000010101000000000000000000000
27	Extract bit 26	0	00000101010000000000000000000000	00000101010000000000000000000000	00000101010000000000000000000000
28	Extract bit 27	0	00001010100000000000000000000000	00001010100000000000000000000000	00001010100000000000000000000000
29	Extract bit 28	0	00010101000000000000000000000000	00010101000000000000000000000000	00010101000000000000000000000000
30	Extract bit 29	0	00101010000000000000000000000000	00101010000000000000000000000000	00101010000000000000000000000000
31	Extract bit 30	0	01010100000000000000000000000000	01010100000000000000000000000000	01010100000000000000000000000000
32	Extract bit 31	0	10101000000000000000000000000000	10101000000000000000000000000000	10101000000000000000000000000000

💡 All 32 bits processed, loop ends

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	After 12	After 13	After 14	After 15	After 16	After 17	After 18	After 19	After 20	After 21	After 22	After 23	After 24	After 25	After 26	After 27	After 28	After 29	After 30	After 31	After 32	Final
result	00000000000000000000000000000000	00000000000000000000000000000001	00000000000000000000000000000010	00000000000000000000000000000101	00000000000000000000000000001010	00000000000000000000000000010101	00000000000000000000000000101010	00000000000000000000000001010100	00000000000000000000000010101000	00000000000000000000000101010000	00000000000000000000001010100000	00000000000000000000010101000000	00000000000000000000101010000000	00000000000000000001010100000000	00000000000000000010101000000000	00000000000000000101010000000000	00000000000000001010100000000000	00000000000000010101000000000000	00000000000000101010000000000000	00000000000001010100000000000000	00000000000010101000000000000000	00000000000101010000000000000000	00000000001010100000000000000000	00000000010101000000000000000000	00000000101010000000000000000000	00000001010100000000000000000000	00000010101000000000000000000000	00000101010000000000000000000000	00001010100000000000000000000000	00010101000000000000000000000000	00101010000000000000000000000000	01010100000000000000000000000000	10101000000000000000000000000000	10101000000000000000000000000000

Key Moments - 3 Insights

Why do we shift the result left before adding the extracted bit?

Because we build the reversed number from left to right, shifting left makes space for the new bit at the rightmost position. This is shown in execution_table rows where 'Result Before' is shifted left before adding 'Bit Extracted'.

Why do we extract bits from the original number using (n >> i) & 1?

This operation moves the bit at position i to the least significant bit and masks all others, isolating that single bit. The execution_table shows 'Bit Extracted' changing each step, confirming this extraction.

Why do we loop exactly 32 times?

Because we assume a 32-bit number, and each bit must be processed to reverse the entire bit pattern. The exit_note confirms the loop ends after 32 bits.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the 'Bit Extracted' value?

A 0

B 1

C 2

D None

💡 Hint

Check the 'Bit Extracted' column in row with Step 3 in execution_table.

At which step does the 'Result After' first become 00000000000000000000000000000101?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Result After' column in execution_table rows for the exact bit pattern.

If we change the loop to run only 16 times, what will happen to the 'Final' result?

A It will reverse only the lower 16 bits

B It will reverse all 32 bits

C It will produce zero

D It will cause an error

💡 Hint

Refer to the concept_flow and variable_tracker showing 32 iterations for full reversal.

Concept Snapshot

Reverse Bits of a Number:
- Loop 32 times for each bit
- Extract bit i with (n >> i) & 1
- Shift result left by 1
- Add extracted bit to result
- Return result after loop
- Reverses bit order of 32-bit integer

Full Transcript

This concept reverses the bits of a 32-bit number by extracting each bit from the original number starting from the least significant bit. For each bit, the result is shifted left to make space, then the extracted bit is added. This process repeats 32 times to cover all bits. The execution table shows each step with the bit extracted, the result before and after shifting and adding, and the visual bit pattern. The variable tracker follows the result variable's changes after each iteration. Key moments clarify why shifting is needed before adding bits, how bits are extracted, and why the loop runs 32 times. The visual quiz tests understanding of bit extraction, result changes, and effects of changing loop count.

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