Bit manipulation techniques - Step-by-Step Execution

Concept Flow - Bit manipulation techniques

Start with integer x

↓

Choose bit operation

↓

Set

↓

Use bitwise operators

↓

Update x with new value

↓

Use or print result

↓

End

Start with a number, pick a bit operation (set, clear, toggle), apply bitwise operators, update the number, then use or print the result.

Execution Sample

C

int x = 5; // binary 0101
x = x | (1 << 1); // set bit 1
printf("%d", x);

This code sets bit 1 of x (which is 5) and prints the new value.

Execution Table

Step	Operation	Expression	Binary Before	Binary After	Decimal After	Explanation
1	Initialize x	x = 5	00000101	00000101	5	Start with x = 5 (binary 0101)
2	Set bit 1	x = x | (1 << 1)	00000101	00000111	7	Set bit 1: 0101 OR 0010 = 0111
3	Print x	printf("%d", x)	00000111	00000111	7	Output the updated value 7

💡 All steps completed; bit 1 set successfully.

Variable Tracker

Variable	Start	After Step 2	Final
x	5 (00000101)	7 (00000111)	7 (00000111)

Key Moments - 3 Insights

Why do we use (1 << 1) to set bit 1?

Because (1 << 1) shifts 1 to the left by 1 position, creating a mask with only bit 1 set (binary 0010). This mask is used with OR to set that bit in x (see execution_table step 2).

Why does OR operation set the bit instead of clearing it?

OR operation sets a bit to 1 if either operand has 1 in that bit. So when OR-ing with a mask that has bit 1 set, that bit in x becomes 1 regardless of its previous value (execution_table step 2).

What happens if the bit is already set before OR?

If the bit is already 1, OR-ing with 1 keeps it 1, so the value stays the same (no change). This is why OR is safe to use to set bits without affecting others.

Visual Quiz - 3 Questions

Look at the execution_table, what is the binary value of x after step 2?

A 00000010

B 00000111

C 00000101

D 00000001

💡 Hint

Check the 'Binary After' column in execution_table row for step 2.

At which step does x change from 5 to 7?

A Step 2

B Step 1

C Step 3

D No change

💡 Hint

Look at the 'Decimal After' column and see when it changes from 5 to 7.

If we wanted to clear bit 2 instead of setting bit 1, which operation would we use?

A x = x | (1 << 2)

B x = x ^ (1 << 2)

C x = x & ~(1 << 2)

D x = x << 2

💡 Hint

Clearing a bit uses AND with the negated mask; see common bit manipulation patterns.

Concept Snapshot

Bit manipulation uses bitwise operators to change bits.
Set bit: x = x | (1 << n)
Clear bit: x = x & ~(1 << n)
Toggle bit: x = x ^ (1 << n)
Shift left/right moves bits.
Use masks to target specific bits.

Full Transcript

This lesson shows how to change bits in an integer using bitwise operators in C. We start with a number x, then pick an operation like setting a bit. To set bit 1, we create a mask by shifting 1 left by 1 (1 << 1), which is binary 0010. We then OR this mask with x to set that bit. The execution table shows x starting at 5 (binary 0101), then after setting bit 1, it becomes 7 (binary 0111). We print the result. Key points include why shifting creates the mask, how OR sets bits, and what happens if the bit is already set. The quiz asks about the binary value after setting the bit, when the change happens, and how to clear a bit using AND with negated mask. The snapshot summarizes common bit manipulation patterns for setting, clearing, toggling bits, and shifting.

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