Why Bit Manipulation and When It Beats Arithmetic in DSA C - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a number is even using bit manipulation.

DSA C

int isEven(int num) {
    return (num & [1]) == 0;
}

Drag options to blanks, or click blank then click option'

A1

B0

C2

Dnum

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 in the bitwise AND which always returns 0.

Using 2 which checks the second bit, not the first.

The least significant bit (LSB) of an even number is 0. Using num & 1 checks this bit.

2fill in blank

medium

Complete the code to multiply a number by 8 using bit manipulation.

DSA C

int multiplyByEight(int num) {
    return num [1] 3;
}

Drag options to blanks, or click blank then click option'

A+

B*

C>>

D<<

Attempts:

3 left

💡 Hint

Common Mistakes

Using right shift which divides the number.

Using multiplication operator instead of bit shift.

Left shifting a number by 3 bits multiplies it by 2³ = 8.

3fill in blank

hard

Fix the error in the code to divide a number by 4 using bit manipulation.

DSA C

int divideByFour(int num) {
    return num [1] 2;
}

Drag options to blanks, or click blank then click option'

A>>

B<<

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using left shift which multiplies instead of dividing.

Using addition or subtraction operators.

Right shifting by 2 bits divides the number by 2² = 4.

4fill in blank

hard

Fill both blanks to toggle the 3rd bit of a number.

DSA C

int toggleThirdBit(int num) {
    return num [1] [2];
}

Drag options to blanks, or click blank then click option'

A^

B&

C1 << 2

D1 << 3

Attempts:

3 left

💡 Hint

Common Mistakes

Using bit 3 (index 3) instead of bit 2 for the 3rd bit.

Using AND which clears bits instead of toggling.

XOR (^) with 1 << 2 toggles the 3rd bit (bit index 2).

5fill in blank

hard

Fill all three blanks to set the 5th bit of a number and clear the 2nd bit.

DSA C

int setAndClearBits(int num) {
    num = num [1] [2];
    num = num [3] ~(1 << 1);
    return num;
}

Drag options to blanks, or click blank then click option'

A|

B&

C~

D1 << 4

Attempts:

3 left

💡 Hint

Common Mistakes

Using XOR to clear bits which toggles instead.

Using wrong bit positions for setting or clearing.

Use OR (|) with 1 << 4 to set the 5th bit, then AND (&) with the negation (~) of 1 << 1 to clear the 2nd bit.

Practice

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

easy

A. Because bit manipulation requires more memory, making it faster

B. Because bit manipulation uses loops internally to speed up calculations

C. Because bit manipulation uses simple CPU instructions that run in constant time

D. Because arithmetic operations are always done in software, not hardware

Solution

1. Step 1: Understand CPU instruction speed

   Bit manipulation uses basic CPU instructions like AND, OR, XOR, and shifts which are very fast and usually take one CPU cycle.

2. Step 2: Compare with arithmetic operations

   Multiplication and division are more complex and often take multiple CPU cycles, making them slower than bit operations.

3. Final Answer:

   Because bit manipulation uses simple CPU instructions that run in constant time -> Option C

4. Quick Check:

   Bit ops faster than arithmetic = D [OK]

Hint: Bit ops use simple CPU steps, so they run faster than math [OK]

Common Mistakes:

• Thinking bit manipulation uses loops internally
• Assuming arithmetic is always hardware-based and fast
• Believing more memory means faster operations

2. Which of the following is the correct C syntax to check if the 3rd bit (from right, zero-based) of an integer x is set using bit manipulation?

easy

A. if (x | (1 << 3))

B. if (x & (1 << 3))

C. if (x & (3 << 1))

D. if (x << 3)

Solution

1. Step 1: Understand bit checking syntax

   To check if a bit is set, we use bitwise AND (&) with a mask that has 1 at the target bit position.

2. Step 2: Create mask for 3rd bit

   The mask is 1 shifted left by 3 positions: (1 << 3). Using (x & (1 << 3)) checks if that bit is set.

3. Final Answer:

   if (x & (1 << 3)) -> Option B

4. Quick Check:

   Bit check uses & and (1 << position) = A [OK]

Hint: Use & with (1 << bit_position) to check bits [OK]

Common Mistakes:

• Using bitwise OR (|) instead of AND (&) to check bits
• Shifting wrong number or wrong direction
• Using left shift without mask

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

unsigned int x = 10; // binary 1010
unsigned int y = x << 2;
printf("%u", y);

medium

A. 20

B. 80

C. 5

D. 40

Solution

1. Step 1: Understand left shift operation

   Left shifting by 2 means multiply by 2^2 = 4. So y = 10 * 4 = 40.

2. Step 2: Confirm output

   printf prints unsigned integer y, which is 40.

3. Final Answer:

   40 -> Option D

4. Quick Check:

   10 << 2 = 40 [OK]

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

Common Mistakes:

• Confusing left shift with right shift
• Thinking shift divides instead of multiplies
• Misreading binary values

4. Identify the error in this C code snippet that tries to clear the 2nd bit of variable x:

int x = 15; // binary 1111
x = x & (1 << 2);
printf("%d", x);

medium

A. The mask should be ~(1 << 2) to clear the bit

B. The shift operator should be >> instead of <<

C. The variable x should be unsigned int

D. The printf format specifier should be %u instead of %d

Solution

1. Step 1: Understand clearing a bit

   To clear a bit, we AND with a mask that has 0 at that bit and 1s elsewhere. This mask is ~(1 << 2).

2. Step 2: Analyze given code

   The code uses x & (1 << 2), which keeps only the 2nd bit and clears others, not what is intended.

3. Final Answer:

   The mask should be ~(1 << 2) to clear the bit -> Option A

4. Quick Check:

   Clear bit uses AND with negated mask = A [OK]

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

Common Mistakes:

• Using positive mask instead of negated mask to clear bit
• Confusing shift directions
• Ignoring signed vs unsigned types

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

hard

A. (x & 1) == 0 because the least significant bit shows evenness, and bitwise AND is faster than modulus

B. (x >> 1) == 0 because shifting right divides by 2, faster than modulus

C. (x | 1) == x because OR with 1 sets the bit, faster than modulus

D. (x ^ 1) == 0 because XOR with 1 checks parity, faster than modulus

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. So (x & 1) == 0 means even.

2. Step 2: Compare speed with modulus

   Bitwise AND is a simple CPU instruction and faster than modulus (%) which is more complex.

3. Final Answer:

   (x & 1) == 0 because the least significant bit shows evenness, and bitwise AND is faster than modulus -> Option A

4. Quick Check:

   Check even with (x & 1) == 0 faster than % [OK]

Hint: Use (x & 1) to check even/odd faster than % [OK]

Common Mistakes:

• Using shift right to check evenness incorrectly
• Confusing OR and XOR for parity check
• Assuming modulus is always faster