Reverse Bits of a Number in DSA Javascript - Execution Trace

Concept Flow - Reverse Bits of a Number

Start with number n

↓

Initialize result = 0

↓

Repeat for each bit position

↓

Extract rightmost bit of n

↓

Shift result left by 1

↓

Add extracted bit to result

↓

Shift n right by 1

↓

Repeat until all bits processed

↓

Return result with bits reversed

We take each bit from the original number from right to left, add it to the result from left to right, shifting bits accordingly until all bits are reversed.

Execution Sample

DSA Javascript

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

This code reverses the bits of an 8-bit number by shifting and masking bits step-by-step.

Execution Table

Step	Operation	n (binary)	Extracted bit (n & 1)	result (binary)	result (decimal)
1	Initialize result=0, n=00010110 (22 decimal)	00010110	-	00000000	0
2	Extract bit: 0, shift result left, add bit	00010110	0	00000000	0
3	Shift n right	00001011	-	00000000	0
4	Extract bit: 1, shift result left, add bit	00001011	1	00000001	1
5	Shift n right	00000101	-	00000001	1
6	Extract bit: 1, shift result left, add bit	00000101	1	00000011	3
7	Shift n right	00000010	-	00000011	3
8	Extract bit: 0, shift result left, add bit	00000010	0	00000110	6
9	Shift n right	00000001	-	00000110	6
10	Extract bit: 1, shift result left, add bit	00000001	1	00001101	13
11	Shift n right	00000000	-	00001101	13
12	Extract bit: 0, shift result left, add bit	00000000	0	00011010	26
13	Shift n right	00000000	-	00011010	26
14	Extract bit: 0, shift result left, add bit	00000000	0	00110100	52
15	Shift n right	00000000	-	00110100	52
16	Extract bit: 0, shift result left, add bit	00000000	0	01101000	104
17	Shift n right	00000000	-	01101000	104
18	8 bits processed, no more extraction	00000000	-	01101000	104
19	Prepare to return result	00000000	-	01101000	104
20	All 8 bits processed, return result (104 decimal)	00000000	-	01101000	104

💡 After 8 iterations, all bits of the original 8-bit number are processed and reversed.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
n (decimal)	22	11	5	2	1	0	0	0	0	0
n (binary)	00010110	00001011	00000101	00000010	00000001	00000000	00000000	00000000	00000000	00000000
result (binary)	00000000	00000000	00000001	00000011	00000110	00001101	00011010	00110100	01101000	01101000
result (decimal)	0	0	1	3	6	13	26	52	104	104

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, as shown in steps 2, 4, 6, etc. in the execution_table.

Why do we use (n & 1) to get the extracted bit?

The expression (n & 1) isolates the rightmost bit of n by masking all other bits, as seen in the 'Extracted bit' column in the execution_table.

Why do we shift n right after each bit extraction?

Shifting n right moves the next bit to the rightmost position so it can be extracted in the next iteration, as shown in the 'n (binary)' changes in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the decimal value of result?

A 13

B 6

C 3

D 1

💡 Hint

Check the 'result (decimal)' column at step 10 in the execution_table.

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

A Step 5

B Step 6

C Step 11

D Step 12

💡 Hint

Look at the 'n (binary)' column in execution_table and variable_tracker to see when it changes to 00000000.

If we change the loop to run 4 times instead of 8, what would be the final decimal result?

A 13

B 6

C 3

D 1

💡 Hint

Check the result after 4 iterations in the execution_table and variable_tracker.

Concept Snapshot

Reverse Bits of a Number:
- Initialize result = 0
- For each bit in number:
  - Extract rightmost bit (n & 1)
  - Shift result left by 1
  - Add extracted bit to result
  - Shift n right by 1
- After all bits processed, result holds reversed bits

Full Transcript

This visualization shows how to reverse the bits of an 8-bit number step-by-step. We start with the original number n and a result initialized to zero. Each step extracts the rightmost bit of n using (n & 1), shifts the result left to make space, then adds the extracted bit. Then n is shifted right to prepare for the next bit extraction. This repeats for 8 iterations, covering all bits. The execution table tracks the binary and decimal values of n and result at each step. The variable tracker shows how n and result change after each iteration. Key moments clarify why shifting and masking are used. The quiz tests understanding of the bit extraction and shifting process. The snapshot summarizes the method in simple steps.

Practice

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

easy

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

B. Changing all 0 bits to 1 bits

C. Adding 1 to the number

D. Multiplying the number by 2

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.

3. Final Answer:

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

4. Quick Check:

   Reverse bits = flip order [OK]

Hint: Think of bits like beads on a string flipped end to end [OK]

Common Mistakes:

• Confusing reversing bits with flipping bits (0 to 1)
• Thinking reversing bits changes the number by adding or multiplying
• Assuming reversing bits means reversing digits in decimal

2. Which of the following JavaScript code snippets correctly reverses the bits of an 8-bit number n?

easy

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

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

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

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

Solution

1. Step 1: Analyze the loop and bit operations

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

2. Step 2: Check other options for errors

   let result = 0; for(let i=0; i<8; i++) { result |= (n & 1) << i; n >>= 1; } does not reverse bits, it copies bits in same order. let result = 0; for(let i=7; i>0; i--) { result |= (n & 1) << i; n >>= 1; } shifts bits incorrectly. let result = 0; for(let i=0; i<8; i++) { result += (n & 1) << i; n <<= 1; } shifts n left, which is wrong.

3. Final Answer:

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

4. Quick Check:

   Shift result left + add bit from n right [OK]

Hint: Shift result left, add n's right bit, shift n right [OK]

Common Mistakes:

• Shifting n left instead of right
• Not shifting result before adding bit
• Using wrong loop direction or bit positions

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

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

console.log(reverseBits(13));

medium

A. 14

B. 11

C. 7

D. 13

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

   Loop 4 times: result builds as follows:
   i=0: result=0<<1=0 + (13&1=1) =1
   n=13>>1=6 (0110)
   i=1: result=1<<1=2 + (6&1=0) =2
   n=6>>1=3 (0011)
   i=2: result=2<<1=4 + (3&1=1) =5
   n=3>>1=1 (0001)
   i=3: result=5<<1=10 + (1&1=1) =11

3. Final Answer:

   11 -> Option B

4. Quick Check:

   Reverse 1101 = 1011 (binary 11 decimal) [OK]

Hint: Trace bit shifts and OR operations carefully [OK]

Common Mistakes:

• Confusing decimal and binary values
• Not shifting result before OR
• Looping wrong number of times

4. Find the error in this bit reversal function and choose the corrected version:

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

medium

A. Change loop to run 16 times

B. Shift n left instead of right

C. Initialize result with 1 instead of 0

D. Swap the order: shift result left before OR operation

Solution

1. Step 1: Identify order of operations

   Current code ORs bit then shifts result left, causing last bit to be lost.

2. Step 2: Correct by shifting result left before OR

   Shift result left first, then OR with current bit to build reversed bits correctly.

3. Final Answer:

   Swap the order: shift result left before OR operation -> Option D

4. Quick Check:

   Shift before OR to keep all bits [OK]

Hint: Always shift result left before adding new bit [OK]

Common Mistakes:

• Shifting result after OR loses last bit
• Shifting n left instead of right
• Wrong loop count for bit size

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 check if reversed number equals its own reverse

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

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

D. Reverse bits using a loop, then convert to decimal and check if even

Solution

1. Step 1: Reverse bits of the number

   Use a loop to reverse all 16 bits correctly.

2. Step 2: Check palindrome by comparing reversed number with its own reverse

   If reversed number equals its reverse, it is a binary palindrome.

3. Final Answer:

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

4. Quick Check:

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

Hint: Check palindrome by comparing reversed number to its reverse [OK]

Common Mistakes:

• Comparing reversed number directly to original (wrong for palindrome)
• Checking decimal evenness instead of binary palindrome
• Reversing bits twice unnecessarily