Lançado · em melhoria
Algorithm
A manipulação de bits trata inteiros como dígitos binários e usa AND, OR, XOR e deslocamentos para lidar com conjuntos, flags e DP com bitmask.
Manipulação de bits é enxergar um inteiro como uma sequência de 0s e 1s e usar AND, OR, XOR, NOT e deslocamentos para ler, ligar, desligar ou inverter bits específicos. Os computadores guardam inteiros em binário e negativos em complemento de dois, então cada uma dessas operações costuma ser uma única instrução da CPU. Uma expressão curta como x & -x (o bit ligado mais baixo) ou x & (x - 1) (esse bit apagado) pode substituir um loop inteiro.
Isso importa porque um único inteiro pode representar um conjunto de cerca de 20 elementos, o que permite percorrer todos os subconjuntos e usar conjuntos como estados em programação dinâmica com bitmask. Entrevistas técnicas cobram com frequência enumeração de subconjuntos, propriedades do XOR e popcount, e em produção os bits aparecem em permissões de arquivos, feature flags, cálculo de sub-redes, tabelas hash e índices bitmap. As regras, porém, mudam conforme a linguagem: inteiros em Python não têm limite, JavaScript converte para 32 bits e oferece >>>, Java também tem >>> e em C++ o mais seguro é usar tipos sem sinal nas máscaras.
Comece convertendo números para binário e para complemento de dois à mão. Depois pratique as quatro operações sobre um bit (ligar, desligar, inverter e testar) e imprima todos os subconjuntos percorrendo uma máscara de 0 a 2^n - 1. Em seguida avance para a enumeração de submáscaras e para problemas de DP com bitmask, como atribuição de tarefas ou o problema do caixeiro-viajante, e por fim confira a largura dos inteiros e as regras de deslocamento das linguagens que você usa.
Um número negativo é obtido invertendo todos os bits e somando 1. O deslocamento à esquerda multiplica por 2, o à direita divide por 2, e as linguagens diferenciam deslocamento aritmético e lógico.
Com a máscara 1 << i, OR liga o bit i, AND NOT o desliga e XOR o inverte. x & -x isola o bit ligado mais baixo e x & (x - 1) o remove.
Os subconjuntos de n elementos correspondem um a um aos inteiros de 0 a 2^n - 1, e união, interseção e diferença custam uma única operação bit a bit.
Os bits ligados são contados repetindo x &= x - 1 ou com uma função nativa. Como a ^ a = 0, o XOR encontra o valor sem par e calcula distâncias de Hamming e códigos de Gray.
popcount conta os bits ligados apagando o mais baixo com x &= x - 1 até não sobrar nenhum. subsets percorre uma máscara de 0 a 2^n - 1 e escolhe os elementos cujo bit está ligado, gerando todos os subconjuntos. A última linha mostra 12 & -12 = 4 (o bit ligado mais baixo), 12 & 11 = 8 (esse bit apagado) e x ^ x = 0. Execute com python bit_manipulation.py.
bit_manipulation.py
def popcount(x: int) -> int:
count = 0
while x:
x &= x - 1 # clear the lowest set bit
count += 1
return count
def subsets(items):
n = len(items)
for mask in range(1 << n):
yield mask, [items[i] for i in range(n) if (mask >> i) & 1]
for mask, chosen in subsets(["a", "b", "c"]):
print(format(mask, "03b"), popcount(mask), chosen)
x = 12
print(x & -x, x & (x - 1), x ^ x) # 4 8 0
python bit_manipulation.pySeis capítulos que levam você da instalação aos conceitos essenciais de Manipulação de bits.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Manipulação de bits.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.