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 double the value using bit manipulation.

DSA C++

int doubleValue(int x) {
    return x [1] 1;
}

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

A-

B>>

C+

D<<

Attempts:

3 left

💡 Hint

Common Mistakes

Using right shift (>>) instead of left shift.

Using arithmetic operators instead of bit shifts.

Left shifting by 1 (<< 1) multiplies the number by 2 efficiently.

2fill in blank

medium

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

DSA C++

bool isEven(int x) {
    return (x [1] 1) == 0;
}

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

A&

B|

C^

D<<

Attempts:

3 left

💡 Hint

Common Mistakes

Using OR (|) instead of AND (&).

Using shift operators incorrectly.

Using bitwise AND with 1 checks the least significant bit. If it is 0, the number is even.

3fill in blank

hard

Fix the error in the code to swap two integers without a temporary variable using XOR.

DSA C++

void swap(int &a, int &b) {
    a = a [1] b;
    b = a [1] b;
    a = a [1] b;
}

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

A&

B^

C|

D<<

Attempts:

3 left

💡 Hint

Common Mistakes

Using AND (&) or OR (|) instead of XOR (^).

Using shift operators incorrectly.

XOR (^) is used to swap values without extra space by toggling bits.

4fill in blank

hard

Fill both blanks to set the 3rd bit of a number and then clear the 2nd bit.

DSA C++

int modifyBits(int x) {
    x = x [1] (1 << 2); // Set 3rd bit
    x = x [2] ~(1 << 1); // Clear 2nd bit
    return x;
}

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

A|

B&

C^

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using XOR (^) to clear bits.

Using subtraction (-) incorrectly.

Use OR (|) to set a bit and AND (&) with negation to clear a bit.

5fill in blank

hard

Fill all three blanks to create a mask that extracts bits 4 to 6 from a number.

DSA C++

int extractBits(int x) {
    int mask = ((1 [1] [2]) - 1) << [3];
    return (x & mask) >> [3];
}

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

A<<

B3

C4

D>>

Attempts:

3 left

💡 Hint

Common Mistakes

Using right shift (>>) instead of left shift (<<) for mask creation.

Incorrect mask size or shift amount.

Shift 1 left by 3 (number of bits), subtract 1 to get mask bits, then shift mask left by 4 to align bits 4 to 6.

Practice

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

easy

A. Because bit manipulation requires complex algorithms

B. Because bit manipulation uses more memory to store results

C. Because arithmetic operations are not supported by modern CPUs

D. Because bit manipulation uses simple CPU instructions that execute in fewer cycles

Solution

1. Step 1: Understand CPU instruction execution

   Bit manipulation uses basic CPU instructions like shifts and AND/OR which are very fast.

2. Step 2: Compare with arithmetic operations

   Multiplication and division take more CPU cycles because they are more complex operations.

3. Final Answer:

   Because bit manipulation uses simple CPU instructions that execute in fewer cycles -> Option D

4. Quick Check:

   Bit manipulation faster than arithmetic = A [OK]

Hint: Bit ops use simple CPU steps, arithmetic takes longer [OK]

Common Mistakes:

• Thinking bit manipulation uses more memory
• Believing arithmetic is unsupported by CPUs
• Confusing complexity of bit ops with arithmetic

2. Which of the following is the correct C++ syntax to multiply an integer x by 8 using bit manipulation?

easy

A. x << 3

B. x >> 3

C. x & 3

D. x | 3

Solution

1. Step 1: Recall bit shift meaning

   Left shift by 3 bits (<< 3) multiplies by 2^3 = 8.

2. Step 2: Check other options

   Right shift divides, AND and OR do not multiply.

3. Final Answer:

   x << 3 -> Option A

4. Quick Check:

   Multiply by 8 = left shift 3 [OK]

Hint: Multiply by 2^n with << n, divide with >> n [OK]

Common Mistakes:

• Using right shift instead of left shift for multiplication
• Confusing bitwise AND/OR with multiplication
• Forgetting shift counts start at zero

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

int x = 10;
int y = x & 7;
std::cout << y << std::endl;

medium

A. 6

B. 3

C. 2

D. 7

Solution

1. Step 1: Convert numbers to binary

   10 in binary is 1010, 7 is 0111.

2. Step 2: Perform bitwise AND

   1010 & 0111 = 0010 (binary) which is 2 decimal.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   10 & 7 = 2 [OK]

Hint: AND keeps bits set in both numbers only [OK]

Common Mistakes:

• Confusing AND with OR operation
• Misreading binary values
• Assuming decimal AND operation

4. Identify the error in this C++ code snippet that tries to check if a number is even using bit manipulation:

int num = 5;
if (num & 1 == 0) {
  std::cout << "Even" << std::endl;
} else {
  std::cout << "Odd" << std::endl;
}

medium

A. Using bitwise AND instead of logical AND

B. Missing parentheses around (num & 1)

C. Incorrect variable type for num

D. Using == 0 instead of != 0

Solution

1. Step 1: Understand operator precedence

   == has higher precedence than &, so expression is evaluated as num & (1 == 0).

2. Step 2: Fix expression with parentheses

   Use (num & 1) == 0 to correctly check if last bit is zero (even number).

3. Final Answer:

   Missing parentheses around (num & 1) -> Option B

4. Quick Check:

   Use parentheses to fix precedence [OK]

Hint: Add parentheses around bit ops before comparisons [OK]

Common Mistakes:

• Ignoring operator precedence rules
• Confusing bitwise and logical AND
• Checking wrong condition for even

5. You want to quickly multiply a positive integer n by 10 using bit manipulation and addition to beat normal multiplication speed. Which expression correctly achieves this?

int result = ?;

hard

A. result = (n << 3) + (n << 1);

B. result = (n << 2) + (n << 1);

C. result = (n << 4) - n;

D. result = (n >> 1) + (n << 3);

Solution

1. Step 1: Express 10 as sum of powers of two

   10 = 8 + 2, which are 2^3 and 2^1.

2. Step 2: Use bit shifts to multiply

   n << 3 multiplies n by 8, n << 1 multiplies n by 2; sum gives n*10.

3. Step 3: Check other options

   (n << 4) - n = 16n - n = 15n; (n << 2) + (n << 1) = 4n + 2n = 6n; (n >> 1) + (n << 3) mixes division with multiplication incorrectly.

4. Final Answer:

   result = (n << 3) + (n << 1); -> Option A

5. Quick Check:

   Multiply by 10 = 8n + 2n = (n<<3)+(n<<1) [OK]

Hint: Multiply by 10 = multiply by 8 plus multiply by 2 [OK]

Common Mistakes:

• Using wrong shift counts for powers of two
• Mixing left and right shifts incorrectly
• Forgetting to add shifted values