XOR Tricks & Bitwise Algorithms

1. Algorithm & Complexity

Many “XOR Tricks” hinge on these core properties of bitwise exclusive-OR (^):

• a ^ a = 0
• a ^ 0 = a
• Commutative & associative: a ^ b = b ^ a, (a ^ b) ^ c = a ^ (b ^ c)

A common pattern is to build a prefix-xor array px[0]=0, px[i]=px[i–1] ^ a[i]. Then the xor of any subarray a[l…r] is px[r] ^ px[l–1] in O(1) time.

Time Complexity

For most XOR-trick solutions you scan the array once (O(n)) or do one pass plus some log-factor data-structure operations (O(n log n)).

Memory Complexity

You typically store:

• The input array, O(n).
• A prefix-xor array or small extra arrays/maps, O(n).

2. Easy Problems

2.1 – Ultra-Fast Mathematician (Codeforces 61A)

Given two binary strings of equal length, output a new string where each bit is the bitwise XOR of the corresponding bits.

Input:
10101
00111

Output:
10010

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

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size();
    string ans(n, '0');
    for (int i = 0; i < n; i++) {
        // XOR of '0'/'1' characters:
        ans[i] = (a[i] != b[i] ? '1' : '0');
    }
    cout << ans << "\n";
    return 0;
}

2.2 – XOR Mixup (Codeforces 1698A)

Given an array of n–1 integers, append one number so that the total XOR of the array becomes zero. Output that number.

Input:
5
1 2 3 4

Output:
4

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int x = 0, v;
    for (int i = 0; i < n-1; i++) {
        cin >> v;
        x ^= v;          // accumulate XOR of given elements
    }
    cout << x << "\n"; // x ^ x = 0, so appending x zeroes total XOR
    return 0;
}

3. Intermediate Problems

3.1 – XOR Queries (Codeforces #trending)

You have an array a[1…n] and q queries of form (l, r). For each query, print a[l] ^ a[l+1] ^ … ^ a[r].

Input:
5 3
1 2 3 4 5
1 3
2 5
1 5

Output:
0
4
1

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n+1), px(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        px[i] = px[i-1] ^ a[i];  
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << (px[r] ^ px[l-1]) << "\n";
    }
    return 0;
}

3.2 – Count Pairs with Given XOR (Codeforces #practice)

Given an array and a target K, count pairs (i, j), i with a[i] ^ a[j] = K.

Input:
5 2
1 3 1 1 2

Output:
3

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, K;
    cin >> n >> K;
    unordered_map<int,int> freq;
    long long ans = 0;
    for (int i = 0, x; i < n; i++) {
        cin >> x;
        // For current x, any previous y with (y ^ x) = K ⇒ y = x ^ K
        ans += freq[x ^ K];
        freq[x]++;
    }
    cout << ans << "\n";
    return 0;
}

Input:
5 3
1 2 3 4 5
1 2
1 3
3 4
3 5
4
5
2

Output:
1^3^4 = 6
1^3^5 = 7
1^2   = 3

#include <iiostream>
#include <vector>
using namespace std;

static const int MAXN = 200000;
vector<int> adj[MAXN+1];
int a[MAXN+1], px[MAXN+1];

void dfs(int u, int p) {
    // px[u] = xor of path from root (1) to u
    px[u] = px[p] ^ a[u];
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // Precompute prefix-xor along root-to-node paths
    px[0] = 0;
    dfs(1, 0);

    while (q--) {
        int u;
        cin >> u;
        cout << px[u] << "\n";
    }
    return 0;
}