Bit Operations

1. Algorithm & Complexity

Bit manipulation is a technique that uses bitwise operators (like AND &, OR |, XOR ^, NOT ~, shift <<, >>) for fast operations on individual bits of integers. It is especially useful in optimization, combinatorics (like subsets), and problems involving parity or states.

Common Bit Operations

• x & 1: check if x is odd
• x & (x-1): removes the lowest set bit
• __builtin_popcount(x): count 1's in x
• 1 << k: number with only the k-th bit set

Time Complexity

Most bit operations are O(1) or O(log N) depending on the size of the integer (e.g., 32 or 64-bit).

Memory Complexity

No extra memory is required beyond variables unless using masks in arrays (like dp[1<<n]).

---

2. Easy Bitwise Problems

2.1 – Codeforces 1418A - Buying Torches

Given k sticks and 1 coal, find how many operations are needed to get n sticks. Each operation uses x sticks and 1 coal to get x+1 sticks. You must simulate using math and bit tricks.

Input:
7 3 2

Output:
3

#include <iostream>
using namespace std;

int main() {
    long long n, k, x;
    cin >> n >> k >> x;
    cout << (n - 1 + (k - x - 1)) / (k - x) << '\n';
    return 0;
}

2.2 – Count Set Bits from 1 to N

Count number of 1s in binary representation of all numbers from 1 to N.

Input:
5

Output:
7   (1:1, 2:1, 3:2, 4:1, 5:2)

#include <iostream>
using namespace std;

int main() {
    int n, count = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        count += __builtin_popcount(i);
    }
    cout << count << '\n';
    return 0;
}

---

3. Intermediate Bitwise Problems

3.1 – Codeforces 1092B - Teams Forming

You are given 2n skill levels. Form n pairs such that sum of absolute differences is minimized. Hint: Sort and use bitwise XOR for differences.

Input:
4
1 3 5 9

Output:
6

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    n *= 2;
    int a[n];
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a+n);
    int sum = 0;
    for (int i = 0; i < n; i += 2) {
        sum += a[i+1] - a[i]; // or use bitwise absolute diff
    }
    cout << sum << '\n';
    return 0;
}

3.2 – Subset Sum Using Bitmask

Print all subset sums from a list using bitmask.

Input:
3
1 2 3

Output:
0 1 2 3 3 4 5 6

#include <iostream>
using namespace std;

int main() {
    int n, a[20];
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int mask = 0; mask < (1<<n); ++mask) {
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1<<i)) sum += a[i];
        }
        cout << sum << ' ';
    }
    return 0;
}

---

4. Hard Bitwise Problem

4.1 – Codeforces 842B - Gleb and Pizza

Count points that fall inside a circular crust of thickness t and radius R. Use bit tricks to speed up calculations.

Input:
5 1 5
1 1 1
2 2 1
0 0 1
4 0 1
6 0 1

Output:
3

#include <iostream>
using namespace std;

int main() {
    int n, t, R, cnt = 0;
    cin >> n >> t >> R;
    int R2 = R*R, r2 = (R-t)*(R-t);
    for (int i = 0; i < n; ++i) {
        int x, y, ri;
        cin >> x >> y >> ri;
        int dist2 = x*x + y*y;
        if ((dist2 + ri*ri <= R2) && (dist2 - ri*ri >= r2)) cnt++;
    }
    cout << cnt << '\n';
    return 0;
}