Manipulação de bits em C#: XOR, popcount e enumeração de subconjuntos

A série usa bits desde a parte 3 sem dizer isso. XOR de prefixos foi o padrão 15, DP com bitmask foi o padrão 45, e os subconjuntos da parte 15 saíram de um contador. Esta parte é o resto disso, e as armadilhas específicas de C#.

Todo programa abaixo é completo, foi rodado no .NET 10, e a saída está colada da execução.

Padrão 76 — XOR para achar o valor que aparece uma vez

Todo valor aparece duas vezes, menos um. Ache ele, com memória O(1).

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.");

Ele 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.

Três propriedades, todas necessárias: x ^ x == 0, x ^ 0 == x, e a ordem é irrelevante. Então todo valor duplicado se cancela, não importa onde as duas cópias estejam, e o que sobra é aquele que nunca teve par.

A variante do número faltando também vale a pena. A resposta usual é n(n+1)/2 - sum, que funciona até n ficar grande o bastante para a soma dar overflow — a armadilha da parte 10. O XOR não tem esse problema, porque nada nunca cresce.

Custo: tempo O(n), espaço O(1).

Use quando as coisas se emparelham e uma não — um elemento faltando, um único valor sem par, achar um duplicado.

Padrão 77 — Quando dois valores aparecem uma vez

Mesma situação, dois valores sem par em vez de um. Aplicar XOR em tudo agora dá a ^ b em vez de uma resposta, então falta mais uma ideia.

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.");

Ele 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.

Um bit ligado em a ^ b é uma posição onde os dois valores diferem. Escolha qualquer um deles — o mais baixo é o mais fácil — e divida a entrada por ele.

Todo valor duplicado tem as duas cópias do mesmo lado, já que as duas cópias têm bits idênticos, então cada par se cancela dentro do seu grupo. Os dois valores únicos diferem naquele bit, então caem em lados opostos. Cada grupo agora tem exatamente um valor sem par, que é o padrão 76 de novo.

both & -both isola o bit ligado mais baixo. Por que isso funciona é o padrão 80.

Custo: tempo O(n), espaço O(1), duas passadas.

Use quando exatamente duas coisas estão sem par. A mesma ideia de dividir por um bit que difere vai mais longe, mas deixa de ser a resposta curta.

Padrão 78 — BitOperations, e contar bits

System.Numerics.BitOperations existe desde o .NET Core 3.0 e quase nenhum código C# encosta nele. Cada método compila para uma única instrução de CPU onde o hardware tem uma.

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");

Ele 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 32

PopCount, LeadingZeroCount, TrailingZeroCount, Log2, IsPow2 e RoundUpToPowerOf2 juntos substituem um monte de manipulação de bits escrita à mão. Repare que eles recebem tipos sem sinal.

A DP de contagem de bits vale por si só. bits[i] = bits[i >> 1] + (i & 1) diz: i >> 1 é i com o último bit removido, e esse número é menor, então a resposta dele já foi calculada. Uma passada no array, nenhum popcount.

E o truque de Brian Kernighan — x &= x - 1 desliga o bit ligado mais baixo — faz o laço rodar uma vez por bit ligado em vez de uma vez por posição de bit. Em 1024 isso é uma iteração em vez de trinta e duas.

Use quando você estiver contando ou localizando bits. Confira BitOperations antes de escrever um laço.

Padrão 79 — Enumerando submasks

Dado um conjunto de bits, visite todo subconjunto dele — sem tocar em nenhum bit fora do 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.");

Ele 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.

Dois laços que valem a pena decorar.

for (int m = mask; m != 0; m &= m - 1) percorre os bits ligados, uma iteração cada, pulando as posições vazias por completo.

for (int s = mask; ; s = (s - 1) & mask) percorre as submasks. Subtrair um pega emprestado através dos zeros finais; o & mask devolve só os bits que pertencem ao conjunto. Roda em ordem decrescente e passa por cada submask exatamente uma vez.

O formato do laço é incomum e proposital. Zero é uma submask válida e precisa ser emitida, mas (0 - 1) & mask é mask de novo — então o laço reiniciaria para sempre. O if (s == 0) break; no final é o que emite o zero e depois para.

O resultado de custo é a razão de isso importar. Iterar toda submask de toda mask é 3ⁿ, não 4ⁿ, porque cada elemento está em um de três estados: fora da mask, na mask mas não na submask, ou nos dois. É isso que torna a DP de soma de subconjuntos sobre todas as partições viável em n = 20.

Use quando uma DP com bitmask precisa considerar formas de dividir um conjunto — problemas de atribuição, particionar em grupos, problemas de cobertura.

Padrão 80 — Onde as operações de bits em C# mordem

Quatro armadilhas, todas por causa do int com sinal do C#.

// 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");

Ele 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 own

A contagem do deslocamento é mascarada. Para int ela é tomada módulo 32, então 1 << 32 é 1 — não zero, não 4294967296. Um bitmask com mais de 31 itens precisa usar long, e errar isso não lança nada e parece um valor comum.

>> preserva o sinal; >>> não. -8 >> 1 é -4, que costuma ser o que você quer aritmeticamente e nunca o que você quer para mexer em bits. O C# 11 adicionou >>> para a versão sem sinal.

Um laço de popcount em um int negativo nunca termina. x >>= 1 em um número negativo fica entrando com bits de sinal, então x nunca chega a zero. O programa acima precisa de uma trava para demonstrar isso com segurança. Converta para uint primeiro.

-x é ~x + 1. O carry se propaga pelos zeros finais e para no bit ligado mais baixo, que é a única posição onde x e -x ainda concordam. Essa é a razão inteira de x & -x funcionar, e é também como uma árvore de Fenwick percorre seus índices.

O que lembrar

• XOR cancela pares independente da ordem. Uma passada, sem memória, e nenhuma aritmética que possa dar overflow do jeito que uma soma pode.

• Um bit ligado em a ^ b é um lugar onde eles diferem. Divida por ele e dois valores sem par viram dois problemas separados de um valor sem par.

• Confira BitOperations antes de escrever um laço de bits. PopCount, TrailingZeroCount, Log2, IsPow2 — instruções únicas, e recebem tipos sem sinal.

• bits[i] = bits[i >> 1] + (i & 1). Contar bits para um intervalo inteiro não precisa de popcount nenhum.

• x &= x - 1 desliga o bit ligado mais baixo, então um laço roda uma vez por bit ligado, não uma vez por posição.

• (s - 1) & mask percorre submasks, e o break precisa ficar no final para que o zero seja emitido antes de o laço reiniciar.

• 1 << 32 é 1. A contagem do deslocamento é mascarada para 5 bits em int e 6 em long. Mais de 31 flags significa long.

• Converta para uint antes de deslocar à direita em um laço, ou um valor negativo entra com bits de sinal para sempre.

Oitenta padrões

Dezesseis partes. As partes 1 a 10 são o material de maratona — arrays, grafos, programação dinâmica, e o I/O de C# que decide se qualquer coisa disso termina a tempo. As partes 11 a 16 são o material de entrevista — listas encadeadas, árvores, intervalos, backtracking, e bits.

As listas contra as quais isto foi conferido nomeiam vinte e seis padrões distintos entre elas. Todos os vinte e seis estão aqui, e mais cinquenta e quatro.

Nada disso vale muito como algo para decorar. O que torna isso útil é reconhecer o formato: minimizar o máximo significando busca binária na resposta, valores de 1 a n significando que o array é a própria hash table dele, exatamente K significando contar “no máximo” duas vezes e subtrair, ordenar pelo fim em vez de pelo início quando o guloso é sobre encaixar coisas.

Todo programa desta série foi rodado no .NET 10 antes de ser publicado, e toda saída em toda página é o que ele realmente imprimiu.