SyntaxPilot
Courses/Competitive Programming/Lesson 17

Competitive Programming · Lesson 17 of 90 · 13 min

Bit tricks: XOR properties, masks, __builtin functions

queued

These are the notes for Competitive Programming episode 17. We go one level below numbers, to the bits inside them. A hostel light switch explains XOR, and we build the bit operators &, |, ^, <<, >> from zero and watch them run. Then an original problem, Odd Bits, asks how many pairs of numbers have an XOR with an odd number of 1 bits. The brute force over every pair is correct but gets Time Limit Exceeded on 2·10^5 numbers. A small table shows the pattern, a short proof explains it (XOR cancels shared 1s two at a time), and the answer becomes odd × (n − odd) in O(n). After that: bitmasks (every subset of n items is a number), the __builtin toolbox (popcount, ctz, clz, popcountll, x & -x, x & (x - 1)), and three bugs with their real outputs. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook: the hostel corridor switch

A hostel corridor has one light and a switch at each end. At night the light is off: call that 0.

  • Press a switch: the light comes on. Press again: it goes off. A press does not set the light on or off. It toggles it.
  • Three friends walk through and each presses a switch, in any order: Ravi, Amit, Neha, or Neha first. The final state is the same. Order doesn't matter.
  • Only one thing decides the result: is the number of presses odd (light on) or even (light off)?

This toggle is called XOR in programming. Keep the switch in mind: almost every XOR trick is this picture.

Bits from zero

  • A bit is one tiny switch inside the computer: 0 or 1. An int is a row of 32 bits; a long long has 64.
  • Binary writes a number with powers of two. Reading from the right, the bits are worth 1, 2, 4, 8, … So 12 = 8 + 4 = 1100 and 10 = 8 + 2 = 1010.

The bit operators work on every bit position separately:

Operator Name Rule for each bit 12 with 10
a & b AND 1 only if both bits are 1 1100 & 1010 = 1000 = 8
a | b OR 1 if at least one bit is 1 1100 | 1010 = 1110 = 14
a ^ b XOR 1 if the bits are different 1100 ^ 1010 = 0110 = 6
1 << k shift left moves bits k places left: 2^k 1 << 3 = 1000 = 8
x >> k shift right moves bits k places right: x / 2^k, remainder dropped 12 >> 2 = 11 = 3

XOR is the light switch on every bit at once: a 1 in b toggles that bit of a, a 0 leaves it alone. That gives the three XOR facts you will use all the time:

  • x ^ x = 0 (pressing twice puts you back)
  • x ^ 0 = x (no press, no change)
  • order doesn't matter: a ^ b ^ c = c ^ a ^ b (XOR is commutative and associative)

bitset<4>(x) prints the last 4 bits of x, and __builtin_popcount(x) counts its 1 bits (the popcount: popcount(12) = 2).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int a = 12, b = 10;
    cout << bitset<4>(a) << "  a = 12\n";
    cout << bitset<4>(b) << "  b = 10\n";
    cout << bitset<4>(a & b) << "  a & b = " << (a & b) << "\n";
    cout << bitset<4>(a | b) << "  a | b = " << (a | b) << "\n";
    cout << bitset<4>(a ^ b) << "  a ^ b = " << (a ^ b) << "\n";
    cout << (a ^ b ^ b) << "  a ^ b ^ b\n";
    cout << (1 << 3) << "  1 << 3\n";
    cout << (a >> 2) << "  a >> 2\n";
    cout << __builtin_popcount(a) << "  popcount(12)\n";
    return 0;
}

Real output:

1100  a = 12
1010  b = 10
1000  a & b = 8
1110  a | b = 14
0110  a ^ b = 6
12  a ^ b ^ b
8  1 << 3
3  a >> 2
2  popcount(12)

a ^ b ^ b gives back 12: XOR with b twice cancels.

The problem: Odd Bits

Problem Q · Odd Bits (written for this course). You are given an array a of n integers, 0 ≤ a[i] < 2^30. Count the pairs i < j such that a[i] ^ a[j] has an odd number of 1 bits.

1 ≤ t ≤ 10^4 test cases, 1 ≤ n ≤ 2·10^5, the sum of n over all tests is at most 2·10^5.

Sample input Sample output
3
3
1 2 3
4
5 5 5 5
2
0 7
2
0
1

Check the first test by hand:

Pair XOR Binary 1 bits Counted?
1, 2 3 11 2 (even) no
1, 3 2 10 1 (odd) yes
2, 3 1 01 1 (odd) yes

Two odd pairs, so the answer is 2. Four equal fives give XOR 0 every time (0 bits, even): answer 0. 0 ^ 7 = 7 = 111 has 3 bits: answer 1.

The answer can be large: with n = 2·10^5 there are about 2·10^10 pairs, far more than an int holds (about 2.1·10^9). Use long long.

Brute force: every pair (Time Limit Exceeded)

Try every pair, XOR the two numbers, count the bits with __builtin_popcount, and check whether the count is odd.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &x : a) cin >> x;
        ll ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (__builtin_popcount(a[i] ^ a[j]) % 2 == 1)
                    ans++;
        cout << ans << "\n";
    }
    return 0;
}

On the sample it prints 2 0 1: correct. But n can be 2·10^5. We can't paste that many numbers, so this version builds the worst case itself:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 200000;            // worst case, built here
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = i * 7 + 3;
    ll ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (__builtin_popcount(a[i] ^ a[j]) % 2 == 1)
                ans++;
    cout << ans << "\n";
    return 0;
}
Input Output
the sample 2 0 1
no input (the program builds n = 2·10^5) Time Limit Exceeded (it was still running after 8 seconds)

Why: n²/2 = (2·10^5)² / 2 = 2·10^10 pairs, twenty billion. A judge does roughly 10^8 simple steps per second. O(n²) is hopeless here.

Step 1: print a small table

Same trick as episode 16: when you are stuck, print small cases and stare at them. For every pair a < b below 4, print the bit counts of a and b and of a ^ b:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    for (int a = 0; a < 4; a++)
        for (int b = a + 1; b < 4; b++) {
            int pa = __builtin_popcount(a), pb = __builtin_popcount(b);
            int px = __builtin_popcount(a ^ b);
            cout << a << "^" << b << "  bits " << pa << "+" << pb
                 << "  xor bits " << px << (px % 2 ? "  ODD" : "") << "\n";
        }
    return 0;
}

Real output:

0^1  bits 0+1  xor bits 1  ODD
0^2  bits 0+1  xor bits 1  ODD
0^3  bits 0+2  xor bits 2
1^2  bits 1+1  xor bits 2
1^3  bits 1+2  xor bits 1  ODD
2^3  bits 1+2  xor bits 1  ODD

In every ODD row one number has an even bit count and the other an odd one (0 + 1, 1 + 2). In 1^2 (1 + 1) and 0^3 (0 + 2) both counts have the same parity and the XOR is even.

Parity means "odd or even". The guess: popcount(a ^ b) is odd exactly when popcount(a) and popcount(b) have different parities.

Step 2: the proof

Take a = 12 and b = 10, bit by bit:

bit 3 bit 2 bit 1 bit 0 1 bits
a = 12 1 1 0 0 2
b = 10 1 0 1 0 2
a & b (shared 1s) 1 0 0 0 1
a ^ b 0 1 1 0 2

Together a and b have 2 + 2 = 4 ones. XOR keeps a 1 only where the bits differ. Where both bits are 1 (bit 3 here), both ones vanish together: always two at a time. So

popcount(a ^ b) = popcount(a) + popcount(b) − 2 · popcount(a & b)
                 2           =      2       +      2       −  2 · 1

Subtracting an even number never changes odd/even. So popcount(a ^ b) has the same parity as popcount(a) + popcount(b), and

  • odd + even = odd,
  • even + even = even, odd + odd = even.

Proved: the pair counts exactly when one number has an odd bit count and the other an even one.

From pairs to counting

Call a number ODD if its popcount is odd and EVEN otherwise. A pair counts ⇔ it has one ODD and one EVEN number. So we never need to look at pairs:

  1. Count the ODD numbers: call it odd. The other n − odd are EVEN.
  2. Every ODD number pairs with every EVEN number:
answer = odd × (n − odd)

Check on [1, 2, 3]: 1 and 2 have one bit each (ODD), 3 has two (EVEN). 2 × 1 = 2. Matches.

Step 3: the O(n) solution

__builtin_popcount(x) & 1 is the last bit of the count: 1 if the count is odd.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &x : a) cin >> x;
        ll odd = 0;
        for (int x : a)
            if (__builtin_popcount(x) & 1) odd++;
        cout << odd * (n - odd) << "\n";
    }
    return 0;
}
Input Output Why
the sample 2 0 1 as computed above
3
1
9
2
1 2
5
1 2 4 8 16
0
0
0
one number has no pairs; 1 and 2 are both ODD (their XOR 11 has 2 bits); every power of two has exactly one bit, so there is no EVEN partner

And the worst case that timed out:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 200000;            // worst case, built here
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = i * 7 + 3;
    ll odd = 0;
    for (int x : a)
        if (__builtin_popcount(x) & 1) odd++;
    cout << odd * (n - odd) << "\n";
    return 0;
}

Real output: 9999970759, instantly. Almost ten billion odd pairs, counted in 2·10^5 steps instead of 2·10^10.

Stress test

We proved the rule, but a stress test checks that the code matches the proof: run the brute force and the fast formula on many random small arrays and compare. mt19937 is C++'s random number generator; a fixed seed (17) makes the run repeatable.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll brute(vector<int> &a) {
    ll ans = 0;
    for (int i = 0; i < (int)a.size(); i++)
        for (int j = i + 1; j < (int)a.size(); j++)
            ans += __builtin_popcount(a[i] ^ a[j]) % 2;
    return ans;
}

ll fast(vector<int> &a) {
    ll odd = 0;
    for (int x : a) odd += __builtin_popcount(x) & 1;
    return odd * ((ll)a.size() - odd);
}

int main() {
    mt19937 rng(17);
    for (int it = 1; it <= 1000; it++) {
        int n = rng() % 10 + 1;
        vector<int> a(n);
        for (auto &x : a) x = rng() % 1000;
        if (brute(a) != fast(a)) {
            cout << "DIFF on test " << it << "\n";
            return 0;
        }
    }
    cout << "OK: 1000 random tests agree\n";
    return 0;
}

Real output: OK: 1000 random tests agree.

Part 2: bitmasks, subsets as numbers

Real-life example: a tick-box tiffin order. An office tiffin form lists 4 dishes (dal, rice, roti, salad), each with a tick box.

Tiffin form In code
a row of tick boxes a mask: bit i = 1 ⇔ dish i is ticked
every possible way to fill the form (2^4 = 16) for (mask = 0; mask < (1 << n); mask++): every subset, once
how many dishes were ordered __builtin_popcount(mask): the subset's size

A subset is any selection of items from a set, including none or all. With n items there are 2^n subsets, and the numbers 0 … 2^n − 1 list them all. A mask is a number used this way, each bit saying yes or no. To test bit i: mask >> i & 1 (shift bit i down to the last place, keep only that bit).

Problem: 4 dishes cost 30, 50, 70, 20 rupees. How many ways are there to pick exactly k = 2 dishes for at most B = 100 rupees?

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 4, k = 2, B = 100;
    int price[] = {30, 50, 70, 20};
    int ways = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (__builtin_popcount(mask) != k) continue;
        int sum = 0;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1) sum += price[i];
        if (sum <= B) {
            ways++;
            cout << bitset<4>(mask) << "  sum = " << sum << "\n";
        }
    }
    cout << "ways = " << ways << "\n";
    return 0;
}

Real output:

0011  sum = 80
0101  sum = 100
1001  sum = 50
1010  sum = 70
1100  sum = 90
ways = 5

Read each mask from the right: 0011 is dishes 0 and 1, 30 + 50 = 80. There are 6 pairs of dishes; the missing one, 0110 (dishes 1 and 2), costs 50 + 70 = 120 > 100.

The loop does 2^n · n steps: fine up to n ≈ 20 (about 2·10^7), hopeless beyond.

The builtin toolbox

GCC (the compiler behind g++) has built-in functions that work on bits in one step:

Function / expression What it gives x = 40 = 00101000
__builtin_popcount(x) number of 1 bits 2
__builtin_ctz(x) ctz, "count trailing zeros": zeros at the end (right) 3
__builtin_clz(x) clz, "count leading zeros": zeros at the front of all 32 bits 26
x & -x the lowest set bit (the rightmost 1) alone 8
x & (x - 1) x with its lowest set bit removed 32
__builtin_popcountll(y) popcount for a 64-bit long long 1LL << 40 → 1

Why x & -x works: computers store -x as ~x + 1 (two's complement: flip every bit, add 1). The +1 carries through the trailing zeros of ~x and stops at the lowest 1 of x, so x and -x share exactly that one bit. Why x & (x - 1) works: subtracting 1 turns the lowest 1 into 0 and the zeros below it into 1s; AND with x wipes them all.

ctz and clz are undefined for 0: there is no 1 bit to find, so the result is meaningless. Check x != 0 first.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    unsigned x = 40;
    cout << bitset<8>(x) << "  x = 40\n";
    cout << __builtin_popcount(x) << "  popcount\n";
    cout << __builtin_ctz(x) << "  ctz (zeros at the end)\n";
    cout << __builtin_clz(x) << "  clz (zeros at the front)\n";
    cout << (x & -x) << "  x & -x (lowest 1 bit)\n";
    cout << (x & (x - 1)) << "  x & (x - 1) (drop it)\n";
    long long y = 1LL << 40;
    cout << __builtin_popcountll(y) << "  popcountll(2^40)\n";
    return 0;
}

Real output:

00101000  x = 40
2  popcount
3  ctz (zeros at the end)
26  clz (zeros at the front)
8  x & -x (lowest 1 bit)
32  x & (x - 1) (drop it)
1  popcountll(2^40)

clz is 26 because 40's highest 1 is bit 5, and 31 − 5 = 26. Each builtin also has an ll version for 64 bits: __builtin_ctzll, __builtin_clzll, __builtin_popcountll.

Solutions in C++, Java and Python

The full Odd Bits solution: count numbers with an odd popcount, print odd × (n − odd).

C++: the O(n) program in Step 3 above.

Java (tested: 2 0 1 on the sample, 0 0 0 on the edge cases, and 9999970759 on the 2·10^5-number worst case). Integer.bitCount is Java's popcount.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken();
        int t = (int) st.nval;
        StringBuilder out = new StringBuilder();
        while (t-- > 0) {
            st.nextToken();
            int n = (int) st.nval;
            long odd = 0;
            for (int i = 0; i < n; i++) {
                st.nextToken();
                int x = (int) st.nval;
                if ((Integer.bitCount(x) & 1) == 1) odd++;
            }
            out.append(odd * (n - odd)).append('\n');
        }
        System.out.print(out);
    }
}

Python (tested with the same three inputs, same outputs). bin(x).count("1") is the popcount; on Python 3.10+ you can also write x.bit_count(). Python integers never overflow.

import sys

def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    pos = 1
    out = []
    for _ in range(t):
        n = int(data[pos]); pos += 1
        odd = 0
        for i in range(pos, pos + n):
            odd += bin(int(data[i])).count("1") & 1
        pos += n
        out.append(str(odd * (n - odd)))
    print("\n".join(out))

main()

Brute force vs optimal

Brute force (all pairs) Parity count Masks (all subsets)
Time O(n²) O(n) (popcount is one machine instruction on modern CPUs) O(2^n · n)
Extra memory O(n) O(n) (O(1) if you count while reading) O(1)
n = 2·10^5 ≈ 2·10^10 pair checks: TLE 2·10^5 steps: instant impossible
n = 20 190 pairs 20 steps ≈ 2·10^7 steps: fine

Common mistakes (and the real outputs)

Bug 1: operator precedence. A friend counts the EVEN numbers instead (the answer is the same, even × (n − even)):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &x : a) cin >> x;
        ll even = 0;
        for (int x : a)
            if (__builtin_popcount(x) & 1 == 0) even++;
        cout << even * (n - even) << "\n";
    }
    return 0;
}

On the sample it prints 0 0 0 instead of 2 0 1, with no compiler warning. Operator precedence is the order in which C++ applies operators, and == binds tighter than &. So the condition is popcount(x) & (1 == 0) = popcount(x) & 0 = always 0. Write (__builtin_popcount(x) & 1) == 0.

Bug 2: overflow. The worst-case program with int odd instead of ll odd:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 200000;            // worst case, built here
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = i * 7 + 3;
    int odd = 0;
    for (int x : a)
        if (__builtin_popcount(x) & 1) odd++;
    cout << odd * (n - odd) << "\n";
    return 0;
}

Real output: 1410036167 instead of 9999970759. About 10^5 × 10^5 = 10^10 does not fit in an int (max 2147483647), so the product overflows: it wraps around (here, exactly 9999970759 − 2·2^32). No error, just a wrong answer. (Signed overflow is officially undefined behaviour in C++, so don't count on any particular wrong value.)

Bug 3: popcount on a long long. The toolbox program with one line changed:

    cout << __builtin_popcount(y) << "  popcount(2^40)\n";

Real output for that line: 0 popcount(2^40) (the other six lines are unchanged). __builtin_popcount takes a 32-bit unsigned int, so the 1 at bit 40 is cut off before counting. Use __builtin_popcountll.

Mistake What you see Why Fix
if (__builtin_popcount(x) & 1 == 0) 0 0 0 instead of 2 0 1 == binds tighter than & (__builtin_popcount(x) & 1) == 0
int odd; … odd * (n - odd) 1410036167 instead of 9999970759 10^10 overflows int ll odd
__builtin_popcount(1LL << 40) 0 instead of 1 the argument is cut to 32 bits __builtin_popcountll
__builtin_ctz(0), __builtin_clz(0) a meaningless number, no error undefined for 0 check x != 0 first

Rule of thumb: brackets around every bit operation, ll for big answers, ll builtins for 64-bit values, and never ctz/clz of zero.

Mini project

Build a bit inspector: read a number x (up to 10^18) and print its binary form (bitset<64>), popcount, parity, ctz, clz (only if x != 0), lowest set bit, x with that bit removed, and whether x is a power of two. Then treat x as a mask and list every subset of its 1 bits with for (ll s = x; s > 0; s = (s - 1) & x). Use ll and the ll builtins throughout, and test it on 0, 1, 40 and 1LL << 40.

Practice

  1. (Homework 1) Every value in an array appears twice except one. Find it in O(n) time and O(1) extra memory.

    Answer XOR all the values. Each pair cancels (<code>x ^ x = 0</code>), order doesn't matter, and <code>0 ^ y = y</code>, so only the single value survives. For <code>{4, 7, 1, 7, 4}</code> the program <code>int x = 0; for (int v : a) x ^= v;</code> prints <code>1</code> (run and checked).

  2. (Homework 2) Count the pairs i < j whose XOR has an even number of 1 bits.

    Answer A pair is even ⇔ both numbers are ODD or both are EVEN. With <code>even = n − odd</code>: answer = <code>odd·(odd − 1)/2 + even·(even − 1)/2</code> (equivalently, all n(n − 1)/2 pairs minus <code>odd·(n − odd)</code>). Use <code>long long</code>. Run on the sample it prints <code>1 6 0</code>; on the edge cases <code>0 1 10</code>.

  3. (Homework 3) Find the total number of 1 bits in all numbers from 1 to n, for n ≤ 10^18.

    Answer Count bit by bit. Bit k repeats a pattern of 2^k zeros then 2^k ones, every 2^(k+1) numbers. Among 0 … n there are <code>full = (n + 1) / 2^(k+1)</code> complete blocks giving <code>full · 2^k</code> ones, plus <code>max(0, (n + 1) % 2^(k+1) − 2^k)</code> from the leftover part. Sum over k = 0 … 59: O(log n). n = 10 gives 17, n = 7 gives 12, and n = 10^18 gives <code>29761222783429247000</code>, which is larger than the <code>long long</code> maximum (≈ 9.22·10^18), so the total must be kept in <code>__int128</code> (or Python). Checked against a brute force for every n below 5000.

  4. (Homework 4) With masks: n ≤ 20 weights; count the subsets whose sum is exactly S.

    Answer Loop <code>mask</code> from 0 to <code>(1 << n) − 1</code>, add <code>w[i]</code> for every bit <code>mask >> i & 1</code>, count the masks with sum == S. O(2^n · n). For weights <code>{2, 3, 5, 7, 8}</code> and S = 10 it prints <code>3</code>: {2, 8}, {3, 7}, {2, 3, 5}.

  5. How can you check in O(1) whether a positive integer is a power of two?

    Answer A power of two has exactly one 1 bit, and <code>x & (x − 1)</code> removes the lowest one, so: <code>x > 0 && (x & (x - 1)) == 0</code> (note the brackets!). Run on 1, 6, 64, 96 it prints YES, NO, YES, NO. <code>__builtin_popcount(x) == 1</code> also works.

Quick quiz

a = {3, 5, 6, 7}. How many Odd Bits pairs? (Bits: 3 = 011, 5 = 101, 6 = 110, 7 = 111.)

A) 0 · B) 2 · C) 3 · D) 4

Answer

C. 3, 5 and 6 have two 1 bits (EVEN), 7 has three (ODD). odd = 1, so the answer is 1 × 3 = 3. Both the brute force and the O(n) program print 3.

Interview questions

  1. What are the main properties of XOR? x ^ x = 0, x ^ 0 = x, and it is commutative and associative, so a list of XORs can be done in any order and equal values cancel in pairs.
  2. How do you find a unique or missing element with XOR? XOR everything: duplicates cancel. For "the missing number from 0 … n", XOR all of 0 … n together with all array values; every present number appears twice and cancels.
  3. How do you test, set, clear and toggle bit i? Test (x >> i) & 1, set x | (1 << i), clear x & ~(1 << i), toggle x ^ (1 << i) (use 1LL for i ≥ 31).
  4. What does x & (x - 1) do, and what is it used for? It removes the lowest set bit: checking powers of two, or counting bits by looping while (x) { x &= x - 1; cnt++; }.
  5. When are bitmask subsets a good idea? When n is about 20 or less: 2^20 ≈ 10^6 masks. For n ≈ 40, split in halves (meet in the middle, next episode).
  6. Why is __builtin_ctz(0) dangerous? It is undefined behaviour: there is no 1 bit, so the result is meaningless and differs between machines.

Glossary

Term Meaning Example
Bit One binary digit, a switch that is 0 or 1 an int has 32 bits
Binary Writing numbers with powers of two (1, 2, 4, 8, … from the right) 12 = 1100
AND (&) Bit is 1 only if both bits are 1 12 & 10 = 8
OR (|) Bit is 1 if at least one bit is 1 12 | 10 = 14
XOR (^) Bit is 1 if the bits differ: a toggle 12 ^ 10 = 6, x ^ x = 0
Toggle Switch between two states light off → on → off
Shift left (<<) Move bits left; 1 << k = 2^k 1 << 3 = 8
Shift right (>>) Move bits right; divides by 2^k, dropping the remainder 12 >> 2 = 3
bitset<k>(x) Prints the last k bits of x bitset<4>(12) → 1100
Popcount Number of 1 bits __builtin_popcount(12) = 2
Parity Whether a number is odd or even popcount 3: odd parity
ODD / EVEN number (this episode) A number whose popcount is odd / even 7 is ODD, 3 is EVEN
Commutative, associative Order and grouping do not change the result a ^ b ^ c = c ^ a ^ b
Mask An integer whose bits mean yes/no for each item 0011 = dishes 0 and 1
Subset Any selection of items (none, some or all) 4 items → 16 subsets
mask >> i & 1 Tests whether bit i of mask is 1 5 >> 2 & 1 = 1
ctz Count trailing zeros (zeros at the end) __builtin_ctz(40) = 3
clz Count leading zeros (zeros at the front of 32 bits) __builtin_clz(40) = 26
popcountll, ctzll, clzll The 64-bit (long long) versions __builtin_popcountll(1LL << 40) = 1
Lowest set bit The rightmost 1 bit, alone: x & -x 40 & -40 = 8
x & (x - 1) x with its lowest set bit removed 40 & 39 = 32
Two's complement How negatives are stored: -x = ~x + 1 why x & -x works
unsigned An integer type with no negative values unsigned x = 40;
Overflow A value too big for its type wraps around int product → 1410036167
long long (ll) 64-bit integer, up to about 9.2·10^18 ll odd
__int128 128-bit integer in g++, for even bigger values homework 3's total
Operator precedence The order operators are applied in x & 1 == 0 means x & (1 == 0)
Undefined behaviour C++ makes no promise about the result __builtin_ctz(0)
Brute force Try every possibility; slow but surely correct all n²/2 pairs
Time Limit Exceeded (TLE) The program ran longer than the judge allows brute force at n = 2·10^5
Observation A fact about the problem that makes it easy "only parities matter"
Stress test Compare a fast solution with a brute force on many random inputs 1000 random arrays
mt19937 C++ random number generator mt19937 rng(17)
Sum of n constraint A limit on the total size of all test cases sum n ≤ 2·10^5

Summary

  • Bits from zero: & (both), | (either), ^ (different), << (×2^k), >> (÷2^k), checked live with bitset.
  • XOR is a toggle: x ^ x = 0, x ^ 0 = x, order doesn't matter.
  • Odd Bits: the O(n²) brute force got TLE at n = 2·10^5.
  • A small table and a proof: popcount(a ^ b) = popcount(a) + popcount(b) − 2·popcount(a & b), so parity survives XOR.
  • Answer odd × (n − odd) in O(n): 9999970759 instantly; 1000 random tests agreed with the brute force.
  • A mask is a subset: loop to 1 << n, size = popcount, fine up to n ≈ 20.
  • Builtins: popcount, ctz, clz, popcountll, x & -x, x & (x - 1).
  • Real bugs: & 1 == 0 (0 0 0), int overflow (1410036167), popcount on long long (0).

Next episode: Meet in the middle.