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

Practice - 5 Tasks

1fill in blank

easy

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

DSA Go

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

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

A1

Bnum

C2

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 as mask always returns true.

Using 2 checks the wrong bit.

Using num & 1 checks the least significant bit. If it is 0, the number is even.

2fill in blank

medium

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

DSA Go

func multiplyByTwo(num int) int {
    return num [1] 1
}

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

A<<

B+

C*

D>>

Attempts:

3 left

💡 Hint

Common Mistakes

Using + 1 adds 1 instead of multiplying.

Using >> shifts right, dividing the number.

Left shifting by 1 bit multiplies the number by 2 efficiently.

3fill in blank

hard

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

DSA Go

func divideByFour(num int) int {
    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 << shifts left, multiplying instead of dividing.

Using + or - does not divide.

Right shifting by 2 bits divides the number by 4 efficiently.

4fill in blank

hard

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

DSA Go

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

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

A^

B<<

C|

D&

Attempts:

3 left

💡 Hint

Common Mistakes

Using OR (|) sets the bit instead of toggling.

Using AND (&) clears bits instead of toggling.

Use XOR (^) with 1 shifted left by 2 to toggle the 3rd bit.

5fill in blank

hard

Fill all three blanks to create a mask that sets the 1st and 4th bits of a number.

DSA Go

func setBits(num int) int {
    mask := (1 [1] 0) [2] (1 [3] 3)
    return num | mask
}

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

A<<

B|

D&

Attempts:

3 left

💡 Hint

Common Mistakes

Using & combines bits incorrectly.

Using wrong shift amounts targets wrong bits.

Shift 1 left by 0 and 3, then OR (|) them to create a mask for 1st and 4th bits.

Practice

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

easy

A. Because bit manipulation uses more memory which speeds up processing

B. Because arithmetic operations are not supported by modern CPUs

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

D. Because arithmetic operations always cause errors in calculations

Solution

1. Step 1: Understand CPU instruction speed

   Bit manipulation uses basic CPU instructions like AND, OR, XOR, 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 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 [OK]

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

Common Mistakes:

• Thinking arithmetic is always faster
• Confusing memory use with speed
• Believing CPUs don't support arithmetic

2. Which of the following Go code snippets correctly uses bit manipulation to multiply an integer by 8?

easy

A. result := num >> 3

B. result := num << 3

C. result := num & 8

D. result := num ^ 8

Solution

1. Step 1: Understand bit shift left operation

   Shifting bits left by 3 positions multiplies the number by 2^3 = 8.

2. Step 2: Check other operations

   Right shift divides, AND masks bits, XOR toggles bits, so they don't multiply by 8.

3. Final Answer:

   result := num << 3 -> Option B

4. Quick Check:

   Left shift by 3 multiplies by 8 [OK]

Hint: Use << 3 to multiply by 8 quickly [OK]

Common Mistakes:

• Using >> instead of << for multiplication
• Using & or ^ which do not multiply
• Confusing shift count with multiplication factor

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

num := 12
result := (num & 7) << 1
fmt.Println(result)

medium

A. 8

B. 10

C. 14

D. 24

Solution

1. Step 1: Calculate num & 7

   12 in binary is 1100, 7 is 0111. Bitwise AND: 1100 & 0111 = 0100 (decimal 4).

2. Step 2: Shift left by 1

   4 << 1 means 4 * 2 = 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   (12 & 7) << 1 = 8 [OK]

Hint: AND then shift left doubles the masked value [OK]

Common Mistakes:

• Misreading binary AND result
• Confusing left shift with right shift
• Calculating decimal incorrectly

4. Find the error in this Go code that tries to check if a number is even using bit manipulation:

func isEven(num int) bool {
    return num & 1 == 0
}

medium

A. Missing parentheses around bitwise operation

B. Incorrect operator precedence causes wrong result

C. Bitwise AND cannot be used with integers

D. No error, code works correctly

Solution

1. Step 1: Understand operator precedence in Go

   Bitwise AND (&) has higher precedence than ==, so expression evaluates as (num & 1) == 0 correctly.

2. Step 2: Check if code logic is correct

   Checking if last bit is 0 means number is even, so function returns true for even numbers.

3. Final Answer:

   No error, code works correctly -> Option D

4. Quick Check:

   Bitwise AND with 1 checks evenness correctly [OK]

Hint: Bitwise AND with 1 checks last bit correctly [OK]

Common Mistakes:

• Assuming operator precedence error
• Thinking bitwise AND can't be used with ints
• Adding unnecessary parentheses

5. You want to quickly check if a number is a power of two using bit manipulation in Go. Which expression correctly does this?

func isPowerOfTwo(num int) bool {
    return ???
}

hard

A. num & (num - 1) == 0 && num != 0

B. num | (num - 1) == 0

C. num ^ (num - 1) == 0

D. num & (num + 1) == 0

Solution

1. Step 1: Recall power of two property

   A power of two has exactly one bit set. num & (num - 1) clears the lowest set bit.

2. Step 2: Check expression meaning

   If num is power of two, num & (num - 1) == 0. Also check num != 0 to exclude zero.

3. Step 3: Verify other options

   OR, XOR, and & with (num + 1) do not correctly test power of two.

4. Final Answer:

   num & (num - 1) == 0 && num != 0 -> Option A

5. Quick Check:

   Power of two test uses num & (num-1) = 0 [OK]

Hint: Use num & (num-1) == 0 to test power of two [OK]

Common Mistakes:

• Using OR or XOR instead of AND
• Not checking num != 0
• Using num + 1 instead of num - 1