Reverse Bits of a Number in DSA C - Execution Trace

Concept Flow - Reverse Bits of a Number

Start with number n

↓

Initialize result = 0

↓

Loop 8 times

↓

Shift result left by 1

↓

Extract last bit of n

↓

Add extracted bit to result

↓

Shift n right by 1

↓

Repeat loop

↓

Return result with bits reversed

Start with the number, then for each of the 8 bits, shift the result left, add the last bit of the number, and shift the number right. Repeat until all bits are reversed.

Execution Sample

DSA C

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

This code reverses the bits of an 8-bit unsigned integer by shifting and masking bits.

Execution Table

Step	Operation	n (binary)	Extracted Bit	result (binary)	Visual State
1	Initialize result=0	00000000000000000000000000001010	-	00000000000000000000000000000000	result=0, n=10 (binary 1010)
2	Shift result left by 1	00000000000000000000000000001010	-	00000000000000000000000000000000	result=0
3	Extract last bit of n (n & 1)	00000000000000000000000000001010	0	00000000000000000000000000000000	bit=0
4	Add extracted bit to result	00000000000000000000000000001010	0	00000000000000000000000000000000	result=0
5	Shift n right by 1	00000000000000000000000000000101	-	00000000000000000000000000000000	n=5
6	Shift result left by 1	00000000000000000000000000000101	-	00000000000000000000000000000000	result=0
7	Extract last bit of n (n & 1)	00000000000000000000000000000101	1	00000000000000000000000000000000	bit=1
8	Add extracted bit to result	00000000000000000000000000000101	1	00000000000000000000000000000001	result=1
9	Shift n right by 1	00000000000000000000000000000010	-	00000000000000000000000000000001	n=2
10	Shift result left by 1	00000000000000000000000000000010	-	00000000000000000000000000000010	result=2
11	Extract last bit of n (n & 1)	00000000000000000000000000000010	0	00000000000000000000000000000010	bit=0
12	Add extracted bit to result	00000000000000000000000000000010	0	00000000000000000000000000000010	result=2
13	Shift n right by 1	00000000000000000000000000000001	-	00000000000000000000000000000010	n=1
14	Shift result left by 1	00000000000000000000000000000001	-	00000000000000000000000000000100	result=4
15	Extract last bit of n (n & 1)	00000000000000000000000000000001	1	00000000000000000000000000000100	bit=1
16	Add extracted bit to result	00000000000000000000000000000001	1	00000000000000000000000000000101	result=5
17	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000000000101	n=0
18	Shift result left by 1	00000000000000000000000000000000	-	00000000000000000000000000001010	result=10
19	Extract last bit of n (n & 1)	00000000000000000000000000000000	0	00000000000000000000000000001010	bit=0
20	Add extracted bit to result	00000000000000000000000000000000	0	00000000000000000000000000001010	result=10
21	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000000001010	n=0
22	Shift result left by 1	00000000000000000000000000000000	-	00000000000000000000000000010100	result=20
23	Extract last bit of n (n & 1)	00000000000000000000000000000000	0	00000000000000000000000000010100	bit=0
24	Add extracted bit to result	00000000000000000000000000000000	0	00000000000000000000000000010100	result=20
25	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000000010100	n=0
26	Shift result left by 1	00000000000000000000000000000000	-	00000000000000000000000000101000	result=40
27	Extract last bit of n (n & 1)	00000000000000000000000000000000	0	00000000000000000000000000101000	bit=0
28	Add extracted bit to result	00000000000000000000000000000000	0	00000000000000000000000000101000	result=40
29	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000000101000	n=0
30	Shift result left by 1	00000000000000000000000000000000	-	00000000000000000000000001010000	result=80
31	Extract last bit of n (n & 1)	00000000000000000000000000000000	0	00000000000000000000000001010000	bit=0
32	Add extracted bit to result	00000000000000000000000000000000	0	00000000000000000000000001010000	result=80
33	Shift n right by 1	00000000000000000000000000000000	-	00000000000000000000000001010000	n=0
34	Loop ends after 8 iterations	-	-	00000000000000000000000001010000	Final reversed bits result=80

💡 Loop ends after 8 iterations, all bits processed

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	Final
n	00000000000000000000000000001010 (10)	00000000000000000000000000000101 (5)	00000000000000000000000000000010 (2)	00000000000000000000000000000001 (1)	00000000000000000000000000000000 (0)	00000000000000000000000000000000 (0)
result	00000000000000000000000000000000 (0)	00000000000000000000000000000000 (0)	00000000000000000000000000000001 (1)	00000000000000000000000000000010 (2)	00000000000000000000000000000101 (5)	00000000000000000000000001010000 (80)
Extracted Bit	-	0	1	0	1	0

Key Moments - 3 Insights

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

Shifting result left makes room for the new bit on the right. This is shown in execution_table rows 2 and 6 where result is shifted before adding the bit in rows 4 and 8.

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

The expression (n & 1) isolates the least significant bit of n. This is the bit we add to result each iteration, as seen in execution_table rows 3, 7, 11, and 15.

What happens when n becomes zero before 8 iterations?

Even if n becomes zero early (row 17), the loop continues shifting result and adding zeros to complete 8 bits, ensuring all bits are reversed.

Visual Quiz - 3 Questions

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

A 00000000000000000000000000000001

B 00000000000000000000000000000010

C 00000000000000000000000000000000

D 00000000000000000000000000000101

💡 Hint

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

At which step does n first become zero according to the execution_table?

A Step 14

B Step 17

C Step 20

D Step 33

💡 Hint

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

If we did not shift result left before adding the extracted bit, how would the result change at step 8?

A Result would be 0

B Result would be 2

C Result would be 1

D Result would be 5

💡 Hint

Without shifting left, adding bit 1 would set result to 1 directly, check step 8 in execution_table.

Concept Snapshot

Reverse Bits of a Number:
- Initialize result = 0
- Loop 8 times:
  - Shift result left by 1
  - Add last bit of n (n & 1) to result
  - Shift n right by 1
- Return result with bits reversed

Full Transcript

This concept reverses the bits of an 8-bit unsigned integer. We start with the input number n and a result initialized to zero. For each of the 8 bits, we shift the result left by one to make space, then add the least significant bit of n to result. Next, we shift n right by one to process the next bit. This repeats 8 times to reverse all bits. The execution table shows each step with the binary states of n and result, and the extracted bit. Key moments clarify why shifting and masking are needed. The visual quiz tests understanding of intermediate states and effects of operations.

Practice

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

easy

A. Shifting bits to the left by one position

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

C. Flipping the order of bits from left to right

D. Adding 1 to the number

Solution

1. Step 1: Understand bit order

   Bits are arranged from left (most significant) to right (least significant).

2. Step 2: Reverse means flip order

   Reversing bits means the leftmost bit becomes rightmost, second leftmost becomes second rightmost, and so on.

3. Final Answer:

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

4. Quick Check:

   Reverse bits = flip order [OK]

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

Common Mistakes:

• Confusing reversing bits with bitwise NOT
• Thinking reversing bits adds or subtracts from number
• Mixing bit shifting with reversing bits

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

easy

A. unsigned char reverseBits(unsigned char n) { return n << 1; }

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

C. unsigned char reverseBits(unsigned char n) { return ~n; }

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

Solution

1. Step 1: Analyze the correct loop logic

   The loop shifts rev left by 1, ORs with (n & 1), then shifts n right by 1. This reverses bits correctly.

2. Step 2: Check distractor options

   rev |= (n & 1) << i; n >>= 1; copies bits in same order. return ~n; is bitwise NOT, not reverse. return n << 1; shifts bits left, not reverse.

3. Final Answer:

   rev <<= 1; rev |= (n & 1); n >>= 1; -> Option D

4. Quick Check:

   Shift rev left + add bit from n = reverse bits [OK]

Hint: Shift rev left, add n's LSB, shift n right each step [OK]

Common Mistakes:

• Using bitwise NOT (~) instead of reversing bits
• Not shifting rev before adding new bit
• Shifting bits incorrectly causing wrong order

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

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

int main() {
    unsigned char x = 13; // binary 00001101
    unsigned char y = reverseBits(x);
    printf("%u", y);
    return 0;
}

medium

A. 11

B. 176

C. 101

D. 13

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 = 128 + 32 + 16 = 176 decimal.

3. Final Answer:

   176 -> Option B

4. Quick Check:

   Reverse 00001101 = 10110000 = 176 [OK]

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

Common Mistakes:

• Confusing reversed bits with original number
• Calculating decimal incorrectly from binary
• Ignoring leading zeros in binary

4. Identify the error in the following C function that attempts to reverse bits of a 4-bit number:

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

medium

A. It does not shift rev left before adding bits, so bits are not reversed

B. It shifts n left instead of right

C. It uses 8-bit loop instead of 4-bit

D. It returns rev without masking bits

Solution

1. Step 1: Analyze bit addition logic

   The code adds bits to rev using rev |= (n & 1) << i, which places bits in original order, not reversed.

2. Step 2: Understand correct reversing method

   To reverse bits, rev should be shifted left before adding new bit, not ORed at position i.

3. Final Answer:

   It does not shift rev left before adding bits, so bits are not reversed -> Option A

4. Quick Check:

   Shift rev left before adding bit to reverse [OK]

Hint: Shift rev left before OR to reverse bits correctly [OK]

Common Mistakes:

• Adding bits at same positions without shifting rev
• Confusing left and right shifts on n
• Looping wrong number of times

5. You want to reverse the bits of a 16-bit unsigned integer and then check if the reversed number is a palindrome in binary (reads the same forwards and backwards). Which approach is correct?

hard

A. Reverse bits using a loop, then compare reversed number with original

B. Check if original number equals reversed number without reversing bits

C. Reverse bits using a loop, then reverse again and compare with original

D. Shift bits left by 8 and compare with original

Solution

1. Step 1: Compute reversed bits

   Reverse bits using a loop to obtain the reversed number rev.

2. Step 2: Check if reversed is palindrome

   The reversed number is a palindrome if it reads the same forwards and backwards, i.e., rev == original (since reverse(rev) == original always holds for a correct reverse).

3. Final Answer:

   Reverse bits using a loop, then compare reversed number with original -> Option A

4. Quick Check:

   rev == original means rev is palindrome [OK]

Hint: rev == original checks if reversed bits form a palindrome [OK]

Common Mistakes:

• Thinking double reverse checks palindrome (it only verifies the reverse function)
• Trying to check palindrome without computing reversed bits
• Confusing bit reversal with simple shifts