Bit Manipulation

Quick Revisit

• USE WHEN: n <= 20 and you need subsets, or when XOR/AND/OR properties simplify the problem
• INVARIANT: Each bit represents membership; x & (-x) isolates lowest set bit; x & (x-1) clears it
• TIME: O(2^n) subset enumeration | SPACE: O(2^n) for bitmask DP
• CLASSIC BUG: Using int instead of long long for masks when n > 30 (1 << 31 is UB)
• PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

Bit manipulation encodes set operations as integer arithmetic, turning subset enumeration, membership tests, and combinatorial searches into tight loops over plain integers. It is the backbone of bitmask DP and dominates every CP problem where $n\le 20$.

Difficulty: Beginner–Advanced | CF Rating: 1100–2100 | Prerequisites: Arrays & Strings

---

Contents

• If I Had 5 Minutes
• Intuition
• C++ STL Reference
• Implementation
• Operations Reference
• Patterns
• Before You Code Checklist
• Contest Cheat Sheet
• When NOT to Use This
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading
• What to Solve Next

---

If I Had 5 Minutes

Speed reference—the five things you must know cold:

1. Subset = integer. An $n$-element subset is an $n$-bit mask; iterate with for (int m = 0; m < (1<<n); m++).
2. The Big Three builtins: __builtin_popcount(x), __builtin_ctz(x) (UB if 0), __builtin_clz(x) (UB if 0).
3. Lowest set bit = x & (-x) (Fenwick tree core). Clear it = x & (x-1) (popcount loop core).
4. XOR cancels pairs: a ^ a = 0. Prefix XOR gives range XOR in $O(1)$, just like prefix sums.
5. $n\le 20$ = bitmask. No exceptions. $n\le 40$ = meet in the middle with bitmasks.

---

Intuition

You're reading a Codeforces problem: "Given an array of $n\le 20$ elements, check if any subset sums to $S$." Your first instinct is recursion—include or exclude each element. But that means $2^{20}$ recursive calls with vectors, allocation, and copying everywhere. There has to be a way to represent each subset as a single number and loop through all of them. There is—and the key is something your computer already does.

What Is Binary Representation?

Computers store everything as sequences of 0s and 1s. Each digit is called a bit (binary digit). Just like decimal uses powers of 10, binary uses powers of 2:

  Decimal 13 = 1*10^1  + 3*10^0
             = 10       + 3

  Binary  1101 = 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0
               = 8     + 4     + 0     + 1
               = 13

Converting decimal to binary—repeatedly divide by 2 and read remainders bottom-up:

  13 / 2 = 6  remainder 1   ^
   6 / 2 = 3  remainder 0   |   read upward: 1101
   3 / 2 = 1  remainder 1   |
   1 / 2 = 0  remainder 1   |

A few values to memorise:

  Decimal :  0    1    2    3    4    5    6    7    8   15   16
  Binary  : 0000 0001 0010 0011 0100 0101 0110 0111 1000 1111 10000

So every non-negative integer already is a string of bits.

The Subset-Sum Problem

Now consider this problem: "Check if any subset of $[3,1,4,1,5]$ sums to 6."

The brute-force approach: list every subset and check its sum. With $n=5$ elements there are $2^5=32$ subsets:

  Subset            Sum   == 6?
  {}                  0    no
  {3}                 3    no
  {1}                 1    no
  {4}                 4    no
  {1}                 1    no
  {5}                 5    no
  {3,1}              4    no
  {3,4}              7    no
  ...                ...
  {1,4,1}            6    YES!     <-- found
  ...
  {3,1,4,1,5}       14    no

Writing the brute force with nested loops would mean 5 nested for loops. For $n=20$: 20 nested loops—clearly impractical to type. Even a recursive solution that builds subsets by include/exclude decisions needs vectors, allocation, and copying.

We need a way to represent any subset as a single number and iterate through all $2^n$ subsets with one for-loop.

---

Every subset of $n$ elements maps to an $n$-bit number. Bit operations let you manipulate sets in $O(1)$ per operation.

Think of $n$ light switches on a wall, labelled $0,1,\dots ,n-1$. Each switch is ON (1) or OFF (0). The pattern of switches uniquely describes a selection—and that pattern, read as a binary number, is the bitmask.

For $[3,1,4,1,5]$ with indices $0\dots 4$:

  index:   4   3   2   1   0
  element: 5   1   4   1   3

  Subset {3, 4, 1[index 1]}  -->  bits:  0  0  1  1  1  --> mask = 00111 = 7
  Subset {5, 1[index 3]}     -->  bits:  1  1  0  0  0  --> mask = 11000 = 24
  Full set                   -->  bits:  1  1  1  1  1  --> mask = 11111 = 31
  Empty set                  -->  bits:  0  0  0  0  0  --> mask = 00000 = 0

So the 32-subset brute force becomes:

for (int mask = 0; mask < (1 << 5); mask++) {
    int sum = 0;
    for (int i = 0; i < 5; i++)
        if (mask >> i & 1) sum += a[i];
    if (sum == 6) cout << "YES\n";
}

One loop. No vectors. No recursion. The mask is the subset.

---

Visual Walkthrough

Set $S=\{a_0,a_1,a_2,a_3\}$ with $n=4$. All 16 subsets and their bitmasks:

  mask  binary  subset
  ----  ------  ------
    0   0000    {}
    1   0001    {a0}
    2   0010    {a1}
    3   0011    {a0, a1}
    4   0100    {a2}
    5   0101    {a0, a2}
    6   0110    {a1, a2}
    7   0111    {a0, a1, a2}
    8   1000    {a3}
    9   1001    {a0, a3}
   10   1010    {a1, a3}
   11   1011    {a0, a1, a3}
   12   1100    {a2, a3}
   13   1101    {a0, a2, a3}
   14   1110    {a1, a2, a3}
   15   1111    {a0, a1, a2, a3}

Set operations become bitwise operations on masks $A$ and $B$:

  A = {a0, a2}       = 0101
  B = {a1, a2}       = 0110

  A | B  (union)     = 0111  = {a0, a1, a2}
  A & B  (intersect) = 0100  = {a2}
  A ^ B  (sym diff)  = 0011  = {a0, a1}
  A & ~B (difference)= 0001  = {a0}
  ~A & full (compl.) = 1010  = {a1, a3}

Subset enumeration via counting:

  mask : 0 -> 1 -> 2 -> 3 -> 4 -> ... -> 15
         |    |    |    |    |            |
         {}  {a0} {a1} {a0, {a2}  ...    full
                        a1}               set

Each increment of mask visits the next subset in binary counting order.

---

The Invariant

Bitmask mask represents the set $\{i:\text{bit }i\text{ of mask is }1\}$. Set operations—union, intersection, difference, symmetric difference—map exactly to bitwise OR, AND, AND-NOT, XOR.

This mapping is a bijection: every subset has exactly one mask, every mask has exactly one subset. It is preserved through all bitwise operations:

• $|A\cup B|$ = popcount(a | b)
• $|A\cap B|$ = popcount(a & b)
• $A\subseteq B$ iff (a & b) == a
• $A=B$ iff a == b

All in $O(1)$ with hardware instructions.

---

What the Code Won't Teach You

The invariant gives you the mechanics. What distinguishes a fluent contestant is the judgment on top.

The constraint is the signal, not the problem statement. Don't wait for the problem to mention "subset" or "bitmask." When you see $n\le 20$ and the problem involves selecting, including, or excluding elements, your first instinct should be bitmask enumeration. The constraint $n\le 20$ is practically a neon sign that reads "enumerate $2^n$ states."

  Reading the constraint
  +---------------------+
  | n <= 20             |-----> Bitmask enumeration
  +---------------------+
  | n <= 40             |-----> Meet in the middle
  +---------------------+
  | n <= 10^5           |-----> Greedy / DP / sorting
  +---------------------+

Bitmask DP is ordinary DP—the state just happens to be a set. The state dp[mask] answers: "what is the optimal answer when exactly the elements in mask have been used?" Transitioning to dp[mask | (1 << i)] means "now also include element $i$." Once you frame every bitmask DP as "which items have been processed," every problem in this family feels structurally identical.

  Bitmask DP transition
  +----------+    include item i    +-----------------+
  | dp[mask] |-------------------->| dp[mask|(1<<i)] |
  +----------+                     +-----------------+
       |              mask bits         |
       v                                v
   0 1 1 0 1   --set bit i-->     0 1 1 1 1
   ^       ^                      ^       ^
   |       +-- items 0,2,3 used   |       +-- items 0,2,3,4 used
   +-- item 4 not yet used        +-- item 4 now included

XOR basis is linear algebra over GF(2), not a "trick." Each integer is a vector over the field $\{0,1\}$ where addition is XOR. "Can we XOR some subset to get a target?" is asking whether the target lies in the span of that vector set. The basis construction is Gaussian elimination in disguise. Once you see it that way, the XOR basis stops being a memorized template and becomes a tool you can adapt to novel problems.

With those three ideas in hand, here is how to spot bitmask problems in the wild.

When to Reach for This

Trigger phrases in problem statements:

Trigger	Meaning
$n\le 20$ (sometimes $\le 25$)	Enumerate $2^n$ subsets
"subsets", "subsequences (order doesn't matter)"	Bitmask enumeration
"XOR of elements"	XOR properties / basis
"minimum/maximum over all subsets"	Bitmask DP
"partition into groups"	Submask enumeration
"bitwise AND / OR of all pairs"	Contribution per bit

If the problem says $n\le 20$, your first reflex should be bitmask.

The shift in thinking that unlocks bitmask problems is this: a bitmask is not a representation of a subset—it is the subset. The moment you stop reaching for a data structure and realize the integer itself is the set, every set operation collapses to a single CPU instruction. Think of it as a row of light switches on a wall: each switch is ON or OFF, and the entire row's state is captured by one number. The fingerprint to burn into memory: "subset enumeration" + $n\le 20$ → bitmask. A useful mnemonic: "Twenty bits? One int. Forty bits? Meet in the middle." The machinery behind this dates to Claude Shannon's 1937 thesis linking Boolean algebra to electrical circuits—the foundation of every digital computer.

---

C++ STL Reference

GCC Builtins

These compile to single CPU instructions on most architectures.

Builtin	Returns	Notes
__builtin_popcount(x)	Number of 1-bits in x	int version
__builtin_popcountll(x)	Same for long long	Always use for 64-bit
__builtin_clz(x)	Count leading zeros	UB if x == 0
__builtin_clzll(x)	Same for long long	UB if x == 0
__builtin_ctz(x)	Count trailing zeros	UB if x == 0
__builtin_ctzll(x)	Same for long long	UB if x == 0
__builtin_parity(x)	1 if odd number of 1-bits, 0 if even
__builtin_parityll(x)	Same for long long
__builtin_ffs(x)	Index of lowest set bit (1-indexed), 0 if x==0	Safe for x=0
__builtin_ffsll(x)	Same for long long

Useful derived expressions:

int highest_bit_pos = x ? 31 - __builtin_clz(x) : -1;   // 0-indexed
int lowest_bit_pos  = __builtin_ctz(x);                   // UB if x==0
int bit_length      = x ? 32 - __builtin_clz(x) : 0;     // num bits needed

C++20 <bit> Header

These are well-defined for zero (no UB) and work on unsigned types.

Function	Description	Equivalent
std::popcount(x)	Number of 1-bits	__builtin_popcount
std::countl_zero(x)	Leading zeros	__builtin_clz (but safe for 0)
std::countr_zero(x)	Trailing zeros	__builtin_ctz (but safe for 0)
std::countl_one(x)	Leading ones	--
std::countr_one(x)	Trailing ones	--
std::bit_width(x)	$\lfloor {\log }_{2}x\rfloor +1$ (0 for x=0)	32 - __builtin_clz(x)
std::has_single_bit(x)	True if power of 2	x && !(x & (x-1))
std::bit_ceil(x)	Smallest power of 2 $\ge x$	--
std::bit_floor(x)	Largest power of 2 $\le x$ (0 for x=0)	--
std::rotl(x, s)	Rotate bits left by s	--
std::rotr(x, s)	Rotate bits right by s	--

#include <bit>
unsigned x = 42;
int pc = std::popcount(x);           // 3
int lz = std::countl_zero(x);        // 26
int tz = std::countr_zero(x);        // 1
int bw = std::bit_width(x);          // 6
bool p2 = std::has_single_bit(x);    // false
unsigned c = std::bit_ceil(x);       // 64
unsigned f = std::bit_floor(x);      // 32

std::bitset<N>

A fixed-size bit array with size known at compile time. Stores bits packed into 64-bit words internally, so bulk operations run in $O(N/64)$.

Constructors:

bitset<8> a;                    // all zeros:  00000000
bitset<8> b(0b10110);           // from int:   00010110
bitset<8> c("11001100");        // from string: 11001100
bitset<8> d(string("XOXO"), 0, 4, 'X', 'O');  // custom chars

Element access:

b[2]              // reference to bit 2 (0-indexed from LSB)
b.test(2)         // same but with bounds checking (throws)

Modification:

b.set()           // set ALL bits to 1
b.set(3)          // set bit 3 to 1
b.set(3, false)   // set bit 3 to 0
b.reset()         // clear ALL bits
b.reset(3)        // clear bit 3
b.flip()          // toggle ALL bits
b.flip(3)         // toggle bit 3

Queries:

b.count()         // number of 1-bits  (popcount)
b.size()          // N (compile-time constant)
b.any()           // true if any bit is 1
b.none()          // true if all bits are 0
b.all()           // true if all bits are 1

Bitwise operators:

a &= b;   a |= b;   a ^= b;   // compound assignment
a <<= 3;  a >>= 3;             // shift
~a;                             // complement
a & b;    a | b;    a ^ b;     // binary operators
a == b;   a != b;              // comparison

Conversion:

b.to_string()     // "00010110"
b.to_ulong()      // unsigned long value
b.to_ullong()     // unsigned long long value (throws if > 64 bits set)

Why bitset matters for CP: When you AND/OR/XOR two bitsets of $N=5000$ bits, the compiler processes 64 bits at a time—roughly 78 operations instead of 5000, a ~64× constant-factor win. That transforms $O(N^3)$ Floyd-Warshall into $O(N^3/64)$, often the difference between TLE and AC.

---

With the intuition and STL tools in place, here is the working code.

Implementation

Fundamentals

Binary Number System

Every non-negative integer can be written in base 2:

$$n=b_k\cdot 2^k+b_{k-1}\cdot 2^{k-1}+\cdots +b_1\cdot 2^1+b_0\cdot 2^0$$

where each $b_i\in \{0,1\}$.

Examples of decimal-to-binary conversion:

  0  -> 0         5  -> 101       10 -> 1010
  1  -> 1         6  -> 110       15 -> 1111
  2  -> 10        7  -> 111       16 -> 10000
  3  -> 11        8  -> 1000      31 -> 11111
  4  -> 100       9  -> 1001      32 -> 100000

C++ integer literals can be written in binary with the 0b prefix:

int x = 0b1101;    // 13
int y = 0b11111;   // 31

Bitwise Operators—Truth Tables

There are six fundamental bitwise operators in C++:

AND (&)—both bits must be 1:

  a  b  a&b
  0  0   0
  0  1   0
  1  0   0
  1  1   1

OR (|)—at least one bit is 1:

  a  b  a|b
  0  0   0
  0  1   1
  1  0   1
  1  1   1

XOR (^)—exactly one bit is 1:

  a  b  a^b
  0  0   0
  0  1   1
  1  0   1
  1  1   0

NOT (~)—flip every bit:

  a  ~a
  0   1
  1   0

Left shift (<<)—shift bits left, fill with zeros:

  5 << 1  =  0101 << 1  =  1010  = 10     (multiply by 2)
  5 << 2  =  0101 << 2  = 10100  = 20     (multiply by 4)
  1 << i  =  a single 1-bit at position i

Right shift (>>)—shift bits right, discard the lowest bit:

  10 >> 1  =  1010 >> 1  =  0101  = 5     (divide by 2)
  10 >> 2  =  1010 >> 2  =  0010  = 2     (divide by 4)

Essential Bit Tricks

These are the bread-and-butter operations. Memorise them.

Check if bit $i$ is set:

bool is_set = (x >> i) & 1;

Explanation: shift $x$ right by $i$ positions so bit $i$ becomes bit 0, then AND with 1 to isolate it.

Set bit $i$ (turn ON):

x |= (1 << i);

Explanation: 1 << i has only bit $i$ set. OR-ing with $x$ forces that bit to 1 without affecting any others.

Clear bit $i$ (turn OFF):

x &= ~(1 << i);

Explanation: ~(1 << i) has all bits 1 except bit $i$. AND-ing preserves everything except bit $i$, which becomes 0.

Toggle bit $i$ (flip):

x ^= (1 << i);

Explanation: XOR with 1 flips the bit; XOR with 0 leaves it unchanged.

Isolate the lowest set bit:

int lowbit = x & (-x);

Explanation: in two's complement, $-x=\sim x+1$. The AND picks out only the rightmost 1-bit. Example: $x=12={1100}_2$, $-x={0100}_2$, $x\mathrm{\&}(-x)={0100}_2=4$.

  x & (-x)  isolate lowest set bit

  x          =  0 1 1 0 1 0 0 0
                          ^--------- lowest set bit
  step 1: ~x =  1 0 0 1 0 1 1 1     flip all bits
  step 2: +1 =  1 0 0 1 1 0 0 0     add 1 -- carry ripples
               -x ^^^^^^^^^^^^^^^^

  x      =  0 1 1 0 1 0 0 0
  -x     =  1 0 0 1 1 0 0 0
             +-+-+-+-+-+-+-+
  x & -x =  0 0 0 0 1 0 0 0   <-- only the lowest set bit
             +-+-+-+-+-+-+-+

Clear the lowest set bit:

x &= (x - 1);

Explanation: $x-1$ flips the lowest set bit and all bits below it. AND-ing with $x$ clears them. Example: $12={1100}_2$, $11={1011}_2$, $12\mathrm{\&}11={1000}_2=8$.

Check if $x$ is a power of 2:

bool is_pow2 = x > 0 && (x & (x - 1)) == 0;

Powers of 2 have exactly one bit set. Clearing the lowest (only) bit gives 0.

Create a mask with bits $0\dots n-1$ set:

int full_mask = (1 << n) - 1;       // CAREFUL: use 1LL if n >= 31

Example: $n=4$: $(1\ll 4)-1=16-1=15={1111}_2$.

Count set bits (popcount):

int cnt = __builtin_popcount(x);     // int
int cnt = __builtin_popcountll(x);   // long long

---

Bit Tricks for CP

Five idioms appear in nearly every bitmask problem. Know them cold.

Check if $n$ is a power of 2: n > 0 && (n & (n-1)) == 0

A power of 2 has exactly one set bit; n-1 flips it and everything below. The AND yields 0 only when there was a single bit to begin with. Where used: segment tree size rounding, binary lifting size checks, interactive problems ("is the answer a power of 2?").

Get the lowest set bit: n & (-n)

Two's complement makes $-n=\sim n+1$, so the AND isolates the rightmost 1-bit. Where used: the core operation of Fenwick trees (BIT)—both update and query advance by the lowest set bit.

Turn off the lowest set bit: n & (n-1)

Subtracting 1 flips the lowest set bit and all trailing zeros. AND-ing clears them. Where used: manual popcount loops, checking power-of-2, and iterating over set bits.

Check if the $i$-th bit is set: (n >> i) & 1

Shift right to bring bit $i$ to position 0, then mask with 1. Where used: virtually every bitmask problem—subset membership, bitmask DP transitions, contribution-per-bit analysis.

Iterate over all submasks of a mask: for(int s = m; s > 0; s = (s-1) & m)

Decrementing within the constrained bit-space of $m$ visits every subset. Total work across all masks $m$ is $O(3^n)$. Where used: SOS DP / subset-sum over supersets, bitmask DP transitions that split a set into two parts.

// Example: print all submasks of mask m (excluding empty set)
for (int s = m; s > 0; s = (s - 1) & m) {
    // Invariant: s is a non-empty subset of m
    cout << bitset<8>(s) << "\n";
}

---

Enumeration and XOR Properties

Subset Enumeration

All subsets of a universe of size $n$:

for (int mask = 0; mask < (1 << n); mask++) {
    // Invariant: mask iterates 0, 1, ..., 2^n - 1 (all subsets)
    // process subset represented by mask
}

Time: $O(2^n)$.

All submasks of a given mask $m$ (all subsets of the subset $m$):

for (int sub = m; sub > 0; sub = (sub - 1) & m) {
    // Invariant: sub is a non-empty submask of m; visits each submask exactly once
    // process sub
}
// don't forget sub = 0 (the empty set) if needed

This enumerates every mask $s$ such that $s\subseteq m$, i.e. $s\mathrm{\&}m=s$. Total iterations across all masks: $\sum _{m=0}^{2^n-1}{2}^{\text{popcount}(m)}=3^n$.

Iterate over set bits of $x$:

while (x) {
    // Invariant: x contains only the not-yet-visited set bits
    int bit = __builtin_ctz(x);   // index of lowest set bit
    // use bit
    x &= x - 1;                   // clear that bit
}

Time: $O(\text{popcount}(x))$.

Gosper's Hack—Enumerate All Masks of Exactly $k$ Bits

Given $n$ and $k$, enumerates all $n$-bit integers with exactly $k$ bits set, in increasing order.

int mask = (1 << k) - 1;           // smallest: 0...0 1...1 (k ones)
int limit = 1 << n;
while (mask < limit) {
    // Invariant: mask has exactly k bits set and is the smallest such value not yet visited
    // process mask  (it has exactly k bits set)

    // Gosper's hack: next combination
    int c = mask & (-mask);         // lowest set bit
    int r = mask + c;               // carry ripples through consecutive 1s
    mask = (((r ^ mask) >> 2) / c) | r;
}

Example for $n=5,k=3$: visits $00111,01011,01101,01110,10011,\dots ,11100$.

This produces all $(\genfrac{}{}{0ex}{}{n}{k})$ subsets of size $k$ in $O((\genfrac{}{}{0ex}{}{n}{k}))$.

XOR Properties

XOR has algebraic properties that are critical for many problems:

1. Self-inverse: $a\oplus a=0$
2. Identity: $a\oplus 0=a$
3. Commutativity: $a\oplus b=b\oplus a$
4. Associativity: $(a\oplus b)\oplus c=a\oplus (b\oplus c)$

Consequence 1—Prefix XOR: Let $P_i=a_0\oplus a_1\oplus \cdots \oplus a_{i-1}$. Then $a_l\oplus a_{l+1}\oplus \cdots \oplus a_{r-1}=P_r\oplus P_l$.

This is the XOR analogue of prefix sums and is used the same way.

  Prefix XOR -- query range XOR in O(1)

  array a :   3    1    4    1    5
  index   :   0    1    2    3    4

  P[0]=0  P[1]=3  P[2]=2  P[3]=6  P[4]=7  P[5]=2

  Query: XOR of a[1..3] = a[1] ^ a[2] ^ a[3]
                         = 1 ^ 4 ^ 1 = 4

  Via prefix:  P[4] ^ P[1] = 7 ^ 3 = 4   <-- same

  +---+---+---+---+---+---+
  |P0 |P1 |P2 |P3 |P4 |P5 |
  | 0 | 3 | 2 | 6 | 7 | 2 |
  +---+---+---+---+---+---+
       ^               ^
       |   range 1..3  |
       +--- P[1] ^ P[4] = 3 ^ 7 = 4

Consequence 2—Cancellation: If $a\oplus b=c$, then $a=b\oplus c$ and $b=a\oplus c$. Used to find missing/duplicate elements.

Consequence 3—Pairwise XOR: In a multiset, if every element appears twice except one, XOR-ing all elements gives the unique element (all pairs cancel).

---

XOR Basis, Bitset Optimization, and Gray Code

XOR Basis Brief

Quick reference: A linear basis (XOR basis) is a set of numbers where no non-empty subset XORs to 0. Build it by inserting numbers one at a time, reducing each by existing basis vectors via Gaussian elimination. If a number reduces to 0, it is redundant; otherwise it extends the basis.

Applications:

• Maximum XOR subset: greedily pick basis vectors from high bit to low.
• Count XOR-reachable values: $2^{\text{rank}}$ distinct values.
• Check if target is achievable: reduce target through the basis—reachable iff it reduces to 0.

// Compact XOR basis -- O(n log V) to build, O(log V) per query
long long basis[60] = {};
int rank = 0;
void insert(long long x) {
    for (int i = 59; i >= 0; i--) {          // Invariant: bits above i are already reduced
        if (!(x >> i & 1)) continue;
        if (!basis[i]) { basis[i] = x; rank++; return; }
        x ^= basis[i];
    }
}
long long max_xor() {
    long long res = 0;
    for (int i = 59; i >= 0; i--)             // Invariant: res is optimal for bits > i
        res = max(res, res ^ basis[i]);
    return res;
}

For the full explained version with can_represent(), see XOR basis detailed below.

XOR Basis (Linear Independence over GF(2))

Think of each number as a vector over $\mathrm{GF}(2)$ (the field with elements $\{0,1\}$ where addition is XOR). A basis is a minimal set of vectors such that every XOR-combination of the original numbers can be expressed as an XOR-combination of basis elements.

Building the basis (Gaussian elimination):

// Minimal contest template
struct XorBasis {
    long long b[60] = {};    // basis vectors, one per bit position
    int sz = 0;              // number of independent vectors

    bool insert(long long x) {
        for (int i = 59; i >= 0; i--) {
            if (!(x >> i & 1)) continue;
            if (!b[i]) { b[i] = x; sz++; return true; }
            x ^= b[i];
        }
        return false;    // x is linearly dependent
    }

    bool can_represent(long long x) {
        for (int i = 59; i >= 0; i--)
            if (x >> i & 1) x ^= b[i];
        return x == 0;
    }

    long long max_xor() {
        long long res = 0;
        for (int i = 59; i >= 0; i--)
            res = max(res, res ^ b[i]);
        return res;
    }
};

Explained version:

struct XorBasis {
    // b[i] stores the basis vector whose highest set bit is bit i.
    // If b[i] == 0, there is no basis vector with highest bit i.
    long long b[60] = {};
    int sz = 0;   // rank = number of independent vectors inserted

    // Try to insert x into the basis.
    // Returns true if x was linearly independent (basis grew).
    // Returns false if x was already representable (redundant).
    bool insert(long long x) {
        // Gaussian elimination: reduce x by existing basis vectors.
        for (int i = 59; i >= 0; i--) {
            if (!(x >> i & 1)) continue;   // bit i of x is 0, skip
            if (!b[i]) {
                // No basis vector with highest bit i yet.
                // x becomes the new basis vector for bit i.
                b[i] = x;
                sz++;
                return true;   // linearly independent!
            }
            // There is already a basis vector for bit i.
            // XOR it away (eliminate bit i from x).
            x ^= b[i];
        }
        // x has been reduced to 0 -- it was a linear combination
        // of existing basis vectors.
        return false;
    }

    // Check if x can be represented as XOR of some basis elements.
    bool can_represent(long long x) {
        for (int i = 59; i >= 0; i--)
            if (x >> i & 1) x ^= b[i];
        return x == 0;
    }

    // Maximum XOR achievable from any subset of basis elements.
    // Greedy: try to set each bit from high to low.
    long long max_xor() {
        long long res = 0;
        for (int i = 59; i >= 0; i--)
            res = max(res, res ^ b[i]);
        return res;
    }

    // Number of distinct XOR values representable = 2^sz.
    // (Each of the 2^sz subsets of the basis gives a unique XOR.)
};

Key facts:

• Basis size (rank) is at most 60 for long long values.
• Number of distinct XOR-representable values = $2^{\text{rank}}$.
• Insertion is $O(\log V)$ where $V$ is the max value.
• Building basis for $n$ numbers: $O(n\log V)$.
• Used in problems like "maximum XOR subset", "count subsets with XOR = k", "partition into groups with nonzero XOR".

Bitset Optimization

Many $O(N^2)$ or $O(N^3)$ algorithms have an inner loop that does simple AND/OR/XOR on boolean arrays. Replace bool[] with std::bitset<N> and the inner loop runs in $O(N/64)$ instead of $O(N)$.

Example 1—Transitive Closure (Floyd-Warshall Reachability):

Naive: $O(N^3)$. With bitsets: $O(N^3/64)$.

// can_reach[i] is a bitset where bit j = 1 means i can reach j.
bitset<MAXN> can_reach[MAXN];

// Initialise: can_reach[i][j] = 1 if direct edge i->j.
for (auto [u, v] : edges) can_reach[u][v] = 1;
for (int i = 0; i < n; i++) can_reach[i][i] = 1;

// Floyd-Warshall style
for (int k = 0; k < n; k++)           // Invariant: paths through vertices 0..k-1 are captured
    for (int i = 0; i < n; i++)
        if (can_reach[i][k])
            can_reach[i] |= can_reach[k];  // O(N/64) per operation

Example 2—Knapsack (0/1) with Bitset:

Standard DP: dp[j] = true if sum j is achievable. Each item: shift and OR.

bitset<MAXSUM + 1> dp;
dp[0] = 1;
for (int i = 0; i < n; i++)
    // Invariant: dp[j] == 1 iff sum j is achievable using items 0..i-1
    dp |= (dp << w[i]);        // O(MAXSUM / 64) per item
// Total: O(n * MAXSUM / 64)

This turns an $O(n\cdot S)$ DP into $O(n\cdot S/64)$—often the difference between TLE and AC when $S$ is up to ${10}^5$ or ${10}^6$.

Gray Code

A Gray code is a sequence of all $n$-bit integers where consecutive values differ in exactly one bit.

Formula: the $i$-th Gray code value is $i\oplus (i\gg 1)$.

for (int i = 0; i < (1 << n); i++) {
    int gray = i ^ (i >> 1);
    // consecutive gray values differ by exactly one bit
}

Inverse (Gray code back to binary):

int gray_to_binary(int g) {
    int b = 0;
    for (; g; g >>= 1) b ^= g;
    return b;
}

Applications: hardware encoding (minimize switching), Karnaugh maps, generating subsets where you add/remove one element at a time (useful for incremental DP).

  Gray code -- consecutive values differ by 1 bit

  i   binary  gray   changed bit
  --  ------  -----  -----------
  0   0 0 0   0 0 0
                       v bit 0
  1   0 0 1   0 0 1
                       v bit 1
  2   0 1 0   0 1 1
                       v bit 0
  3   0 1 1   0 1 0
                       v bit 2
  4   1 0 0   1 1 0
                       v bit 0
  5   1 0 1   1 1 1
                       v bit 1
  6   1 1 0   1 0 1
                       v bit 0
  7   1 1 1   1 0 0

  Each step flips exactly one bit -- ideal for
  incremental add/remove of one element at a time

---

Operations Reference

Every bit operation covered in this topic, with raw-bit idioms, builtins, and bitset equivalents side by side.

Operation	Raw bits	__builtin_* / STL	bitset<N>	Complexity
Popcount	while(x) { cnt++; x &= x-1; }	__builtin_popcount(x)	bs.count()	$O(1)$ / $O(N/64)$
Lowest set bit	x & (-x)	--	--	$O(1)$
Highest set bit	1 << (31 - __builtin_clz(x))	std::bit_floor(x)	--	$O(1)$
Trailing zeros	--	__builtin_ctz(x) / std::countr_zero(x)	--	$O(1)$
Leading zeros	--	__builtin_clz(x) / std::countl_zero(x)	--	$O(1)$
Bit width	--	std::bit_width(x)	.size() (compile-time)	$O(1)$
Is power of 2	x > 0 && !(x & (x-1))	std::has_single_bit(x)	--	$O(1)$
Set bit $i$	x |= (1 << i)	--	bs.set(i)	$O(1)$
Clear bit $i$	x &= ~(1 << i)	--	bs.reset(i)	$O(1)$
Toggle bit $i$	x ^= (1 << i)	--	bs.flip(i)	$O(1)$
Check bit $i$	(x >> i) & 1	--	bs.test(i) / bs[i]	$O(1)$
Union	a | b	--	a | b	$O(1)$ / $O(N/64)$
Intersection	a & b	--	a & b	$O(1)$ / $O(N/64)$
Difference	a & ~b	--	a & ~b	$O(1)$ / $O(N/64)$
Sym. difference	a ^ b	--	a ^ b	$O(1)$ / $O(N/64)$
Subset check	(a & b) == a	--	(a & b) == a	$O(1)$ / $O(N/64)$
Full mask $0..n-1$	(1LL << n) - 1	--	bs.set()	$O(1)$ / $O(N/64)$

The bitset<N> column shows the $O(N/64)$ cost—the key advantage when $N$ is large (thousands or more).

---

Patterns

The operations and tricks above combine into a small set of recurring code shapes. Recognizing which one fits a problem is the core contest skill.

Bitmask Subset Enumeration

Enumerate all subsets of a universe of $n$ elements:

for (int mask = 0; mask < (1 << n); mask++) {
    // mask represents a subset
    for (int i = 0; i < n; i++) {
        if (mask >> i & 1) {
            // element i is in this subset
        }
    }
}

Use: brute-force over subsets when $n\le 20$.

XOR Tricks

Find the unique element when all others appear twice:

int result = 0;
for (int x : a) result ^= x;
// result is the element that appears once

Find two unique elements when all others appear twice:

int xor_all = 0;
for (int x : a) xor_all ^= x;         // xor_all = u ^ v
int diff_bit = xor_all & (-xor_all);   // some bit where u and v differ
int u = 0, v = 0;
for (int x : a) {
    if (x & diff_bit) u ^= x;
    else              v ^= x;
}
// u and v are the two unique elements

Bitmask DP

State is dp[mask] where mask encodes which elements have been used.

Example—Travelling Salesman (TSP):

// dp[mask][v] = min cost to visit the set of cities in mask,
//               ending at city v.
vector<vector<int>> dp(1 << n, vector<int>(n, INF));
dp[1][0] = 0;   // start at city 0

for (int mask = 1; mask < (1 << n); mask++) {
    for (int v = 0; v < n; v++) {
        if (dp[mask][v] == INF) continue;
        if (!(mask >> v & 1)) continue;
        for (int u = 0; u < n; u++) {
            if (mask >> u & 1) continue;   // already visited
            int nmask = mask | (1 << u);
            dp[nmask][u] = min(dp[nmask][u], dp[mask][v] + dist[v][u]);
        }
    }
}

Time: $O(2^n\cdot n^2)$. Works for $n\le 20$.

Bitset Optimization

Replace bool dp[N] with bitset<N> and get a $64\times$ constant-factor speedup.

0/1 Knapsack:

bitset<MAXW + 1> dp;
dp[0] = 1;
for (int i = 0; i < n; i++)
    dp |= (dp << w[i]);
// dp[W] tells if sum W is achievable

Reachability / transitive closure:

bitset<N> reach[N];   // reach[u] = set of vertices reachable from u
// initialise with direct edges, then:
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        if (reach[i][k])
            reach[i] |= reach[k];

Gosper's Hack

Enumerate all subsets of exactly $k$ elements from a universe of $n$:

int mask = (1 << k) - 1;
while (mask < (1 << n)) {
    // process mask (exactly k bits set)
    int c = mask & (-mask);
    int r = mask + c;
    mask = (((r ^ mask) >> 2) / c) | r;
}

Use: when you need all $(\genfrac{}{}{0ex}{}{n}{k})$ subsets of a fixed size.

XOR Basis

Insert numbers into a basis to find the maximum XOR, count representable values, or check if a target XOR is achievable.

XorBasis basis;
for (int x : a) basis.insert(x);

long long max_val = basis.max_xor();
long long count_distinct = 1LL << basis.sz;
bool can_make_target = basis.can_represent(target);

Use: "maximum XOR subset", "partition into nonzero XOR groups", "count XOR-distinct subsets".

Gray Code Generation

Visit all $2^n$ subsets such that consecutive subsets differ by exactly one element:

for (int i = 0; i < (1 << n); i++) {
    int gray = i ^ (i >> 1);
    // process subset represented by gray
}

Use: incremental computation—if processing a subset is expensive but adding/removing one element is cheap, Gray code order is optimal.

Submask Enumeration

Enumerate all subsets of a given mask $m$:

for (int sub = m; ; sub = (sub - 1) & m) {
    // process sub (sub is a subset of m)
    if (sub == 0) break;
}

Use: bitmask DP transitions where you split a set into two parts (iterate over all ways to partition).

Total complexity across all $m$ from $0$ to $2^n-1$: $O(3^n)$ (each element is in $m$ only, in $\text{sub}$ only, or in neither—3 states).

---

Before You Code Checklist

Run through these before writing bitmask code in a contest:

1. Is $n$ small enough? Bitmask enumeration needs $n\le 20$. Meet-in-the-middle pushes to $n\le 40$.
2. int or long long? If $n\ge 31$, every 1 << must be 1LL <<. If $n>62$, use bitset<N>.
3. What does the mask represent? Name it: visited cities, used items, selected elements. Naming prevents off-by-one confusion.
4. Do you need submasks? If transitions split a set into parts, total work is $O(3^n)$, not $O(4^n)$.
5. Parentheses on bitwise ops? Write (x & 1) == 0, never x & 1 == 0.

---

Contest Cheat Sheet

+------------------------------------------------------------------+
| BIT MANIPULATION CHEAT SHEET                                     |
|==================================================================|
| SINGLE-BIT OPERATIONS                                            |
| Check bit i:       (x >> i) & 1                                 |
| Set bit i:         x |= (1 << i)         // use 1LL if i >= 31  |
| Clear bit i:       x &= ~(1 << i)                               |
| Toggle bit i:      x ^= (1 << i)                                |
| Lowest set bit:    x & (-x)                                     |
| Clear lowest bit:  x & (x - 1)                                  |
| Is power of 2:     x > 0 && (x & (x - 1)) == 0                 |
| All bits 0..n-1:   (1LL << n) - 1                               |
|------------------------------------------------------------------|
| COUNTING                                                         |
| Popcount:          __builtin_popcount(x)  // popcountll for LL  |
| Trailing zeros:    __builtin_ctz(x)       // UB if x == 0       |
| Leading zeros:     __builtin_clz(x)       // UB if x == 0       |
| Highest set bit:   31 - __builtin_clz(x)                        |
| Bit width:         32 - __builtin_clz(x)  // or bit_width(x)    |
| Parity:            __builtin_parity(x)    // 1 if odd popcount  |
|------------------------------------------------------------------|
| SET OPERATIONS (on masks)                                        |
| Union:       a | b       Intersection: a & b                    |
| Difference:  a & ~b      Sym. diff:    a ^ b                    |
| Subset?:     (a & b) == a   (a is subset of b)                  |
| Size:        __builtin_popcount(a)                               |
|------------------------------------------------------------------|
| ENUMERATION                                                      |
| All subsets:        for (int m = 0; m < (1<<n); m++)             |
| Submasks of m:      for (int s = m; s; s = (s-1) & m)           |
|                     // remember to handle s = 0 separately       |
| Set bits of x:      while (x) { int b = ctz(x); x &= x-1; }   |
| Size-k subsets:     Gosper's hack (see Pattern 5)                |
|------------------------------------------------------------------|
| XOR IDENTITIES                                                   |
| a ^ a = 0           a ^ 0 = a                                   |
| a ^ b = b ^ a       (a ^ b) ^ c = a ^ (b ^ c)                  |
| Prefix XOR:  xor(l..r) = prefix[r+1] ^ prefix[l]               |
|------------------------------------------------------------------|
| BITSET (for large N)                                             |
| bitset<N> bs;                                                    |
| bs.count()   bs.any()   bs.none()   bs.all()                    |
| bs.set(i)    bs.reset(i)  bs.flip(i)  bs.test(i)                |
| bs &= other; bs |= other; bs ^= other;  // O(N/64) each        |
| Knapsack:    dp |= (dp << w[i]);         // O(S/64) per item    |
+------------------------------------------------------------------+

---

When NOT to Use This

The $n\le 20$ reflex is strong—which is exactly why knowing when to override it matters. Step back if:

• $n>25$ without meet-in-the-middle. $2^{25}$ is ~33 million—already tight. $2^{30}$ is a billion.
• The problem is about bit patterns in values, not subsets. Digit DP or greedy bit-by-bit construction may be the right tool. See essential techniques for alternatives.
• A greedy or sorting solution exists. Don't enumerate $2^{20}$ subsets when sorting + greedy runs in $O(n\log n)$. Check the data structure selection guide first.
• The "bits" are cosmetic. Some problems mention XOR but reduce to a per-bit contribution argument with no subset structure at all.

---

Gotchas & Debugging

1 << i Is UB When i >= 31

The literal 1 is int (32 bits). Shifting left by 31 or more bits is undefined behavior. Always use 1LL << i for bitmask operations where i can reach 31 or more. This is the single most common bitmask bug.

int bad  = 1 << 31;         // undefined behavior! signed overflow
long long good = 1LL << 31; // correct: 2147483648

// Subtle: even assigning to long long doesn't help
long long also_bad = 1 << 40;   // UB: 1 is int, shift overflows BEFORE assignment
long long also_good = 1LL << 40; // correct: cast BEFORE shifting

Whenever $n$ can be 31 or more, or you are using long long masks, always write 1LL.

Rule of thumb: if the mask variable is long long, every 1 << must be 1LL <<.

(1 << n) - 1 Overflows When $n=31$ or $n=32$

int full = (1 << 31) - 1;     // UB: 1 << 31 overflows int
int full = (1LL << 31) - 1;   // correct (result fits in int)
long long full = (1LL << 32) - 1; // correct for 32-bit masks

Signed vs. Unsigned Right Shift

Right shift on a negative signed integer is implementation-defined in C++. For bitmask work, keep values non-negative or use unsigned types.

int x = -1;
x >> 1;    // implementation-defined! might be 0x7FFFFFFF or 0xFFFFFFFF
unsigned u = -1;
u >> 1;    // well-defined: 0x7FFFFFFF (logical shift)

__builtin_clz(0) and __builtin_ctz(0) Are UB

Always guard with a zero check:

int highest = x ? 31 - __builtin_clz(x) : -1;
int lowest  = x ? __builtin_ctz(x) : -1;

Or use C++20 std::countl_zero / std::countr_zero which are safe for 0.

XOR Is Not Addition

$a\oplus b\ne a+b$ in general. XOR has no carries. Don't confuse XOR sums with arithmetic sums in DP transitions.

3 ^ 5 = 6   (011 ^ 101 = 110)
3 + 5 = 8   (different!)

Also: $a\oplus b\le a+b$ always, and $a\oplus b\equiv a+b(\mathrm{mod}2)$ always.

Submask Enumeration Misses the Empty Set

The common loop for (int sub = m; sub > 0; sub = (sub - 1) & m) stops before sub = 0. If you need the empty set, handle it separately:

for (int sub = m; ; sub = (sub - 1) & m) {
    process(sub);
    if (sub == 0) break;  // include empty set, then stop
}

Operator Precedence

Bitwise operators have lower precedence than comparison. x & 1 == 0 parses as x & (1 == 0) = x & 0 = 0. Always parenthesize: (x & 1) == 0. Same applies to | and ^. This causes silent wrong answers.

if (x & 1 == 0)     // WRONG: parsed as x & (1 == 0) = x & 0 = 0
if ((x & 1) == 0)   // CORRECT

if (a ^ b == c)      // WRONG: parsed as a ^ (b == c)
if ((a ^ b) == c)    // CORRECT

if (mask | flag != 0) // WRONG: parsed as mask | (flag != 0)
if ((mask | flag) != 0) // CORRECT

Always parenthesize bitwise expressions in conditions.

Debugging—Print Bits

// Method 1: bitset to_string
cerr << bitset<32>(x).to_string() << "\n";

// Method 2: print set bit indices
for (int tmp = x; tmp; tmp &= tmp - 1)
    cerr << __builtin_ctz(tmp) << " ";
cerr << "\n";

Mental Traps

~mask does not give the $n$-bit complement.

~mask flips all 64 bits, not just the $n$ you care about. To get the complement within $n$ bits, use (~mask) & ((1LL << n) - 1).

  n = 4   mask = 0101

  WRONG ---  ~mask
  +--+--+--+--+--+--+--+--+
  | 1| 1| 1| 1|  ...  | 1| 0| 1| 0|
  +--+--+--+--+--+--+--+--+
  <-- 60 garbage 1s -->|<-4 bits->|

  RIGHT ---  ~mask & ((1<<4)-1)
  +--+--+--+--+--+--+--+--+
  | 0| 0| 0| 0|  ...  | 1| 0| 1| 0|
  +--+--+--+--+--+--+--+--+
  <-- all zeros ------>|<-4 bits->|

Confusing XOR with addition.

XOR has no carry propagation. 3 ^ 5 = 6 but 3 + 5 = 8. Reaching for XOR in DP transitions when you actually need addition produces silent wrong answers.

  Addition vs XOR  --  bit 1 is the difference

      0 1 1       0 1 1
    + 1 0 1     ^ 1 0 1
    -------     -------
    1 0 0 0     0 1 1 0
    ^               ^
    |               +-- no carry -- XOR = 6
    +-- carry ripples -- ADD = 8

  Rule: XOR = addition without carries

Grabbing the familiar pattern instead of the correct one.

Bitmask problems have many patterns—subset enumeration, submask DP, XOR tricks, Gosper's hack. The trap is reaching for the one you practiced most rather than the one the problem needs. When $n\le 20$, don't immediately write submask enumeration if the problem is actually about XOR properties.

  Pattern selection -- match the problem, not your comfort

  +------------------+     +-------------------+
  |  n <= 20         |---->| Bitmask enum / DP |
  +------------------+     +-------------------+
  |  "XOR of subset" |---->| XOR basis         |
  +------------------+     +-------------------+
  |  "exactly k"     |---->| Gosper hack       |
  +------------------+     +-------------------+
  |  "split into 2"  |---->| Submask enum      |
  +------------------+     +-------------------+
        v
    WRONG: always pick the same one
    RIGHT: read the problem first

---

Self-Test

Cover these from memory before hitting the practice table:

• [ ] Write the code to check if bit $i$ is set in $x$, set it, clear it, and toggle it—from memory.
• [ ] Enumerate all submasks of a given mask $m$ using the (sub-1) & m idiom—explain why it works.
• [ ] State why 1 << 32 is undefined behavior for int and how to fix it.
• [ ] Explain why (x & 1 == 0) is always false and write the correct version.
• [ ] Given numbers $\{3,5,6\}$, build the XOR basis by hand and determine if target $=4$ is representable.
• [ ] Describe the difference between ~mask and the $n$-bit complement of mask. Write the correct expression.
• [ ] Convert the numbers 12, 15, and 23 to binary without a calculator.

---

Practice Problems

#	Problem	Source	Difficulty	Key Technique
1	Missing Number	CSES	800	XOR cancellation
2	Sum of All Subsets	CSES	1000	Bitmask enumeration
3	Apple Division	CSES	1200	Enumerate subsets, min diff
4	CF 550B -- Preparing Olympiad	CF	1400	Subset enumeration + constraints
5	CF 1516B -- AGAGA XOOORRO	CF	1500	XOR properties
6	CSES Hamiltonian Flights	CSES	1500	Bitmask DP
7	CSES Elevator Rides	CSES	1700	Bitmask DP, submask enum
8	CF 1721D -- Maximum AND	CF	1800	Greedy + bit contribution
9	CF 895C -- Square Subsets	CF	1900	XOR basis / linear algebra
10	CF 1101G -- (Zero XOR Subset)-less	CF	2100	XOR basis, rank

Work through these in order. Problems 1–3 drill basic enumeration and XOR; 4–7 introduce bitmask DP and enumeration patterns; 8–10 combine bit manipulation with greedy, linear algebra, and advanced DP.

---

Further Reading

• Bitmask DP—the natural continuation: DP where states are bitmasks.
• Binary Indexed Tree / Fenwick—a different use of bit structure (for prefix operations).
• cp-algorithms: Bit manipulation—broader coverage of tricks.
• Bit Twiddling Hacks—Sean Anderson's classic reference. Dozens of useful one-liners.
• Codeforces Blog: Bit Tricks for CP—community-curated tricks with problem links.
• Codeforces Blog: XOR basis—tutorial on linear basis over GF(2).
• C++20 <bit> header reference—official documentation for std::popcount, bit_width, etc.

---

What to Solve Next

Everything in this chapter—subset-as-integer, enumeration, XOR properties—feeds directly into two places:

• Bitset Optimization—when you need the $/64$ speedup. Bitsets extend the same "pack bits into words" idea to arrays of thousands of elements, turning $O(N^2)$ and $O(N^3)$ into $O(N^2/64)$ and $O(N^3/64)$.
• DP—Bitmask—memoize over subset states. The bitmask enumeration and submask tricks from this chapter become the state-space and transitions of DP; if you understood the Bitmask DP pattern above, you are ready.

Practice path: work through the problems table above (1→10 in order), then continue with the 1100–1400 ladder.