Why Bit Manipulation and When It Beats Arithmetic in DSA Javascript - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bitwise AND vs Arithmetic AND

What is the output of the following JavaScript code snippet?

DSA Javascript

const a = 5; // binary 0101
const b = 3; // binary 0011
const result = a & b;
console.log(result);

A 8

B 7

C 15

D 1

💡 Hint

Remember how bitwise AND works on each bit position.

The bitwise AND operator compares each bit of two numbers and returns 1 only if both bits are 1.

5 in binary is 0101, 3 is 0011. ANDing them gives 0001 which is 1 in decimal.

❓ Predict Output

intermediate

When Bit Shift Beats Multiplication

What is the output of this JavaScript code that uses bit shifting instead of multiplication?

DSA Javascript

const x = 4;
const y = x << 2;
console.log(y);

A 16

B 32

C 8

D 4

💡 Hint

Left shift by 2 bits multiplies the number by 2^2.

Left shifting a number by 2 bits is the same as multiplying it by 4.

So 4 << 2 equals 4 * 4 = 16.

🔧 Debug

advanced

Identify the Error in Bitwise XOR Usage

What error or unexpected output will this JavaScript code produce?

DSA Javascript

let num = 10;
num = num ^ 5;
num = num ^ 5;
console.log(num);

A 5

B 15

C 10

D SyntaxError

💡 Hint

XORing a number twice with the same number returns the original number.

XOR operation toggles bits. Doing XOR twice with the same number restores the original value.

So num ends up as 10 again.

🧠 Conceptual

advanced

Why Bit Manipulation Can Be Faster Than Arithmetic

Which of the following is the best reason why bit manipulation can be faster than arithmetic operations in some cases?

A Bit manipulation avoids using registers and thus is faster.

B Bit manipulation uses fewer CPU cycles because it works directly on binary digits.

C Arithmetic operations always require more memory than bit manipulation.

D Bit manipulation uses floating point operations which are faster.

💡 Hint

Think about how computers store and process numbers at the lowest level.

Bit manipulation works directly on the binary representation of numbers, often using simple CPU instructions that are faster than arithmetic operations.

🚀 Application

expert

Using Bit Manipulation to Check Even or Odd

Which code snippet correctly uses bit manipulation to check if a number is even or odd?

A if ((num & 1) === 0) { console.log('Even'); } else { console.log('Odd'); }

B if ((num | 1) === 0) { console.log('Even'); } else { console.log('Odd'); }

C if ((num ^ 1) === 0) { console.log('Even'); } else { console.log('Odd'); }

D if ((num << 1) === 0) { console.log('Even'); } else { console.log('Odd'); }

💡 Hint

The least significant bit tells if a number is even or odd.

The least significant bit (rightmost bit) is 0 for even numbers and 1 for odd numbers.

Using bitwise AND with 1 isolates this bit.

Practice

1. Why is bit manipulation often faster than arithmetic operations like multiplication or division?

easy

A. Because bit manipulation works directly on binary digits using CPU instructions

B. Because arithmetic operations use less memory

C. Because bit manipulation requires more CPU cycles

D. Because arithmetic operations are always done in parallel

Solution

1. Step 1: Understand how bit manipulation works

   Bit manipulation uses CPU instructions that directly change bits (0s and 1s) in numbers.

2. Step 2: Compare with arithmetic operations

   Arithmetic like multiplication or division involves more complex calculations and takes more CPU cycles.

3. Final Answer:

   Because bit manipulation works directly on binary digits using CPU instructions -> Option A

4. Quick Check:

   Bit manipulation = faster CPU-level operations [OK]

Hint: Bit ops use CPU bits directly, so they run faster [OK]

Common Mistakes:

• Thinking arithmetic uses less memory
• Believing bit manipulation is slower
• Assuming arithmetic is always parallel

2. Which of the following is the correct JavaScript syntax to check if the 3rd bit (from right, zero-based) of a number n is set using bit manipulation?

easy

A. if ((n & (1 << 3)) !== 0) { /* bit is set */ }

B. if ((n | (1 << 3)) === 0) { /* bit is set */ }

C. if ((n & (3 << 1)) !== 0) { /* bit is set */ }

D. if ((n ^ (1 << 3)) !== 0) { /* bit is set */ }

Solution

1. Step 1: Understand bit checking syntax

   To check if a bit is set, use bitwise AND (&) with 1 shifted left by the bit position.

2. Step 2: Apply to 3rd bit (zero-based)

   Shift 1 by 3 places: (1 << 3). Then check if (n & (1 << 3)) is not zero.

3. Final Answer:

   if ((n & (1 << 3)) !== 0) { /* bit is set */ } -> Option A

4. Quick Check:

   Bit check = (n & (1 << 3)) !== 0 [OK]

Hint: Use & with 1 shifted to bit position to check bit [OK]

Common Mistakes:

• Using bitwise OR (|) instead of AND (&)
• Shifting wrong number of bits
• Using XOR (^) which toggles bits

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

let x = 5; // binary 0101
let y = x << 2;
console.log(y);

medium

A. 10

B. 40

C. 20

D. 8

Solution

1. Step 1: Understand left shift operation

   Left shifting by 2 moves bits 2 places left, multiplying the number by 2^2 = 4.

2. Step 2: Calculate shifted value

   5 * 4 = 20, so y = 20.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   5 << 2 = 20 [OK]

Hint: Left shift by n multiplies by 2^n [OK]

Common Mistakes:

• Confusing left shift with right shift
• Forgetting shift multiplies by powers of two
• Assuming shift adds bits instead of moving

4. Find the error in this JavaScript code that tries to clear the 2nd bit of a number num:

num = num & (1 << 2);

medium

A. It should use bitwise OR (|) instead of AND (&)

B. It should use bitwise XOR (^) to clear the bit

C. There is no error; code correctly clears the bit

D. It should use bitwise AND with the negation of the bit mask

Solution

1. Step 1: Understand clearing a bit

   To clear a bit, AND with a mask that has all bits 1 except the target bit 0.

2. Step 2: Fix the mask

   Mask should be ~(1 << 2), so code should be: num = num & ~(1 << 2).

3. Final Answer:

   It should use bitwise AND with the negation of the bit mask -> Option D

4. Quick Check:

   Clear bit = num & ~(1 << bit) [OK]

Hint: Clear bit by AND with negated mask ~(1 << bit) [OK]

Common Mistakes:

• Using OR (|) which sets bits instead of clearing
• Using XOR (^) which toggles bits
• Not negating the mask before AND

5. You want to quickly check if a number n is even or odd without using modulus (%) or division. Which bit manipulation expression correctly does this and why is it faster than arithmetic?

hard

A. (n ^ 1) === 0 because XOR toggles the last bit

B. (n & 1) === 0 because it checks the least significant bit directly

C. (n | 1) === n because OR sets the last bit

D. (n >> 1) === 0 because shifting right divides by 2

Solution

1. Step 1: Understand even/odd check with bits

   The least significant bit (rightmost) is 0 for even numbers and 1 for odd numbers.

2. Step 2: Use bitwise AND to check LSB

   Expression (n & 1) extracts the last bit. If it equals 0, number is even.

3. Step 3: Why faster than arithmetic

   Bitwise AND is a simple CPU instruction, faster than modulus or division.

4. Final Answer:

   (n & 1) === 0 because it checks the least significant bit directly -> Option B

5. Quick Check:

   Even check = (n & 1) === 0 [OK]

Hint: Check even with (n & 1) === 0 for fast bit test [OK]

Common Mistakes:

• Using right shift (>>) which changes number value
• Using OR (|) which sets bits instead of checking
• Using XOR (^) which toggles bits