Bit manipulation techniques - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the bitwise AND operator (&) do in C?

It compares each bit of two numbers and returns 1 only if both bits are 1; otherwise, it returns 0.

beginner

How do you set (turn on) the nth bit of a number using bit manipulation?

Use the OR operator (|) with a mask that has only the nth bit set:
number |= (1 << n);

intermediate

What is the purpose of the bitwise XOR operator (^) in bit manipulation?

It returns 1 for bits that are different and 0 for bits that are the same. It can be used to toggle bits.

beginner

How can you check if the nth bit of a number is set (1)?

Use the AND operator with a mask and check if the result is not zero:
if (number & (1 << n)) { /* nth bit is set */ }

beginner

What does the left shift operator (<<) do in bit manipulation?

It shifts all bits in a number to the left by a specified number of positions, adding zeros on the right. This multiplies the number by 2 for each shift.

Which operator is used to clear (turn off) the nth bit of a number in C?

A AND (&) with the complement of (1 << n)

B OR (|) with (1 << n)

C XOR (^) with (1 << n)

D Left shift (<<) by n

To clear the nth bit, use AND with the mask that has all bits set except the nth bit: number &= ~(1 << n);

What is the result of 5 & 3 in binary?

A 7

B 6

C 1

D 0

5 in binary is 0101, 3 is 0011; AND gives 0001 which is 1.

How do you toggle the 2nd bit of a number?

A number ^= (1 << 2);

B number &= ~(1 << 2);

C number |= (1 << 2);

D number << 2;

XOR (^) with (1 << 2) flips the 2nd bit.

What does the expression (number >> 1) do?

A Sets the 1st bit of number

B Shifts bits of number to the right by 1, dividing by 2

C Shifts bits of number to the left by 1, multiplying by 2

D Clears the 1st bit of number

Right shift by 1 moves bits right, effectively dividing by 2.

Which operator can be used to check if a number is even or odd?

A Left shift (<<) by 1

B OR (|) with 1

C XOR (^) with 1

D AND (&) with 1

Checking number & 1 returns 0 if even, 1 if odd.

Explain how to set, clear, and toggle a specific bit in a number using bit manipulation.

Think about how masks with a single bit set can change bits using AND, OR, XOR.

Describe how left shift and right shift operators affect a number's value and bits.

Consider how shifting bits changes the number in binary.

Practice

1. What does the bitwise AND operator & do when applied between two bits?

easy

A. Returns 1 if either bit is 1

B. Returns 0 always

C. Flips the bits

D. Returns 1 only if both bits are 1

Solution

1. Step 1: Understand bitwise AND operation

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

2. Step 2: Apply to bits

   For example, 1 & 1 = 1, but 1 & 0 = 0 and 0 & 0 = 0.

3. Final Answer:

   Returns 1 only if both bits are 1 -> Option D

4. Quick Check:

   AND = 1 if both bits 1 [OK]

Hint: AND returns 1 only when both bits are 1 [OK]

Common Mistakes:

• Confusing AND with OR operator
• Thinking AND flips bits
• Assuming AND always returns 1

2. Which of the following is the correct syntax to set the 3rd bit (0-indexed) of an unsigned int variable num in C?

easy

A. num = num | (1 << 3);

B. num = num & (1 << 3);

C. num = num ^ (1 << 3);

D. num = num << 3;

Solution

1. Step 1: Understand setting a bit

   To set a bit means to make it 1 without changing other bits. We use OR with a mask that has 1 at the target bit.

2. Step 2: Use bit shift and OR

   The mask is created by shifting 1 left by 3 (1 << 3). OR-ing num with this mask sets the 3rd bit.

3. Final Answer:

   num = num | (1 << 3); -> Option A

4. Quick Check:

   Set bit = OR with shifted 1 [OK]

Hint: Use OR with (1 << bit_position) to set a bit [OK]

Common Mistakes:

• Using AND instead of OR to set bits
• Using XOR which toggles bits
• Shifting num instead of 1

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

unsigned int x = 5;  // binary 0101
x = x ^ (1 << 2);
printf("%u", x);

medium

A. 4

B. 1

C. 5

D. 7

Solution

1. Step 1: Understand initial value and mask

   x = 5 in binary is 0101. The mask is (1 << 2) = 0100 (decimal 4).

2. Step 2: Apply XOR operation

   XOR toggles bits where mask has 1. 0101 ^ 0100 = 1101 (decimal 7). Let's do bitwise XOR:
   Bits (3 2 1 0):
   5 = 0 1 0 1
   Mask = 0 1 0 0
   XOR = 0 0 0 1 is incorrect.
   Actually, bits are:
   Bit 3: 0 ^ 0 = 0
   Bit 2: 1 ^ 1 = 0
   Bit 1: 0 ^ 0 = 0
   Bit 0: 1 ^ 0 = 1
   Result: 0001 (decimal 1) is incorrect for toggling bit 2.
   Wait, bit 2 is the third bit from right (0-indexed). So bits are:
   Bit 0: least significant bit
   Bit 1: next
   Bit 2: next
   So 5 (0101) bits:
   Bit 3: 0
   Bit 2: 1
   Bit 1: 0
   Bit 0: 1
   XOR with mask 0100:
   Bit 3: 0 ^ 0 = 0
   Bit 2: 1 ^ 1 = 0
   Bit 1: 0 ^ 0 = 0
   Bit 0: 1 ^ 0 = 1
   Result: 0001 (decimal 1). So output is 1.
   Therefore, correct answer is 1 -> 1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   XOR toggles bit 2: 5 ^ 4 = 1 [OK]

Hint: XOR toggles bits where mask is 1 [OK]

Common Mistakes:

• Miscounting bit positions (0-indexed from right)
• Confusing XOR with OR or AND
• Incorrect binary to decimal conversion

4. Identify the error in this C code snippet that tries to clear the 1st bit of num:

unsigned int num = 14;  // binary 1110
num = num & (1 << 1);
printf("%u", num);

medium

A. Mask should be inverted before AND

B. Should use OR instead of AND

C. Bit shift is incorrect, should be (1 << 0)

D. No error, code is correct

Solution

1. Step 1: Understand clearing a bit

   To clear a bit, we AND with a mask that has 0 at the target bit and 1s elsewhere.

2. Step 2: Analyze given mask

   The mask (1 << 1) is 00010 (binary), which has 1 only at bit 1. AND-ing num with this mask keeps only bit 1 and clears others, not what we want.

3. Step 3: Correct mask usage

   We should invert the mask: ~ (1 << 1), so bit 1 is 0 and others 1, then AND with num to clear bit 1.

4. Final Answer:

   Mask should be inverted before AND -> Option A

5. Quick Check:

   Clear bit = AND with inverted mask [OK]

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

Common Mistakes:

• Using mask without inversion to clear bits
• Using OR instead of AND to clear bits
• Confusing bit positions

5. You want to check if the 4th bit (0-indexed) of an unsigned int flags is set (1). Which code snippet correctly does this and prints "Set" if true, otherwise "Not set"?

hard

A. if ((flags ^ (1 << 4)) == 1) printf("Set"); else printf("Not set");

B. if ((flags | (1 << 4)) == 0) printf("Set"); else printf("Not set");

C. if ((flags & (1 << 4)) != 0) printf("Set"); else printf("Not set");

D. if ((flags & (1 << 3)) != 0) printf("Set"); else printf("Not set");

Solution

1. Step 1: Understand checking a bit

   To check if a bit is set, AND the number with a mask having 1 at that bit. If result is not zero, bit is set.

2. Step 2: Analyze options

   if ((flags & (1 << 4)) != 0) printf("Set"); else printf("Not set"); uses (flags & (1 << 4)) != 0 which correctly checks the 4th bit.
   if ((flags | (1 << 4)) == 0) printf("Set"); else printf("Not set"); uses OR and compares to zero, which is incorrect.
   if ((flags ^ (1 << 4)) == 1) printf("Set"); else printf("Not set"); uses XOR and compares to 1, which is incorrect.
   if ((flags & (1 << 3)) != 0) printf("Set"); else printf("Not set"); checks bit 3 instead of 4, so wrong bit.

3. Final Answer:

   if ((flags & (1 << 4)) != 0) printf("Set"); else printf("Not set"); -> Option C

4. Quick Check:

   Check bit = AND with mask != 0 [OK]

Hint: Check bit with AND and compare to zero [OK]

Common Mistakes:

• Using OR or XOR to check bits
• Checking wrong bit position
• Comparing AND result incorrectly