i. Bit Tricks and XOR

Bitwise operations act on every bit independently, with no carries. That one fact powers per-bit counting, MSB-first greedy, XOR prefix tricks and bitmask states. Submask enumeration, SOS DP, transforms and the XOR basis each have their own notes in this chapter.

Core idioms

Expression	Meaning
`x >> i & 1`	bit $i$
`x \| 1 << i`, `x & ~(1 << i)`, `x ^ 1 << i`	set, clear, toggle bit $i$
`x & -x`	lowest set bit (as a value): `lowbit`
`x & (x - 1)`	clear the lowest set bit
`x \| (x + 1)`	set the lowest clear bit
`x & (x + 1)`	clear the trailing ones
`~x & (x + 1)`	lowest clear bit (as a value)
`x ^ (x + 1)`	mask of the trailing ones plus the next bit
`x && !(x & (x - 1))`	power of two
`(1 << k) - 1`	low $k$ bits
`(a & b) == a`	$a \subseteq b$
`x ^ (x >> 1)`	Gray code
`~(a & b)`, `~(a \| b)`, `~(a ^ b)`	NAND, NOR, XNOR
`x & ~((1 << k) - 1)`, `(x + (1 << k) - 1) & ~((1 << k) - 1)`	round down / up to a multiple of $2^{k}$

Every integer is a sum of distinct powers of two ( $26 = 2^{4} + 2^{3} + 2^{1} = 1101 0_{2}$ ); every bit operation below is just a statement about that expansion.

Use 1LL << i for $i \geq 31$ , and 1ULL << 63 for the top bit. Shifting by $\geq$ the width is undefined behaviour. Right-shifting a negative signed integer is an arithmetic shift in practice (and guaranteed since C++20), so -7 >> 1 == -4, which is floor division.

Builtins

GCC builtin (`ll` suffix for 64-bit)	C++20 `<bit>` (unsigned only)	Result
`__builtin_popcount(x)`	`popcount(x)`	number of set bits
`__builtin_ctz(x)`	`countr_zero(x)`	trailing zeros (undefined for 0 with the builtin)
`__builtin_clz(x)`	`countl_zero(x)`	leading zeros (undefined for 0 with the builtin)
`__lg(x)`, `31 - __builtin_clz(x)`	`bit_width(x) - 1`	$⌊ lo g_{2} x ⌋$
`__builtin_parity(x)`	`popcount(x) & 1`	parity
`__builtin_ffs(x)`		index of the lowest set bit, 1-based (0 if $x = 0$ ); `__builtin_ffsll` for 64-bit
`__builtin_bswap32/64(x)`		byte swap
	`bit_ceil(x)`, `bit_floor(x)`	next / previous power of two
	`rotl`, `rotr`	rotations

With #pragma GCC target("popcnt") these compile to single instructions; without it, __builtin_popcount calls a slower routine.

Arithmetic identities

$a + b = (a \oplus b) + 2 (a & b) = (a ∣ b) + (a & b), a \oplus b = (a ∣ b) - (a & b) .$

Proof: $a + b = (a \oplus b) + 2 (a & b)$

Binary addition, bit by bit, is two independent computations: the sum bit ignoring carries, and the carry generated. XOR gives exactly the carry-free sum at each position ( $0 + 0, 1 + 1 \to 0$ ; $0 + 1, 1 + 0 \to 1$ , matching $\oplus$ ), and AND gives exactly the positions where a carry into the next bit is generated (only $1 + 1$ carries). Each such carry is worth $2$ at its own position (it lands one bit higher), so the total carry contribution is $2 (a & b)$ . Summing the carry-free part and the carry contribution reconstructs ordinary addition: $a + b = (a \oplus b) + 2 (a & b)$ . The second form follows from $a ∣ b = (a \oplus b) + (a & b)$ (every bit set in $a ∣ b$ is either set in exactly one of $a, b$ , counted once by $\oplus$ , or set in both, counted once by $\oplus$ as $0$ and once by $&$ ), substituted into the first identity. $■$

Consequences:

$a + b = a \oplus b ⟺ a & b = 0$ .
Given $s = a + b$ and $x = a \oplus b$ : $a & b = (s - x) /2$ , which must be a non-negative integer with $(s - x) /2 & x = 0$ . Then the pairs $(a, b)$ number $2^{popcount (x)}$ (minus the ones with a zero, if positives are required).
In interactive problems, querying $a ∣ b$ and $a & b$ (or $a \oplus b$ ) gives $a + b$ , and three pairwise sums recover three numbers.
$a & b \leq min (a, b) \leq max (a, b) \leq a ∣ b \leq a + b$ , and $a \oplus b \leq a ∣ b$ .
$∣ a - b ∣ \leq a \oplus b \leq a + b$ : XOR is subtraction (and addition) without borrows (carries).
When guessing an inequality between bitwise and arithmetic expressions, brute-force all pairs below 64 first.

XOR facts

XOR is addition in $F_{2}^{k}$ : associative, commutative, $x \oplus x = 0$ , every element is its own inverse. So “XOR of a range” is a prefix difference: $a_{l} \oplus \dots \oplus a_{r} = p_{r + 1} \oplus p_{l}$ .
$0 \oplus 1 \oplus \dots \oplus n = n, 1, n + 1, 0$ for $n mod 4 = 0, 1, 2, 3$ .
Unique element when all others appear twice: XOR everything. Two unique elements: XOR everything to get $x \oplus y$ , split the numbers by any set bit of it, XOR each group. Element appearing once when others appear three times: count each bit mod 3.
Subarrays with XOR $= k$ : count pairs of prefixes with $p_{i} \oplus p_{j} = k$ via a hash map.
Tree paths: $xor (u, v) = d_{u} \oplus d_{v}$ where $d$ is the root-to-vertex XOR (the LCA part cancels).
Minimum XOR pair of a set is attained by two elements adjacent in sorted order. Maximum XOR pair needs a binary trie (Binary Trie).
Maximum $a \oplus b$ with $l \leq a \leq b \leq r$ : $2^{bit_width (l \oplus r)} - 1$ .
Maximum subset XOR, $k$ -th subset XOR, is $x$ representable: XOR basis (XOR Basis).
Sum of pairwise XORs / ANDs / ORs: count ones per bit, $c_{b}$ . Then the XOR sum is $\sum_{b} c_{b} (n - c_{b}) 2^{b}$ , the AND sum is $\sum_{b} (2 c _{b}) 2^{b}$ , and the OR sum is $\sum_{b} ((2 n) - (2 n - c _{b})) 2^{b}$ .
Nim: a position is losing for the player to move iff the XOR of the pile sizes is 0 (Combinatorial Games and Nim).

Per-bit independence and MSB greedy

Independence: for AND/OR/XOR expressions, solve each bit separately and add $2^{b} \times$ (count for bit $b$ ). This turns sums over pairs or subarrays of bitwise values into $O (n lo g V)$ counting.

MSB-first greedy: $2^{k} > 2^{k} - 1 = \sum_{i < k} 2^{i}$ , so securing a 1 at bit $k$ beats any combination of lower bits. Decide bits from the top and never revisit. Patterns:

maximum AND of two elements: for $b$ from high to low, keep the candidate prefix ans | 1 << b if at least two numbers contain it as a submask;
maximum AND of $k$ elements, maximum OR with constraints, minimum OR of a partition into $k$ segments: same “try to fix this bit, check feasibility” loop;
find $x$ minimising $max_{i} (a_{i} \oplus x)$ : recurse on the top bit, splitting the set (or a trie) when both values appear;
choose $x \leq K$ maximising $\sum (a_{i} \oplus x)$ : go through bits from high to low, staying tight with $K$ as in digit DP.

Iterating over bits and masks

for (ull m = x; m; m &= m - 1) { int i = __builtin_ctzll(m); /* each set bit i */ }
for (int s = m; ; s = (s - 1) & m) { /* each submask, decreasing */ if (!s) break; }
for (int s = m; s < 1 << n; s = (s + 1) | m) { /* each supermask */ }
// next mask with the same popcount (Gosper's hack): enumerate k-subsets in increasing order
unsigned nxt(unsigned v) { unsigned t = v | (v - 1); return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1)); }

Sets as masks: union |, intersection &, difference a & ~b, symmetric difference ^, complement within $n$ bits full ^ a, size popcount.

Other tricks

Reverse bits of a 32-bit word: swap halves, then bytes, nibbles, pairs, single bits with masks (0x55555555, 0x33333333, 0x0f0f0f0f, …), or a 256-entry table.
Popcount table for 16-bit chunks when computing many popcounts of 64-bit words without hardware support.
Highest power of two dividing $n$ : n & -n. $v_{2} (n)$ : __builtin_ctzll(n).
Sign without branches: (x > 0) - (x < 0). Absolute value: (x ^ (x >> 63)) - (x >> 63) for 64-bit. min/max without branches: y ^ ((x ^ y) & -(x < y)).
Swap via XOR: a ^= b ^= a ^= b is undefined when a and b alias; use swap.
Bit-parallel tricks: comparing 8 bytes at once, finding a zero byte with (v - 0x0101..) & ~v & 0x8080.., SWAR popcount. These matter only in constant-factor battles; bitset covers most contest uses (Bitset), including the GCC extensions _Find_first/_Find_next which iterate only the set bits of a sparse bitset in $O (popcount \cdot n /64)$ instead of $O (n)$ .

Boolean algebra identities

The laws behind every simplification of an AND/OR/NOT expression (XOR-specific identities are in “XOR facts” above):

Law	AND / OR form
Identity	$a \land 1 = a, a \lor 0 = a$
Null	$a \land 0 = 0, a \lor 1 = 1$
Idempotent	$a \land a = a, a \lor a = a$
Complement	$a \land \neg a = 0, a \lor \neg a = 1$
Double negation	$\neg (\neg a) = a$
Distributive	$a \land (b \lor c) = (a \land b) \lor (a \land c)$ , and the dual
Absorption	$a \lor (a \land b) = a, a \land (a \lor b) = a$
De Morgan	$\neg (a \land b) = \neg a \lor \neg b, \neg (a \lor b) = \neg a \land \neg b$

Common problems

Problem	Approach
count pairs with $a_{i} & a_{j} = 0$	SOS over complements (SOS DP)
count pairs with $a_{i} \oplus a_{j} \leq k$	binary trie, walking bits of $k$
subarrays with OR $\geq k$	two pointers with bit counts, or $O (lo g V)$ distinct ORs per right end
minimise $\sum (a_{i} \oplus x)$	each bit independently: set bit $b$ of $x$ if most $a_{i}$ have it
construct $n$ distinct numbers with XOR $x$	fill with small distinct numbers, fix the last two with high bits
XOR of all pairwise sums	per bit $b$ , count pairs whose sum has bit $b$ set: sort values mod $2^{b + 1}$ , two pointers on two ranges
Gray code and Hamiltonian paths on the hypercube	Gray Code
tiling / frontier DP where the mask is a fill-pattern, not an item subset	broken-profile DP (Profile DP)

whoashish's cp notes

Directory