Bits como Conjuntos: Máscaras, popcount e Bitsets de Muitas Palavras

O Artigo 14 usou, na sparse table (tabela de respostas pré-calculadas para blocos de potência de 2), uma expressão que passou quase despercebida: 1 << k, o comprimento dos blocos de cada nível. Este artigo leva essa expressão a sério. Um deslocamento de bits não é só uma forma curta de escrever uma potência de $2$. Um inteiro sem sinal de $64$ bits é um conjunto de até $64$ elementos, e uma única instrução do processador aplica a mesma operação lógica aos $64$ elementos de uma vez.

O artigo percorre essa ideia em três escalas. Na primeira, uma máscara de bits (bitmask) guarda um conjunto pequeno em um único inteiro, e as funções da biblioteca <bit> respondem às perguntas mais comuns sobre ela. Na segunda, std::bit_cast e std::byteswap trabalham sobre os bytes de um valor, e não sobre um conjunto. Na terceira, um conjunto de milhares de elementos ocupa muitas palavras de máquina, e as operações de conjunto viram laços curtos sobre essas palavras. As medições no MSVC comparam cinco representações para a mesma interseção e mostram duas coisas que o código-fonte não mostra: o teste de processador que o std::popcount faz a cada chamada e o preço de um desvio que depende dos dados.

As medições foram feitas com o MSVC do Visual Studio 18.10.3, com /std:c++latest /O2, em um Intel Core i7-10750H. Cada tempo é a mediana de cinco execuções depois de uma de aquecimento, salvo onde o texto disser outra coisa. Os programas deste artigo, com as entradas e as saídas esperadas de cada caso de teste, estão em serie-blog/competitiva-15.

1. Uma máscara é um conjunto pequeno

Deslocar o valor binário $1$ por $k$ posições para a esquerda produz um número com apenas o bit $k$ ligado:

$$1\ll k=2^k.$$