Eu vi um código chamado "Conjunto de contagem de bits, do jeito de Brian Kernighan" . Estou intrigado sobre como funciona "bitwise and'ing" um inteiro com seu decremento para contar bits definidos, alguém pode explicar isso?
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}
Vamos percorrer o loop com um exemplo: vamos definir v = 42qual é 0010 1010em binário.
Primeira iteração : c=0, v=42 (0010 1010). Agora v-1é o 41que está 0010 1001em binário. Vamos calcular v & v-1:
0010 1010
& 0010 1001
.........
0010 1000
Agora v&v-1's valor é 0010 1000em binário ou 40 em decimal. Este valor é armazenado em v.
Segunda iteração : c=1, v=40 (0010 1000). Agora v-1é o 39que está 0010 0111em binário. Vamos calcular v & v-1:
0010 1000
& 0010 0111
.........
0010 0000
Agora v&v-1's valor é 0010 0000que é 32em decimal. Este valor é armazenado em v.
Terceira iteração : c=2, v=32 (0010 0000). Agora v-1é o 31que está 0001 1111em binário. Vamos calcular v & v-1:
0010 0000
& 0001 1111
.........
0000 0000
Agora v&v-1's valor é 0.
c=3, v=0. O loop termina . ccontém 3qual é o número de bits definido em 42.Você pode ver que a representação binária de v-1define o bit menos significativo ou LSB (ou seja, o bit mais à direita que é 1) de 1 a 0 e todos os bits à direita do LSB de 0 a 1.
Quando você faz um AND bit a bit entre ve v-1, os bits restantes do LSB são os mesmos ve, v-1portanto, o AND bit a bit os deixa inalterados. Todos os bits do LSB (incluindo o próprio LSB) são diferentes e, portanto, os bits resultantes serão 0.
Em nosso exemplo original, v=42 (0010 1010)o LSB é o segundo bit da direita. Você pode ver que v-1tem os mesmos bits, 42exceto os dois últimos: o 0 tornou-se 1 e o 1 tornou-se 0.
Da mesma forma, para v=40 (0010 1000)o LSB é o quarto bit da direita. Ao calcular, v-1 (0010 0111)você pode ver que os quatro bits esquerdos permanecem inalterados enquanto os quatro bits direitos se inverteram (zeros tornaram-se uns e os uns se tornaram zeros).
O efeito de v = v & v-1é, portanto, definir o bit menos significativo vpara 0 e deixar o resto inalterado. Quando todos os bits forem apagados dessa maneira, vserá 0 e todos os bits serão contados.
Este artigo é coletado da Internet.
Se houver alguma infração, entre em [email protected] Delete.
deixe-me dizer algumas palavras