The series has been using bits since part 3 without saying so. Prefix XOR was pattern 15, bitmask DP was pattern 45, and part 15’s subsets came out of a counter. This part is the rest of it, and the C#-specific traps.
Every program below is complete, was run on .NET 10, and its output is pasted from the run.
Pattern 76 — XOR to find the value that appears once
Every value appears twice except one. Find it, in O(1) memory.
Three properties do the work: x ^ x == 0, x ^ 0 == x, and order is irrelevant. Any value appearing an even number of times disappears, wherever it sits in the input.
int[] a = [4, 1, 2, 1, 2];
// XOR has three properties and all three are needed:
// x ^ x == 0 a pair cancels
// x ^ 0 == x zero is the identity
// order does not matter (commutative and associative)
int unique = 0;
foreach (int x in a)
{
int before = unique;
unique ^= x;
Console.WriteLine($"{before,3} ^ {x} = {unique,3}");
}
Console.WriteLine($"\nthe value appearing once: {unique}");
Console.WriteLine($"\nBecause order does not matter, this is the same as");
Console.WriteLine($"(1^1) ^ (2^2) ^ 4 = 0 ^ 0 ^ 4 = 4, whatever order they arrived in.");
// The same idea finds a missing number in 0..n without any arithmetic.
int[] present = [0, 1, 3];
int n = 3;
int missing = n;
for (int i = 0; i < n; i++) missing ^= i ^ present[i];
Console.WriteLine($"\nmissing from [{string.Join(",", present)}] out of 0..{n}: {missing}");
Console.WriteLine("No sum, so nothing can overflow — which the sum formula can.");It prints:
0 ^ 4 = 4
4 ^ 1 = 5
5 ^ 2 = 7
7 ^ 1 = 6
6 ^ 2 = 4
the value appearing once: 4
Because order does not matter, this is the same as
(1^1) ^ (2^2) ^ 4 = 0 ^ 0 ^ 4 = 4, whatever order they arrived in.
missing from [0,1,3] out of 0..3: 2
No sum, so nothing can overflow — which the sum formula can.Three properties, all needed: x ^ x == 0, x ^ 0 == x, and order is irrelevant. So every duplicated value cancels itself out no matter where its two copies sit, and what survives is the one that never had a partner.
The missing-number variant is worth having as well. The usual answer is n(n+1)/2 - sum, which is fine until n is large enough that the sum overflows — the trap from part 10. XOR has no such problem, because nothing ever grows.
Cost: O(n) time, O(1) space.
Reach for it when things pair up and one does not — a missing element, a single unmatched value, finding a duplicate.
Pattern 77 — When two values appear once
Same setup, two unmatched values instead of one. XOR-ing everything now gives a ^ b rather than an answer, so it needs one more idea.
The two values that appear once differ at the chosen bit, so they are guaranteed to land in different groups. Each group then reduces to the single-unique problem from pattern 76.
int[] a = [1, 2, 1, 3, 2, 5]; // 3 and 5 appear once, the rest twice
// XOR everything: the pairs cancel and what is left is a ^ b.
int both = 0;
foreach (int x in a) both ^= x;
Console.WriteLine($"xor of everything = {both} (= a ^ b, binary {Convert.ToString(both, 2)})");
// A set bit in a ^ b is a position where a and b DIFFER. Take the lowest one.
int bit = both & -both; // two's complement: isolates the lowest set bit
Console.WriteLine($"lowest set bit = {bit} (binary {Convert.ToString(bit, 2)})");
Console.WriteLine($" because -x is ~x + 1, so x & -x keeps exactly that bit");
// Split into two groups by that bit. The two uniques cannot land together.
int groupOn = 0, groupOff = 0;
foreach (int x in a)
{
if ((x & bit) != 0) groupOn ^= x; else groupOff ^= x;
}
Console.WriteLine($"\ngroup with the bit set -> xor = {groupOn}");
Console.WriteLine($"group with it clear -> xor = {groupOff}");
Console.WriteLine($"\nthe two values appearing once: {Math.Min(groupOn, groupOff)} and {Math.Max(groupOn, groupOff)}");
Console.WriteLine($"\nEvery duplicate pair has the same bit, so both copies land in the same");
Console.WriteLine($"group and cancel. The two uniques differ at that bit, so they separate.");It prints:
xor of everything = 6 (= a ^ b, binary 110)
lowest set bit = 2 (binary 10)
because -x is ~x + 1, so x & -x keeps exactly that bit
group with the bit set -> xor = 3
group with it clear -> xor = 5
the two values appearing once: 3 and 5
Every duplicate pair has the same bit, so both copies land in the same
group and cancel. The two uniques differ at that bit, so they separate.A set bit in a ^ b is a position where the two values differ. Pick any one of them — the lowest is easiest — and split the input on it.
Every duplicated value has both copies on the same side, since both copies have identical bits, so each pair cancels within its group. The two unique values differ at that bit, so they land on opposite sides. Each group now contains exactly one unmatched value, which is pattern 76 again.
both & -both isolates the lowest set bit. Why that works is pattern 80.
Cost: O(n) time, O(1) space, two passes.
Reach for it when exactly two things are unmatched. The same split-on-a-differing-bit idea extends further, but it stops being the short answer.
Pattern 78 — BitOperations, and counting bits
System.Numerics.BitOperations has existed since .NET Core 3.0 and most C# code never touches it. Each method compiles to a single CPU instruction where the hardware has one.
using System.Numerics;
// System.Numerics.BitOperations maps to a single CPU instruction where one
// exists. Hand-rolled loops are strictly worse and much longer.
foreach (uint x in new uint[] { 0, 1, 7, 8, 255, 1024 })
Console.WriteLine($"{x,5} popcount {BitOperations.PopCount(x),2} " +
$"leadingZeros {BitOperations.LeadingZeroCount(x),2} " +
$"trailingZeros {BitOperations.TrailingZeroCount(x),2} " +
$"isPow2 {BitOperations.IsPow2(x),-5} log2 {(x == 0 ? "-" : BitOperations.Log2(x).ToString())}");
Console.WriteLine();
Console.WriteLine($"RoundUpToPowerOf2(100) = {BitOperations.RoundUpToPowerOf2(100)}");
Console.WriteLine($"RoundUpToPowerOf2(128) = {BitOperations.RoundUpToPowerOf2(128)}");
// Counting bits for 0..n, without calling popcount at all.
// i >> 1 is i with the last bit dropped, and its answer is already known.
int n = 8;
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1);
Console.WriteLine($"\ncounting bits 0..{n} by DP: [{string.Join(", ", bits)}]");
Console.WriteLine($"cross-check with PopCount: [{string.Join(", ", Enumerable.Range(0, n + 1).Select(i => BitOperations.PopCount((uint)i)))}]");
// Brian Kernighan: x & (x - 1) clears the lowest set bit, so the loop runs
// once per SET bit rather than once per bit position.
static int CountSlow(uint x) { int c = 0; while (x != 0) { x &= x - 1; c++; } return c; }
Console.WriteLine($"\nKernighan on 1024 (one set bit): {CountSlow(1024)} iteration, not 32");It prints:
0 popcount 0 leadingZeros 32 trailingZeros 32 isPow2 False log2 -
1 popcount 1 leadingZeros 31 trailingZeros 0 isPow2 True log2 0
7 popcount 3 leadingZeros 29 trailingZeros 0 isPow2 False log2 2
8 popcount 1 leadingZeros 28 trailingZeros 3 isPow2 True log2 3
255 popcount 8 leadingZeros 24 trailingZeros 0 isPow2 False log2 7
1024 popcount 1 leadingZeros 21 trailingZeros 10 isPow2 True log2 10
RoundUpToPowerOf2(100) = 128
RoundUpToPowerOf2(128) = 128
counting bits 0..8 by DP: [0, 1, 1, 2, 1, 2, 2, 3, 1]
cross-check with PopCount: [0, 1, 1, 2, 1, 2, 2, 3, 1]
Kernighan on 1024 (one set bit): 1 iteration, not 32PopCount, LeadingZeroCount, TrailingZeroCount, Log2, IsPow2 and RoundUpToPowerOf2 between them replace a great deal of hand-written bit fiddling. Note that they take unsigned types.
The counting-bits DP is worth seeing on its own. bits[i] = bits[i >> 1] + (i & 1) says: i >> 1 is i with its last bit removed, and that number is smaller, so its answer is already computed. One array pass, no popcount at all.
And Brian Kernighan’s trick — x &= x - 1 clears the lowest set bit — makes a loop run once per set bit rather than once per bit position. On 1024 that is one iteration instead of thirty-two.
Reach for it when you are counting or locating bits. Check BitOperations before writing a loop.
Pattern 79 — Enumerating submasks
Given a set of bits, visit every subset of it — without touching any bit outside the set.
using System.Numerics;
int mask = 0b1011; // elements 0, 1 and 3 are in the set
Console.WriteLine($"mask = {Convert.ToString(mask, 2).PadLeft(4, '0')}\n");
// Walk only the SET bits, not all 32 positions.
Console.WriteLine("set bits:");
for (int m = mask; m != 0; m &= m - 1)
{
int low = m & -m; // lowest set bit
Console.WriteLine($" bit {BitOperations.Log2((uint)low)} ({Convert.ToString(low, 2).PadLeft(4, '0')})");
}
// Every SUBSET of the set bits, without touching any bit outside the mask.
Console.WriteLine("\nevery submask:");
int count = 0;
for (int s = mask; ; s = (s - 1) & mask)
{
Console.WriteLine($" {Convert.ToString(s, 2).PadLeft(4, '0')} " +
$"[{string.Join(",", Enumerable.Range(0, 4).Where(i => (s & (1 << i)) != 0))}]");
count++;
if (s == 0) break; // 0 must be emitted, then stop
}
Console.WriteLine($"\n{count} submasks, expected 2^{BitOperations.PopCount((uint)mask)} = {1 << BitOperations.PopCount((uint)mask)}");
Console.WriteLine();
Console.WriteLine("(s - 1) borrows through the low zero bits; & mask puts back only the");
Console.WriteLine("bits that belong to the set. It walks the submasks in descending order");
Console.WriteLine("and touches each exactly once.");
Console.WriteLine();
Console.WriteLine("Over ALL masks this is 3^n total work, not 4^n — each element is either");
Console.WriteLine("out of the mask, in the mask but not the submask, or in both.");It prints:
mask = 1011
set bits:
bit 0 (0001)
bit 1 (0010)
bit 3 (1000)
every submask:
1011 [0,1,3]
1010 [1,3]
1001 [0,3]
1000 [3]
0011 [0,1]
0010 [1]
0001 [0]
0000 []
8 submasks, expected 2^3 = 8
(s - 1) borrows through the low zero bits; & mask puts back only the
bits that belong to the set. It walks the submasks in descending order
and touches each exactly once.
Over ALL masks this is 3^n total work, not 4^n — each element is either
out of the mask, in the mask but not the submask, or in both.Two loops worth memorising.
for (int m = mask; m != 0; m &= m - 1) walks the set bits, one iteration each, skipping the empty positions entirely.
for (int s = mask; ; s = (s - 1) & mask) walks the submasks. Subtracting one borrows down through the trailing zeros; the & mask puts back only bits that belong to the set. It runs in descending order and hits each submask exactly once.
The loop shape is unusual and deliberate. Zero is a valid submask and must be emitted, but (0 - 1) & mask is mask again — so the loop would restart forever. The if (s == 0) break; at the bottom is what emits it and then stops.
The cost result is the reason this matters. Iterating every submask of every mask is 3ⁿ, not 4ⁿ, because each element is in one of three states: outside the mask, in the mask but not the submask, or in both. That is what makes subset-sum DP over all partitions tractable at n = 20.
Reach for it when a bitmask DP has to consider ways of splitting a set — assignment problems, partitioning into groups, covering problems.
Pattern 80 — Where C# bit operations bite
Four traps, all specific to C# having a signed int.
This is why x & -x works, and it depends on two’s complement. It appears in pattern 77 above, and it is also how a Fenwick tree walks its indices.
// 1. The shift COUNT is masked. For int it is taken modulo 32.
Console.WriteLine($"1 << 31 = {1 << 31}");
Console.WriteLine($"1 << 32 = {1 << 32} <- not 0, and not 4294967296: the count wrapped to 0");
Console.WriteLine($"1 << 33 = {1 << 33} <- same as 1 << 1");
Console.WriteLine($"1L << 32 = {1L << 32} <- long shifts are taken modulo 64");
Console.WriteLine();
Console.WriteLine("So a bitmask over more than 31 items MUST use long, and the failure is");
Console.WriteLine("silent — 1 << 32 is a perfectly ordinary 1.");
// 2. >> keeps the sign. >>> does not. (>>> is C# 11 and later.)
Console.WriteLine();
int neg = -8;
Console.WriteLine($"-8 >> 1 = {neg >> 1,12} arithmetic shift, sign extends");
Console.WriteLine($"-8 >>> 1 = {neg >>> 1,12} unsigned shift, zeros shifted in");
Console.WriteLine($"int.MinValue >> 31 = {int.MinValue >> 31,4} all sign bits");
Console.WriteLine($"int.MinValue >>> 31 = {int.MinValue >>> 31,3} just the top bit");
// 3. Which is why popcount loops need uint, or they never terminate.
Console.WriteLine();
static int Wrong(int x) { int c = 0; int guard = 0; while (x != 0 && guard++ < 40) { c += x & 1; x >>= 1; } return guard >= 40 ? -1 : c; }
static int Right(int x) { int c = 0; uint u = (uint)x; while (u != 0) { c += (int)(u & 1); u >>= 1; } return c; }
Console.WriteLine($"counting bits of -8 with int >>: {Wrong(-8)} (-1 means it never terminated)");
Console.WriteLine($"counting bits of -8 with uint >>: {Right(-8)}");
// 4. -x is ~x + 1, which is what makes x & -x work.
Console.WriteLine();
int v = 12; // 1100
Console.WriteLine($"v = {Convert.ToString(v, 2).PadLeft(8, '0')}");
Console.WriteLine($"~v = {Convert.ToString(~v & 0xFF, 2).PadLeft(8, '0')}");
Console.WriteLine($"-v = {Convert.ToString(-v & 0xFF, 2).PadLeft(8, '0')} (= ~v + 1)");
Console.WriteLine($"v & -v = {Convert.ToString(v & -v, 2).PadLeft(8, '0')} the lowest set bit, on its own");It prints:
1 << 31 = -2147483648
1 << 32 = 1 <- not 0, and not 4294967296: the count wrapped to 0
1 << 33 = 2 <- same as 1 << 1
1L << 32 = 4294967296 <- long shifts are taken modulo 64
So a bitmask over more than 31 items MUST use long, and the failure is
silent — 1 << 32 is a perfectly ordinary 1.
-8 >> 1 = -4 arithmetic shift, sign extends
-8 >>> 1 = 2147483644 unsigned shift, zeros shifted in
int.MinValue >> 31 = -1 all sign bits
int.MinValue >>> 31 = 1 just the top bit
counting bits of -8 with int >>: -1 (-1 means it never terminated)
counting bits of -8 with uint >>: 29
v = 00001100
~v = 11110011
-v = 11110100 (= ~v + 1)
v & -v = 00000100 the lowest set bit, on its ownThe shift count is masked. For int it is taken modulo 32, so 1 << 32 is 1 — not zero, not 4294967296. A bitmask over more than 31 items must use long, and getting it wrong throws nothing and looks like an ordinary value.
>> preserves the sign; >>> does not. -8 >> 1 is -4, which is usually what you want arithmetically and never what you want for bit twiddling. C# 11 added >>> for the unsigned version.
A popcount loop on a negative int never terminates. x >>= 1 on a negative number keeps shifting in sign bits, so x never reaches zero. The program above needs a guard to demonstrate it safely. Cast to uint first.
-x is ~x + 1. The carry propagates up through the trailing zeros and stops at the lowest set bit, which is the only position where x and -x still agree. That is the whole reason x & -x works, and it is also how a Fenwick tree walks its indices.
What to remember
-
XOR cancels pairs regardless of order. One pass, no memory, and no arithmetic that can overflow the way a sum can.
-
A set bit in
a ^ bis a place where they differ. Split on it and two unmatched values become two separate one-unmatched problems. -
Check
BitOperationsbefore writing a bit loop.PopCount,TrailingZeroCount,Log2,IsPow2— single instructions, and they take unsigned types. -
bits[i] = bits[i >> 1] + (i & 1). Counting bits for a whole range needs no popcount at all. -
x &= x - 1clears the lowest set bit, so a loop runs once per set bit, not once per position. -
(s - 1) & maskwalks submasks, and thebreakmust be at the bottom so zero is emitted before the loop restarts. -
1 << 32is1. The shift count is masked to 5 bits forintand 6 forlong. More than 31 flags meanslong. -
Cast to
uintbefore shifting right in a loop, or a negative value shifts in sign bits forever.
Eighty patterns
Sixteen parts. Parts 1 to 10 are the contest material — arrays, graphs, dynamic programming, and the C# I/O that decides whether any of it finishes in time. Parts 11 to 16 are the interview material — linked lists, trees, intervals, backtracking, and bits.
The lists these were checked against name twenty-six distinct patterns between them. All twenty-six are here, and so are fifty-four more.
None of it is worth much as something to memorise. What makes it useful is recognising the shape: minimise the maximum meaning binary search on the answer, values from 1 to n meaning the array is its own hash table, exactly K meaning count “at most” twice and subtract, sort by end rather than start when the greedy is about fitting things in.
Every program in this series was run on .NET 10 before it was published, and every output on every page is what it actually printed.