Bit manipulation techniques

Introduction

Bit manipulation lets you work directly with the tiny bits inside numbers. It helps you do tasks faster and use less memory.

You want to check if a number is even or odd quickly.

You need to turn on or off specific features represented by bits in a setting.

You want to swap two numbers without extra space.

You want to count how many bits are set to 1 in a number.

You want to store multiple true/false values compactly.

Syntax

C

/* Bit manipulation operations in C */

// Set a bit: number |= (1U << position);
// Clear a bit: number &= ~(1U << position);
// Toggle a bit: number ^= (1U << position);
// Check a bit: (number & (1U << position)) != 0

// Example function to set a bit:
unsigned int set_bit(unsigned int number, int position) {
    return number | (1U << position);
}

Bits are counted from 0 starting at the rightmost bit (least significant bit).

Use unsigned types to avoid unexpected behavior with shifts.

Examples

This example shows setting, clearing, toggling, and checking bits on a small number.

C

unsigned int number = 0b00001010; // 10 in decimal
// Set bit at position 1
number |= (1U << 1); // number becomes 0b00001010 (bit 1 already set)

// Clear bit at position 3
number &= ~(1U << 3); // number becomes 0b00000010

// Toggle bit at position 0
number ^= (1U << 0); // number becomes 0b00000011

// Check bit at position 2
int bit_is_set = (number & (1U << 2)) != 0; // bit_is_set is 0

Shows setting bits on an empty number, including the highest bit.

C

unsigned int number = 0; // all bits off
// Set bit at position 0
number |= (1U << 0); // number is 1

// Set bit at position 31 (highest bit in 32-bit)
number |= (1U << 31); // number has highest bit set

Shows clearing and toggling bits on a number with all bits set.

C

unsigned int number = 0xFFFFFFFF; // all bits on
// Clear bit at position 15
number &= ~(1U << 15); // bit 15 cleared

// Toggle bit at position 15
number ^= (1U << 15); // bit 15 set again

Sample Program

This program shows how to set, clear, toggle, and check bits in a number. It prints the bits before and after each operation for clear understanding.

C

#include <stdio.h>

// Function to print bits of a 32-bit number
void print_bits(unsigned int number) {
    for (int i = 31; i >= 0; i--) {
        unsigned int bit = (number >> i) & 1U;
        printf("%u", bit);
        if (i % 8 == 0 && i != 0) {
            printf(" "); // space every byte for readability
        }
    }
    printf("\n");
}

int main() {
    unsigned int number = 0b00000000000000000000000000001010; // 10 decimal
    printf("Original number bits:   ");
    print_bits(number);

    // Set bit at position 4
    number |= (1U << 4);
    printf("After setting bit 4:    ");
    print_bits(number);

    // Clear bit at position 1
    number &= ~(1U << 1);
    printf("After clearing bit 1:   ");
    print_bits(number);

    // Toggle bit at position 3
    number ^= (1U << 3);
    printf("After toggling bit 3:  ");
    print_bits(number);

    // Check bit at position 2
    int bit2 = (number & (1U << 2)) != 0;
    printf("Bit at position 2 is:  %d\n", bit2);

    return 0;
}

Important Notes

Bit manipulation operations run very fast because they work directly on bits.

Time complexity for these operations is O(1) because they do a fixed number of steps.

Be careful with signed integers and shifting; use unsigned types to avoid surprises.

Use bit manipulation when you want to save memory or speed up low-level tasks.

Summary

Bit manipulation lets you change or check individual bits inside numbers.

Common operations are setting, clearing, toggling, and checking bits.

Use unsigned integers and bitwise operators like |, &, ^, and << for these tasks.

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