La serie viene usando bits desde la parte 3 sin decirlo. El XOR de prefijos fue el patrón 15, el DP con máscara de bits fue el patrón 45, y los subconjuntos de la parte 15 salieron de un contador. Esta parte es todo lo demás, y las trampas propias de C#.
Todos los programas de abajo están completos, se ejecutaron en .NET 10, y su salida está pegada tal cual de la ejecución.
Patrón 76 — XOR para encontrar el valor que aparece una sola vez
Cada valor aparece dos veces menos uno. Encuéntralo, con memoria O(1).
Tres propiedades hacen el trabajo: x ^ x == 0, x ^ 0 == x, y el orden es irrelevante. Cualquier valor que aparece un número par de veces desaparece, esté donde esté en la entrada.
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.");Imprime:
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.Tres propiedades, todas necesarias: x ^ x == 0, x ^ 0 == x, y el orden es irrelevante. Así cada valor duplicado se cancela solo, sin importar dónde estén sus dos copias, y lo que sobrevive es el que nunca tuvo pareja.
La variante del número faltante también vale la pena. La respuesta habitual es n(n+1)/2 - sum, que está bien hasta que n es lo bastante grande como para que la suma se desborde — la trampa de la parte 10. XOR no tiene ese problema, porque nada crece nunca.
Costo: O(n) tiempo, O(1) espacio.
Úsalo cuando las cosas vienen en pares y una no — un elemento faltante, un único valor sin pareja, encontrar un duplicado.
Patrón 77 — Cuando dos valores aparecen una sola vez
El mismo planteamiento, con dos valores sin pareja en vez de uno. Hacer XOR de todo ahora da a ^ b en lugar de una respuesta, así que hace falta una idea más.
Los dos valores que aparecen una sola vez difieren en el bit elegido, así que caen garantizadamente en grupos distintos. Cada grupo se reduce entonces al problema de un solo valor sin pareja del patrón 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.");Imprime:
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.Un bit en 1 dentro de a ^ b es una posición donde los dos valores difieren. Elige cualquiera de ellos — el más bajo es el más fácil — y divide la entrada por ahí.
Todo valor duplicado tiene sus dos copias del mismo lado, porque ambas copias tienen bits idénticos, así que cada par se cancela dentro de su grupo. Los dos valores únicos difieren en ese bit, así que caen en lados opuestos. Cada grupo contiene ahora exactamente un valor sin pareja, que es otra vez el patrón 76.
both & -both aísla el bit en 1 más bajo. Por qué funciona es el patrón 80.
Costo: O(n) tiempo, O(1) espacio, dos pasadas.
Úsalo cuando exactamente dos cosas quedan sin pareja. La misma idea de dividir por un bit que difiere se extiende más allá, pero deja de ser la respuesta corta.
Patrón 78 — BitOperations, y contar bits
System.Numerics.BitOperations existe desde .NET Core 3.0 y casi ningún código C# lo toca. Cada método compila a una sola instrucción de CPU donde el hardware tiene una.
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");Imprime:
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 y RoundUpToPowerOf2 entre todos reemplazan un montón de manipulación de bits escrita a mano. Ojo: reciben tipos sin signo.
El DP para contar bits vale la pena por sí solo. bits[i] = bits[i >> 1] + (i & 1) dice: i >> 1 es i sin su último bit, y ese número es más chico, así que su respuesta ya está calculada. Una pasada por el arreglo, sin popcount en absoluto.
Y el truco de Brian Kernighan — x &= x - 1 borra el bit en 1 más bajo — hace que un bucle corra una vez por bit en 1 en lugar de una vez por posición de bit. En 1024 eso es una iteración en lugar de treinta y dos.
Úsalo cuando estés contando o localizando bits. Revisa BitOperations antes de escribir un bucle.
Patrón 79 — Enumerar submáscaras
Dado un conjunto de bits, visita cada subconjunto suyo — sin tocar ningún bit fuera del conjunto.
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.");Imprime:
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.Dos bucles que vale la pena memorizar.
for (int m = mask; m != 0; m &= m - 1) recorre los bits en 1, una iteración por cada uno, saltándose por completo las posiciones vacías.
for (int s = mask; ; s = (s - 1) & mask) recorre las submáscaras. Restar uno pide prestado hacia abajo a través de los ceros finales; el & mask devuelve solo los bits que pertenecen al conjunto. Va en orden descendente y toca cada submáscara exactamente una vez.
La forma del bucle es rara y deliberada. Cero es una submáscara válida y hay que emitirla, pero (0 - 1) & mask es mask otra vez — así que el bucle volvería a empezar para siempre. El if (s == 0) break; al final es lo que la emite y después detiene todo.
El resultado de costo es la razón por la que esto importa. Iterar cada submáscara de cada máscara es 3ⁿ, no 4ⁿ, porque cada elemento está en uno de tres estados: fuera de la máscara, en la máscara pero no en la submáscara, o en ambas. Eso es lo que hace tratable el DP de suma de subconjuntos sobre todas las particiones con n = 20.
Úsalo cuando un DP con máscara de bits tiene que considerar formas de dividir un conjunto — problemas de asignación, particionar en grupos, problemas de cobertura.
Patrón 80 — Dónde muerden las operaciones de bits de C
Cuatro trampas, todas propias de que C# tenga un int con signo.
Por esto funciona x & -x, y depende del complemento a dos. Aparece en el patrón 77 de arriba, y también es como un árbol de Fenwick recorre sus índices.
// 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");Imprime:
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 ownEl contador de desplazamiento se enmascara. Para int se toma módulo 32, así que 1 << 32 es 1 — no cero, no 4294967296. Una máscara de bits sobre más de 31 elementos tiene que usar long, y equivocarse no lanza nada y parece un valor cualquiera.
>> conserva el signo; >>> no. -8 >> 1 es -4, que suele ser lo que quieres aritméticamente y nunca lo que quieres para manipular bits. C# 11 agregó >>> para la versión sin signo.
Un bucle de popcount sobre un int negativo nunca termina. x >>= 1 sobre un número negativo sigue metiendo bits de signo, así que x nunca llega a cero. El programa de arriba necesita una guarda para demostrarlo sin riesgo. Convierte a uint primero.
-x es ~x + 1. El acarreo se propaga hacia arriba por los ceros finales y se detiene en el bit en 1 más bajo, que es la única posición donde x y -x aún coinciden. Esa es toda la razón por la que funciona x & -x, y también es como un árbol de Fenwick recorre sus índices.
Qué recordar
-
XOR cancela pares sin importar el orden. Una pasada, sin memoria, y sin aritmética que pueda desbordarse como sí puede una suma.
-
Un bit en 1 dentro de
a ^ bes un lugar donde difieren. Divide por ahí y dos valores sin pareja se vuelven dos problemas separados de un solo valor sin pareja. -
Revisa
BitOperationsantes de escribir un bucle de bits.PopCount,TrailingZeroCount,Log2,IsPow2— instrucciones únicas, y reciben tipos sin signo. -
bits[i] = bits[i >> 1] + (i & 1). Contar los bits de un rango entero no necesita popcount para nada. -
x &= x - 1borra el bit en 1 más bajo, así que un bucle corre una vez por bit en 1, no una vez por posición. -
(s - 1) & maskrecorre submáscaras, y elbreaktiene que ir al final para que el cero se emita antes de que el bucle vuelva a empezar. -
1 << 32es1. El contador de desplazamiento se enmascara a 5 bits parainty 6 paralong. Más de 31 banderas significalong. -
Convierte a
uintantes de desplazar a la derecha en un bucle, o un valor negativo mete bits de signo para siempre.
Ochenta patrones
Dieciséis partes. Las partes 1 a 10 son el material de concurso — arreglos, grafos, programación dinámica, y la entrada/salida de C# que decide si algo de eso termina a tiempo. Las partes 11 a 16 son el material de entrevista — listas enlazadas, árboles, intervalos, backtracking, y bits.
Las listas contra las que se verificaron nombran veintiséis patrones distintos entre todas. Los veintiséis están aquí, y otros cincuenta y cuatro más.
Nada de esto vale mucho como algo para memorizar. Lo que lo hace útil es reconocer la forma: minimizar el máximo significa búsqueda binaria sobre la respuesta, valores de 1 a n significa que el arreglo es su propia tabla hash, exactamente K significa contar “como máximo” dos veces y restar, ordenar por el final en vez de por el inicio cuando el algoritmo voraz trata de acomodar cosas.
Todos los programas de esta serie se ejecutaron en .NET 10 antes de publicarse, y cada salida de cada página es lo que realmente imprimieron.