Reverse Bits of a Number in DSA C++ - Execution Trace

Concept Flow - Reverse Bits of a Number

Start with input number n

↓

Initialize result = 0, count = 32

↓

Loop while count > 0

↓

Shift result left by 1

↓

Extract last bit of n

↓

Add extracted bit to result

↓

Shift n right by 1

↓

Decrement count

↓

Repeat loop

↓

Return result with bits reversed

We take each bit from the input number starting from the right, add it to the result shifted left, and repeat 32 times to reverse all bits.

Execution Sample

DSA C++

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    int count = 32;
    while (count--) {
        result <<= 1;
        result |= (n & 1);
        n >>= 1;
    }
    return result;
}

This code reverses the bits of a 32-bit unsigned integer by shifting and masking bits one by one.

Execution Table

Step	Operation	n (binary)	Extracted Bit	result (binary)	Pointer Changes	Visual State
1	Initialize	00000000000000000000000000001010	-	00000000000000000000000000000000	result=0, n=10	result=0b00000000000000000000000000000000
2	Shift result left	00000000000000000000000000001010	-	00000000000000000000000000000000	result <<=1	result=0b00000000000000000000000000000000
3	Extract last bit of n	00000000000000000000000000001010	0	00000000000000000000000000000000	bit = n & 1	bit=0
4	Add bit to result	00000000000000000000000000001010	0	00000000000000000000000000000000	result |= bit	result=0b00000000000000000000000000000000
5	Shift n right	00000000000000000000000000000101	-	00000000000000000000000000000000	n >>=1	n=0b00000000000000000000000000000101
6	Decrement count	-	-	-	count=31	-
7	Shift result left	00000000000000000000000000000101	-	00000000000000000000000000000000	result <<=1	result=0b00000000000000000000000000000000
8	Extract last bit of n	00000000000000000000000000000101	1	00000000000000000000000000000000	bit = n & 1	bit=1
9	Add bit to result	00000000000000000000000000000101	1	00000000000000000000000000000001	result |= bit	result=0b00000000000000000000000000000001
10	Shift n right	00000000000000000000000000000010	-	00000000000000000000000000000001	n >>=1	n=0b00000000000000000000000000000010
11	Decrement count	-	-	-	count=30	-
12	Shift result left	00000000000000000000000000000010	-	00000000000000000000000000000010	result <<=1	result=0b00000000000000000000000000000010
13	Extract last bit of n	00000000000000000000000000000010	0	00000000000000000000000000000010	bit = n & 1	bit=0
14	Add bit to result	00000000000000000000000000000010	0	00000000000000000000000000000010	result |= bit	result=0b00000000000000000000000000000010
15	Shift n right	00000000000000000000000000000001	-	00000000000000000000000000000010	n >>=1	n=0b00000000000000000000000000000001
16	Decrement count	-	-	-	count=29	-
17	Shift result left	00000000000000000000000000000001	-	00000000000000000000000000000100	result <<=1	result=0b00000000000000000000000000000100
18	Extract last bit of n	00000000000000000000000000000001	1	00000000000000000000000000000100	bit = n & 1	bit=1
19	Add bit to result	00000000000000000000000000000001	1	00000000000000000000000000000101	result |= bit	result=0b00000000000000000000000000000101
20	Shift n right	00000000000000000000000000000000	-	00000000000000000000000000000101	n >>=1	n=0b00000000000000000000000000000000
21	Decrement count	-	-	-	count=28	-
22	Shift result left	00000000000000000000000000000000	-	00000000000000000000000000001010	result <<=1	result=0b00000000000000000000000000001010
23	Extract last bit of n	00000000000000000000000000000000	0	00000000000000000000000000001010	bit = n & 1	bit=0
24	Add bit to result	00000000000000000000000000000000	0	00000000000000000000000000001010	result |= bit	result=0b00000000000000000000000000001010
25	Shift n right	00000000000000000000000000000000	-	00000000000000000000000000001010	n >>=1	n=0b00000000000000000000000000000000
26	Decrement count	-	-	-	count=27	-
27	Shift result left	00000000000000000000000000000000	-	00000000000000000000000000010100	result <<=1	result=0b00000000000000000000000000010100
28	Extract last bit of n	00000000000000000000000000000000	0	00000000000000000000000000010100	bit = n & 1	bit=0
29	Add bit to result	00000000000000000000000000000000	0	00000000000000000000000000010100	result |= bit	result=0b00000000000000000000000000010100
30	Shift n right	00000000000000000000000000000000	-	00000000000000000000000000010100	n >>=1	n=0b00000000000000000000000000000000
31	Decrement count	-	-	-	count=26	-
32	Loop continues until count=0	-	-	-	-	-
33	End loop	-	-	-	-	All 32 bits processed
34	Return result	-	-	01010000000000000000000000000000	-	Final reversed bits

💡 Loop ends after 32 iterations, all bits reversed

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	Final
n	00000000000000000000000000001010	00000000000000000000000000000101	00000000000000000000000000000010	00000000000000000000000000000001	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000
result	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000001	00000000000000000000000000000010	00000000000000000000000000000101	00000000000000000000000000001010	00000000000000000000000000010100	00000000000000000000000000101000	00000000000000000000000001010000	00000000000000000000000010100000	00000000000000000000000101000000	01010000000000000000000000000000
count	32	31	30	29	28	27	26	25	24	23	22	0

Key Moments - 3 Insights

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

Because shifting result left makes space for the new bit on the right. This is shown in execution_table rows 2 and 3 where result is shifted before adding the bit.

Why do we extract the last bit of n using (n & 1)?

Because (n & 1) isolates the rightmost bit of n. This is shown in execution_table row 3 where the extracted bit is taken from n's least significant bit.

Why do we shift n right after extracting the bit?

Shifting n right moves the next bit into the last position for extraction in the next loop. This is shown in execution_table row 5 where n is shifted right.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the binary value of result?

A 00000000000000000000000000000000

B 00000000000000000000000000000001

C 00000000000000000000000000000010

D 00000000000000000000000000000101

💡 Hint

Check the 'result (binary)' column at step 9 in execution_table.

At which step does n become zero in the execution_table?

A Step 15

B Step 25

C Step 20

D Step 30

💡 Hint

Look at the 'n (binary)' column and find when it changes to all zeros.

If we did not shift result left before adding the bit, what would happen?

A Result would accumulate bits in the wrong order

B Bits would be reversed correctly

C n would not change

D Count would not decrement

💡 Hint

Refer to key_moments about why shifting result left is necessary before adding bits.

Concept Snapshot

Reverse Bits of a Number:
- Initialize result=0, count=32
- Loop 32 times:
  - Shift result left by 1
  - Add last bit of n to result
  - Shift n right by 1
- Return result
This reverses all bits of a 32-bit number.

Full Transcript

This concept shows how to reverse the bits of a 32-bit unsigned integer. We start with the input number n and a result initialized to zero. We repeat 32 times: shift the result left to make space, extract the last bit of n using bitwise AND with 1, add this bit to the result, then shift n right to process the next bit. After 32 iterations, the result contains the bits of n in reverse order. The execution table traces each step, showing how n and result change in binary. Key moments clarify why shifting result left is needed before adding bits, and why we extract bits using n & 1. The visual quiz tests understanding of these steps. This method ensures all bits are reversed correctly.

Practice

1. What does reversing the bits of a number mean in binary representation?

easy

A. Adding 1 to the binary number

B. Changing all 0s to 1s and 1s to 0s

C. Shifting bits to the left by one position

D. Flipping the order of bits from left to right

Solution

1. Step 1: Understand bit order

   Bits are arranged from left (most significant) to right (least significant). Reversing means swapping their order.

2. Step 2: Differentiate from other operations

   Flipping bits means changing 0 to 1 or 1 to 0, which is different from reversing order.

3. Final Answer:

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

4. Quick Check:

   Reverse bits = flip order [OK]

Hint: Reverse bits means reverse order, not flip values [OK]

Common Mistakes:

• Confusing reversing bits with flipping bits
• Thinking reversing means shifting bits
• Assuming reversing adds or subtracts value

2. Which of the following C++ code snippets correctly reverses the bits of an 8-bit unsigned integer n?

easy

A. ```cpp
unsigned char reverseBits(unsigned char n) {
unsigned char result = 0;
for (int i = 0; i < 8; i++) {
result <<= 1;
result |= (n & 1);
n >>= 1;
}
return result;
}
```

B. ```cpp
unsigned char reverseBits(unsigned char n) {
unsigned char result = 0;
for (int i = 0; i < 8; i++) {
result |= (n & 1) << i;
n >>= 1;
}
return result;
}
```

C. ```cpp
unsigned char reverseBits(unsigned char n) {
unsigned char result = 0;
for (int i = 0; i < 8; i++) {
result <<= 1;
result |= ((n >> i) & 1);
}
return result;
}
```

D. ```cpp
unsigned char reverseBits(unsigned char n) {
unsigned char result = 0;
for (int i = 7; i >= 0; i--) {
result <<= 1;
result |= (n & 1);
n >>= 1;
}
return result;
}
```

Solution

1. Step 1: Analyze the loop and bit operations

   ```cpp unsigned char reverseBits(unsigned char n) { unsigned char result = 0; for (int i = 0; i < 8; i++) { result <<= 1; result |= (n & 1); n >>= 1; } return result; } ``` shifts result left, adds least significant bit of n, then shifts n right. This reverses bits correctly.

2. Step 2: Check other options for correctness

   ```cpp unsigned char reverseBits(unsigned char n) { unsigned char result = 0; for (int i = 0; i < 8; i++) { result |= (n & 1) << i; n >>= 1; } return result; } ``` does not reverse bits, it copies bits in same order. ```cpp unsigned char reverseBits(unsigned char n) { unsigned char result = 0; for (int i = 0; i < 8; i++) { result <<= 1; result |= ((n >> i) & 1); } return result; } ``` uses wrong bit extraction. ```cpp unsigned char reverseBits(unsigned char n) { unsigned char result = 0; for (int i = 7; i >= 0; i--) { result <<= 1; result |= (n & 1); n >>= 1; } return result; } ``` has wrong loop condition causing infinite loop if i-- is missing.

3. Final Answer:

   Option A code correctly reverses bits -> Option A

4. Quick Check:

   Shift result left + add LSB of n each step [OK]

Hint: Shift result left, add LSB of n, shift n right [OK]

Common Mistakes:

• Using wrong loop conditions causing infinite loops
• Not shifting result before adding bits
• Extracting bits incorrectly with wrong shifts

3. What is the output of the following C++ code snippet?

unsigned char reverseBits(unsigned char n) {
  unsigned char result = 0;
  for (int i = 0; i < 8; i++) {
    result <<= 1;
    result |= (n & 1);
    n >>= 1;
  }
  return result;
}

int main() {
  unsigned char n = 13; // binary 00001101
  unsigned char reversed = reverseBits(n);
  std::cout << (int)reversed << std::endl;
  return 0;
}

medium

A. 101

B. 176

C. 11

D. 208

Solution

1. Step 1: Convert 13 to binary and reverse bits

   13 in 8-bit binary is 00001101. Reversing bits gives 10110000.

2. Step 2: Convert reversed binary to decimal

   10110000 binary equals 128+32+16=176 decimal.

3. Final Answer:

   176 -> Option B

4. Quick Check:

   00001101 reversed = 10110000 = 176 [OK]

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

Common Mistakes:

• Confusing bit reversal with bit flipping
• Not casting unsigned char to int for output
• Misreading binary to decimal conversion

4. Identify the bug in this C++ function that attempts to reverse bits of a 4-bit number:

unsigned char reverseBits4(unsigned char n) {
  unsigned char result = 0;
  for (int i = 0; i <= 4; i++) {
    result <<= 1;
    result |= (n & 1);
    n >>= 1;
  }
  return result;
}

medium

A. Loop runs one extra time causing incorrect result

B. Bitwise OR operator is used incorrectly

C. Result is not shifted before OR operation

D. Function does not return a value

Solution

1. Step 1: Check loop range

   The loop runs from i=0 to i=4 inclusive, so 5 iterations instead of 4.

2. Step 2: Understand effect of extra iteration

   Extra iteration shifts result and adds an extra bit, corrupting the reversed bits.

3. Final Answer:

   Loop runs one extra time causing incorrect result -> Option A

4. Quick Check:

   Loop should run 4 times, not 5 [OK]

Hint: Use < instead of <= for loop count [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Forgetting to shift result before OR
• Ignoring return statement correctness

5. Given a 16-bit unsigned integer, how would you efficiently reverse its bits using a divide-and-conquer approach in C++?

hard

A. Use recursion to reverse bits by dividing number by 2 repeatedly

B. Use a loop to reverse bits one by one shifting result left each time

C. Swap bits in pairs, then nibbles, then bytes, then half-words using masks and shifts

D. Convert number to string, reverse string, then convert back to integer

Solution

1. Step 1: Understand divide-and-conquer bit reversal

   Divide bits into pairs, swap them; then groups of 4 bits (nibbles), swap; then bytes, then half-words.

2. Step 2: Use masks and shifts for efficient swapping

   Use bit masks to isolate groups and shift them to swap positions without looping over each bit.

3. Final Answer:

   Swap bits in pairs, then nibbles, then bytes, then half-words using masks and shifts -> Option C

4. Quick Check:

   Divide-and-conquer uses masks and shifts [OK]

Hint: Swap bits in groups using masks and shifts [OK]

Common Mistakes:

• Using slow bit-by-bit loops for large bit sizes
• Trying string conversion which is inefficient
• Misunderstanding recursion for bit reversal