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

Concept Flow - Reverse Bits of a Number

Start with input number

↓

Initialize result = 0, count = 32

↓

Loop while count > 0

↓

Shift result left by 1

↓

Extract rightmost bit of input

↓

Add extracted bit to result

↓

Shift input right by 1

↓

Decrement count

↓

Repeat loop

↓

Return result with bits reversed

We take each bit from the input number from right to left and build the reversed number by shifting and adding bits one by one.

Execution Sample

DSA C#

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

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

Execution Table

Step	Operation	Input (n)	Result (binary)	Extracted Bit	Result (decimal)
1	Initialize result=0, count=32	00000000000000000000000000000001	00000000000000000000000000000000	N/A	0
2	Shift result left by 1	00000000000000000000000000000001	00000000000000000000000000000000	N/A	0
3	Extract rightmost bit of n (n & 1)	00000000000000000000000000000001	00000000000000000000000000000000	1	0
4	Add extracted bit to result (result |= bit)	00000000000000000000000000000001	00000000000000000000000000000001	1	1
5	Shift n right by 1	00000000000000000000000000000000	00000000000000000000000000000001	N/A	1
6	Decrement count to 31	00000000000000000000000000000000	00000000000000000000000000000001	N/A	1
7	Shift result left by 1	00000000000000000000000000000000	00000000000000000000000000000010	N/A	2
8	Extract rightmost bit of n (n & 1)	00000000000000000000000000000000	00000000000000000000000000000010	0	2
9	Add extracted bit to result (result |= bit)	00000000000000000000000000000000	00000000000000000000000000000010	0	2
10	Shift n right by 1	00000000000000000000000000000000	00000000000000000000000000000010	N/A	2
11	Decrement count to 30	00000000000000000000000000000000	00000000000000000000000000000010	N/A	2
12	Shift result left by 1	00000000000000000000000000000000	00000000000000000000000000000100	N/A	4
13	Extract rightmost bit of n (n & 1)	00000000000000000000000000000000	00000000000000000000000000000100	0	4
14	Add extracted bit to result (result |= bit)	00000000000000000000000000000000	00000000000000000000000000000100	0	4
15	Shift n right by 1	00000000000000000000000000000000	00000000000000000000000000000100	N/A	4
16	Decrement count to 29	00000000000000000000000000000000	00000000000000000000000000000100	N/A	4
31	Shift result left by 1	00000000000000000000000000000000	10000000000000000000000000000000	N/A	2147483648
32	Extract rightmost bit of n (n & 1)	00000000000000000000000000000000	10000000000000000000000000000000	0	2147483648
33	Add extracted bit to result (result |= bit)	00000000000000000000000000000000	10000000000000000000000000000000	0	2147483648
34	Shift n right by 1	00000000000000000000000000000000	10000000000000000000000000000000	N/A	2147483648
35	Decrement count to 0	00000000000000000000000000000000	10000000000000000000000000000000	N/A	2147483648
36	Return result	00000000000000000000000000000000	10000000000000000000000000000000	N/A	2147483648

💡 Count reaches 0, 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	Final
n	00000000000000000000000000000001	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000000
result	00000000000000000000000000000000	00000000000000000000000000000000	00000000000000000000000000000001	00000000000000000000000000000010	00000000000000000000000000000100	00000000000000000000000000001000	00000000000000000000000000010000	00000000000000000000000000100000	00000000000000000000000001000000	10000000000000000000000000000000
count	32	31	30	29	28	27	26	25	24	0

Key Moments - 3 Insights

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

Because shifting left makes room for the new bit at the rightmost position. This is shown in execution_table rows 2 and 4 where result is shifted before OR-ing the extracted bit.

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

Because (n & 1) isolates the least significant bit of n. This is shown in execution_table row 3 where the extracted bit is 1 or 0 depending on n's last bit.

Why do we shift n right after extracting the bit?

To move the next bit into the rightmost position for the next iteration. This is shown in execution_table row 5 where n is shifted right to prepare for the next bit extraction.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the decimal value of result after adding the extracted bit?

A 2

B 0

C 1

D 4

💡 Hint

Check the 'Result (decimal)' column at step 4 in execution_table

At which step does the count reach zero and the loop ends?

A Step 32

B Step 35

C Step 36

D Step 30

💡 Hint

Look at the 'exit_note' and the 'count' variable in variable_tracker for when count becomes 0

If the input number n was 0 instead of 1, what would be the final result?

A 0

B 1

C 4294967295

D 2147483648

💡 Hint

If n is 0, all extracted bits are 0, so result remains 0 throughout (see how bits are extracted in execution_table)

Concept Snapshot

Reverse Bits of a Number:
- Initialize result=0 and count=32
- Loop: shift result left by 1
- Extract rightmost bit of input (n & 1)
- Add extracted bit to result
- Shift input right by 1
- Decrement count
- Repeat until count=0
- Return result with bits reversed

Full Transcript

This concept shows how to reverse the bits of a 32-bit unsigned integer. We start with the input number and an empty result. We repeat 32 times: shift the result left to make space, extract the rightmost bit of the input, add it to the result, then shift the input right to process the next bit. After all bits are processed, the result contains the reversed bits of the original number.

Practice

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

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).

2. Step 2: Reverse means flip order

   Reversing bits means the leftmost bit becomes rightmost and vice versa.

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 flip their order, not invert values [OK]

Common Mistakes:

• Confusing reversing bits with bitwise NOT (inverting bits)
• Thinking reversing means shifting bits
• Assuming reversing adds or subtracts from the number

2. Which of the following C# code snippets correctly reverses the bits of a 4-bit number stored in an integer variable n?

easy

A. int reversed = 0; for(int i=0; i<4; i++) { reversed <<= 1; reversed |= (n & 1); n >>= 1; }

B. int reversed = 0; for(int i=0; i<4; i++) { reversed |= (n & 1) << i; n >>= 1; }

C. int reversed = n << 4;

D. int reversed = ~n;

Solution

1. Step 1: Analyze the loop logic in int reversed = 0; for(int i=0; i<4; i++) { reversed <<= 1; reversed |= (n & 1); n >>= 1; }

   It shifts reversed left by 1, adds least bit of n, then shifts n right by 1, effectively reversing bits.

2. Step 2: Check other options

   int reversed = 0; for(int i=0; i<4; i++) { reversed |= (n & 1) << i; n >>= 1; } does not reverse bits, it copies bits in same order. int reversed = n << 4; shifts bits left, not reverse. int reversed = ~n; inverts bits, not reverse.

3. Final Answer:

   Option A code correctly reverses bits -> Option A

4. Quick Check:

   Shift left + OR + shift right = reverse bits [OK]

Hint: Shift reversed left, OR with last bit, shift input right [OK]

Common Mistakes:

• Using bitwise NOT (~) instead of reversing bits
• Shifting bits without combining properly
• Not updating reversed variable inside loop

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

int n = 13; // binary 1101
int reversed = 0;
for (int i = 0; i < 4; i++) {
  reversed <<= 1;
  reversed |= (n & 1);
  n >>= 1;
}
Console.WriteLine(reversed);

medium

A. 11

B. 7

C. 13

D. 14

Solution

1. Step 1: Convert 13 to 4-bit binary

   13 in binary (4 bits) is 1101.

2. Step 2: Reverse bits step-by-step

   Bits: 1 1 0 1 reversed: 1 0 1 1 which is binary 1011 = decimal 11.

3. Final Answer:

   11 -> Option A

4. Quick Check:

   1101 reversed = 1011 = 11 [OK]

Hint: Reverse bits manually and convert to decimal [OK]

Common Mistakes:

• Not limiting to 4 bits, causing wrong output
• Confusing bit order when reversing
• Assuming reversed number equals original

4. Identify the error in the following C# code that attempts to reverse bits of an 8-bit number:

int ReverseBits(int n) {
  int reversed = 0;
  for (int i = 0; i < 8; i++) {
    reversed |= (n & 1) << i;
    n >>= 1;
  }
  return reversed;
}

medium

A. The variable reversed should be initialized to 1

B. The loop should run 16 times for 8-bit numbers

C. The bits are not reversed; they are copied in the same order

D. The shift operator << is used incorrectly

Solution

1. Step 1: Analyze bit placement in loop

   The code places bits at increasing positions without reversing order.

2. Step 2: Understand reversing bits logic

   Reversing requires shifting reversed left and OR with last bit, not shifting bits by i.

3. Final Answer:

   The bits are not reversed; they are copied in the same order -> Option C

4. Quick Check:

   Shifting bits by i copies order, not reverse [OK]

Hint: Reversing needs shifting reversed left each step, not shifting bits by i [OK]

Common Mistakes:

• Using bit shift by loop index instead of shifting reversed
• Incorrect loop count for bit size
• Initializing reversed incorrectly

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 correctly combines reversing bits and palindrome check?

hard

A. Invert bits using bitwise NOT, then check if inverted equals original

B. Reverse bits using a loop shifting reversed left and OR with last bit, then compare reversed with original

C. Shift original number left by 16 bits, then compare with original

D. Reverse bits by shifting bits by index, then check if reversed equals original

Solution

1. Step 1: Reverse bits correctly

   Use loop to shift reversed left, OR with last bit of original, shift original right.

2. Step 2: Check palindrome by comparing reversed and original

   If reversed equals original, bits form a palindrome.

3. Final Answer:

   Reverse bits using a loop shifting reversed left and OR with last bit, then compare reversed with original -> Option B

4. Quick Check:

   Reverse bits + compare = palindrome check [OK]

Hint: Reverse bits properly, then compare to original for palindrome [OK]

Common Mistakes:

• Using bitwise NOT instead of reversing bits
• Shifting bits incorrectly causing wrong reverse
• Comparing inverted bits instead of reversed bits