Chapter 8: Bit Manipulation & Encoding

8.1 The Six Core Operators

Suppose we have two 8-bit numbers:

A = 0011_1100 (60)
B = 0000_1101 (13)

Useful Shift Tricks

Competitive programmers rarely write pow(2, n) because floating-point operations are slow and prone to precision issues. Instead:

• 2^n → 1 << n
• x * 2 → x << 1
• x / 2 → x >> 1 (common in binary search: mid = (l + r) >> 1)

8.2 Handy Bitwise Hacks

1. Check parity:

   • if (x & 1) → x is odd.
   • if (!(x & 1)) → x is even. Odd numbers have the least significant bit set to 1.

2. Swap without temp (for fun, not recommended in production):

   a ^= b;
   b ^= a;
   a ^= b;

3. Find the lone number: An array has numbers appearing twice except one unique element. Trick: XOR all numbers. Because a ^ b ^ a = b, the duplicates cancel out and you are left with the odd-one-out.

8.3 Bitmasking: Encode a Set in an Integer

This is the strongest application of bit tricks. Suppose you have N switches (N ≤ 20). Each can be on or off. Instead of an array of bools, use a single integer state.

If state = 21 (binary 10101):

• Bit 0 = 1 → switch 0 is on.
• Bit 1 = 0 → switch 1 is off.
• Bit 2 = 1 → switch 2 is on.
• …

Core operations (0-indexed):

1. Check: if (state & (1 << i))
2. Add: state = state | (1 << i);
3. Remove: state = state & ~(1 << i); ~(1 << i) creates a mask with all bits 1 except bit i.
4. Toggle: state = state ^ (1 << i);

8.4 Lowbit: The Foundational Trick Behind Fenwick Trees

lowbit(x) returns the value of the lowest set bit in x.

• x = 12 (1100) → lowbit(12) = 4 (100)
• x = 6 (0110) → lowbit(6) = 2 (10)
• x = 7 (0111) → lowbit(7) = 1 (1)

int lowbit(int x) {
    return x & (-x);
}

Reason: In two’s complement, -x equals ~x + 1. The AND operation strips all bits except the lowest 1.

Example application: Count the number of 1-bits in x by repeatedly subtracting lowbit(x).

int countSetBits(int x) {
    int cnt = 0;
    while (x > 0) {
        x -= x & -x;
        cnt++;
    }
    return cnt;
}
// C++20 offers std::popcount(x)

8.5 GCC Built-ins (GCC/G++ Specific)

If you use GCC (Luogu, Codeforces), there are blazing-fast built-ins that save you from writing loops:

1. __builtin_popcount(x): number of 1s in x.
2. __builtin_ctz(x): count trailing zeros (number of zeros at the end).
3. __builtin_clz(x): count leading zeros (works for 32-bit ints).

⚠️ For long long, append ll: e.g., __builtin_popcountll(x).

🧠 Chapter Summary & Practice

Bit tricks might look mystical, but they are simply the right tools for representing sets and states compactly.

Practice problems:

1. P1469 Find Chopsticks (Luogu): find the lone number when every other number appears twice—O(N) and minimal extra space (hint: XOR).
2. LeetCode 78. Subsets: generate all subsets using bitmasking (0 to 2^N - 1).
3. P1226 Fast Power: revisit the previous chapter’s template and observe how b & 1 and b >>= 1 are bit tricks.

With bit operations in your belt, you now have the mindset for prefix sums and difference arrays (they are all about incremental updates). Next chapter introduces your first “preprocessing” technique: how to answer any range sum in O(1) time.