Reverse Bits of a Number in DSA Typescript - Execution Trace

Concept Flow - Reverse Bits of a Number

Start with number n

↓

Initialize result = 0

↓

Loop 32 times

↓

Extract last bit of n

↓

Shift result left by 1

↓

Add extracted bit to result

↓

Shift n right by 1

↓

Repeat until 32 bits processed

↓

Return result

We take each bit from the original number from right to left, add it to the result from left to right, repeating 32 times to reverse all bits.

Execution Sample

DSA Typescript

function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>>= 1;
  }
  return result;
}

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

Execution Table

Step	Operation	n (binary)	Extracted Bit	result (binary)	Visual State
1	Initialize result=0	00000000000000000000000000001011	-	00000000000000000000000000000000	result=0, n=11 (decimal)
2	Extract last bit (n & 1)	00000000000000000000000000001011	1	00000000000000000000000000000001	result=1 after shift and add bit 1
3	Shift n right (n >>>= 1)	00000000000000000000000000000101	-	00000000000000000000000000000001	n=5
4	Extract last bit (n & 1)	00000000000000000000000000000101	1	00000000000000000000000000000011	result=3 after shift and add bit 1
5	Shift n right (n >>>= 1)	00000000000000000000000000000010	-	00000000000000000000000000000011	n=2
6	Extract last bit (n & 1)	00000000000000000000000000000010	0	00000000000000000000000000000110	result=6 after shift and add bit 0
7	Shift n right (n >>>= 1)	00000000000000000000000000000001	-	00000000000000000000000000000110	n=1
8	Extract last bit (n & 1)	00000000000000000000000000000001	1	00000000000000000000000000001101	result=13 after shift and add bit 1
9	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000000000000000001101	n=0
10	Extract last bit (n & 1)	00000000000000000000000000000000	0	00000000000000000000000000011010	result=26 after shift and add bit 0
11	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000000000000000011010	n=0
12	Extract last bit (n & 1)	00000000000000000000000000000000	0	00000000000000000000000000110100	result=52 after shift and add bit 0
13	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000000000000000110100	n=0
14	Extract last bit (n & 1)	00000000000000000000000000000000	0	00000000000000000000000001101000	result=104 after shift and add bit 0
15	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000000000000001101000	n=0
16	Extract last bit (n & 1)	00000000000000000000000000000000	0	00000000000000000000000011010000	result=208 after shift and add bit 0
17	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000000000000011010000	n=0
18	Extract last bit (n & 1)	00000000000000000000000000000000	0	00000000000000000000000110100000	result=416 after shift and add bit 0
19	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000000000000110100000	n=0
20	Extract last bit (n & 1)	00000000000000000000000000000000	0	00000000000000000000001101000000	result=832 after shift and add bit 0
21	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000000000001101000000	n=0
22	Extract last bit (n & 1)	00000000000000000000000000000000	0	00000000000000000000011010000000	result=1664 after shift and add bit 0
23	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000000000011010000000	n=0
24	Extract last bit (n & 1)	00000000000000000000000000000000	0	00000000000000000000110100000000	result=3328 after shift and add bit 0
25	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000000000110100000000	n=0
26	Extract last bit (n & 1)	00000000000000000000000000000000	0	00000000000000000001101000000000	result=6656 after shift and add bit 0
27	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000000001101000000000	n=0
28	Extract last bit (n & 1)	00000000000000000000000000000000	0	00000000000000000011010000000000	result=13312 after shift and add bit 0
29	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000000011010000000000	n=0
30	Extract last bit (n & 1)	00000000000000000000000000000000	0	00000000000000000110100000000000	result=26624 after shift and add bit 0
31	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000000110100000000000	n=0
32	Extract last bit (n & 1)	00000000000000000000000000000000	0	00000000000000001101000000000000	result=53248 after shift and add bit 0
33	Shift n right (n >>>= 1)	00000000000000000000000000000000	-	00000000000000001101000000000000	n=0
34	End of loop	-	-	00000000000000001101000000000000	Return result = 53248 (decimal)

💡 Loop ends after 32 steps, all bits processed and 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	00000000000000000000000000001011 (11)	00000000000000000000000000000101 (5)	00000000000000000000000000000010 (2)	00000000000000000000000000000001 (1)	00000000000000000000000000000000 (0)	0	0	0	0	0	0	0
result	00000000000000000000000000000000 (0)	00000000000000000000000000000001 (1)	00000000000000000000000000000011 (3)	00000000000000000000000000000110 (6)	00000000000000000000000000001101 (13)	00000000000000000000000000011010 (26)	00000000000000000000000000110100 (52)	00000000000000000000000001101000 (104)	00000000000000000000000011010000 (208)	00000000000000000000000110100000 (416)	00000000000000000000001101000000 (832)	00000000000000001101000000000000 (53248)

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. See execution_table steps 2, 4, 6 where result shifts before adding bit.

Why do we use unsigned right shift (>>>) on n instead of signed right shift (>>)?

Unsigned right shift fills left bits with zeros, preserving the bit pattern for unsigned numbers. Signed shift could fill with 1s if the number is negative, corrupting the bit reversal. See variable_tracker for n changes.

What happens when n becomes zero before 32 iterations are done?

We continue shifting zeros into result to complete 32 bits. This ensures the reversed number has all bits accounted for. See execution_table steps 9 to 33 where n=0 but loop continues.

Visual Quiz - 3 Questions

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

A 00000000000000000000000000000011

B 00000000000000000000000000000010

C 00000000000000000000000000000001

D 00000000000000000000000000000100

💡 Hint

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

At which step does n become zero for the first time?

A Step 7

B Step 9

C Step 10

D Step 8

💡 Hint

Look at the 'n (binary)' column in execution_table and variable_tracker to find when n is all zeros.

If we change the loop to run only 16 times, how would the final result change?

A Only the first 16 bits would be reversed, the rest remain zero

B All 32 bits would still be reversed correctly

C The result would be the same as original n

D The function would return zero

💡 Hint

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

Concept Snapshot

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

Full Transcript

This concept reverses the bits of a 32-bit unsigned integer. We start with the input number n and an empty result. Each step extracts the last bit of n, shifts the result left to make space, adds the extracted bit, then shifts n right to process the next bit. This repeats 32 times to cover all bits. The final result is the input number with bits reversed. The execution table shows each step's bit extraction, shifts, and updated values. The variable tracker follows n and result changes. Key moments clarify why shifting is done in a certain order, why unsigned shift is used, and what happens when n becomes zero early. The visual quiz tests understanding of intermediate states and effects of changing loop count.

Practice

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

easy

A. Changing all 0 bits to 1 bits

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

C. Adding 1 to the number

D. Shifting bits to the left by one position

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 all bits from left to right -> Option B

4. Quick Check:

   Reverse bits = flip order [OK]

Hint: Reverse bits means flip their order from left to right [OK]

Common Mistakes:

• Thinking reversing bits means changing 0 to 1
• Confusing reversing bits with shifting bits
• Assuming reversing bits adds or subtracts from number

2. Which TypeScript code snippet correctly reverses the bits of an 8-bit number n?

easy

A. let result = 0; for(let i=0; i<8; i++) { result |= ((n >> i) & 1) << (7 - i); }

B. let result = 0; for(let i=0; i<8; i++) { result |= ((n << i) & 1) << i; }

C. let result = 0; for(let i=0; i<8; i++) { result += (n & 1) << i; n >>= 1; }

D. let result = 0; for(let i = 0; i < 8; i++) { result |= (n & 1) << i; n >>= 1; }

Solution

1. Step 1: Analyze bit extraction and placement

   let result = 0; for(let i=0; i<8; i++) { result |= ((n >> i) & 1) << (7 - i); } extracts each bit from right to left and places it reversed from left to right correctly.

2. Step 2: Check other options

   A extracts LSBs but places them starting from low bits (original order); B uses left shift for extraction which fails to get bits properly; C uses arithmetic + instead of bitwise | and builds original order.

3. Final Answer:

   let result = 0; for(let i=0; i<8; i++) { result |= ((n >> i) & 1) << (7 - i); } -> Option A

4. Quick Check:

   Right shift and left place = correct reverse [OK]

Hint: Shift right to extract bits, shift left to place reversed bits [OK]

Common Mistakes:

• Using left shift to extract bits instead of right shift
• Not reversing the bit position when placing
• Adding bits instead of using bitwise OR

3. What is the output of this TypeScript code?

function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 4; i++) {
    result |= ((n >> i) & 1) << (3 - i);
  }
  return result;
}
console.log(reverseBits(6));

medium

A. 6

B. 9

C. 3

D. 12

Solution

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

   6 in binary (4 bits) is 0110.

2. Step 2: Reverse bits

   Bits from LSB: 0,1,1,0. Reversed positions yield 0,1,1,0 reversed is 0110 reversed to 0110 reversed is 0110? Actually reversed bits are 0110 reversed to 0110? Let's check carefully.

3. Step 3: Dry run code

   i=0: (6 >> 0) & 1 = 0 << 3 = 0
   i=1: (6 >> 1) & 1 = 1 << 2 = 4 (result=4)
   i=2: (6 >> 2) & 1 = 1 << 1 = 2 (result=6)
   i=3: (6 >> 3) & 1 = 0 << 0 = 0 (result=6)

4. Step 4: Check if output matches options

   Output is 6, but 9 is 9, 6 is 6.

5. Final Answer:

   6 -> Option A

6. Quick Check:

   Reverse bits of 6 (0110) = 6 [OK]

Hint: Trace bit shifts carefully to find reversed number [OK]

Common Mistakes:

• Confusing bit positions when reversing
• Assuming reversed bits always change the number
• Miscounting bits or loop range

4. Identify the bug in this TypeScript function that reverses 8-bit numbers:

function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i <= 8; i++) {
    result |= ((n >> i) & 1) << (7 - i);
  }
  return result;
}

medium

A. Variable result should be initialized to 1

B. Bitwise OR operator is used incorrectly

C. Shift amount is not adjusted for 8 bits

D. Loop runs one extra time causing incorrect bit shift

Solution

1. Step 1: Check loop range

   The loop runs from i = 0 to i = 8 inclusive, so 9 iterations total, but 8-bit numbers have bits 0 to 7 only.

2. Step 2: Effect of extra iteration

   At i=8, shifting by (7 - 8) = -1 is invalid and causes incorrect behavior or runtime error.

3. Final Answer:

   Loop runs one extra time causing incorrect bit shift -> Option D

4. Quick Check:

   Loop should run 8 times, not 9 [OK]

Hint: Loop from 0 to 7 for 8 bits, not 0 to 8 [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring negative shift values
• Initializing result incorrectly

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

hard

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

B. Reverse bits using a loop, then reverse again and compare to original

C. Reverse bits using a loop, then check if reversed number equals its own reverse

D. Check if original number equals its own reverse without reversing bits

Solution

1. Step 1: Reverse bits of the number

   Use a loop to reverse bits of the 16-bit number to get reversedNum.

2. Step 2: Check palindrome property

   To check if reversedNum is palindrome, reverse reversedNum again and compare with reversedNum itself.

3. Step 3: Reasoning

   If reversedNum equals its own reverse, it is a palindrome in binary.

4. Final Answer:

   Reverse bits using a loop, then check if reversed number equals its own reverse -> Option C

5. Quick Check:

   Palindrome check = reversedNum == reverse(reversedNum) [OK]

Hint: Check palindrome by reversing reversed number and comparing [OK]

Common Mistakes:

• Comparing reversed number to original instead of itself
• Not reversing reversed number for palindrome check
• Assuming original number palindrome means reversed number palindrome