Exercício para pensar: Como contar o número de bits 1 em um inteiro de 32 bits?
10/04/2023
0
Cada um dos 32 bits pode ser setado como 0 ou 1
...
11111111 11111111 11111111 11111101 = -3
11111111 11111111 11111111 11111110 = -2
11111111 11111111 11111111 11111111 = -1
00000000 00000000 00000000 00000000 = 0
00000000 00000000 00000000 00000001 = 1
00000000 00000000 00000000 00000010 = 2
00000000 00000000 00000000 00000011 = 3
...
Como contar o número de bits 1 de um número qualquer, da forma mais eficiente possível?
Ex.: O número 1.234.567.890 (em decimal) é representado por: 01001001 10010110 00000010 11010010 em binário.
Ele possui 12 bits 1 e 20 bits 0
Arthur Heinrich
Post mais votado
12/04/2023
for($i=1;$i<=9;$i++){
echo "$i=>".decbin($i)."<br>";}
/* resultado
1=>1
2=>10
3=>11
4=>100
...
Isto não deu certo porque o número com múltiplos dígitos em decimal não é representado como a concatenação de bits de cada dígito.
Ex.: o número 12 (doze) não é a concatenação do 1 (1 em binário) com o 2 (10 em binário) formando 110, que corresponde ao 6.
12 em binário é representado por 8 + 4 ou 1100 em binário.
Mas a ideia de decompor o número em partes menores é uma boa saída.
É como a técnica de dividir para conquistar. Se consegimos quebrar um problema complexo em problemas menores e mais simples, pode surgir um algoritmo melhorado.
Arthur Heinrich
Mais Posts
11/04/2023
Arthur Heinrich
var i, n, v : Integer; begin v := 1234567890; n := 0; for i:=1 to 32 do begin if Odd(v) then Inc(n); v := v shr 1; end; writeln(n,' bits 1'); end;
Porém, como eu disse, este é o método da força bruta, que utiliza a função Odd(v) para testar o bit menos significativo, que retorna true caso seja 1 (número ímpar).
Em seguida executa um shr (shift right) de 1 posição nos bits, repetindo este procedimento 32 vezes, até que todos os bits tenham sido testados.
O mesmo podia ser feito utilizando o shl (shift left). Mas, neste caso, precisaríamos testar o bit mais significativo, que é 1 quando o número é negativo.
Porém, queremos uma abordagem mais eficiente.
E se, ao invés de somar bit a bit, pudéssemos somar múltiplos bits simultaneamente?
O número 1234567890 é representado pela sequência de bits: 01001001100101100000001011010010
Podemos imaginar esta sequência como um conjunto de 32 valores de 1 bit. O valor de cada um destes números corresponde à quantidade de bits 1: 0 -> zero bits 1; 1 -> um bit 1
Então, podemos dividir esta sequência de 32 números de 1 bit e agrupá-los em duas sequências de 16 números de 2 bits, uma contendo os bits ímpares e a outra com os bits pares.
Partimos da sequência original, agrupada a cada 2 bits. Queremos dividir estes bits entre duas variáveis A e B, de forma que A contenha o primeiro dos dos bits e B o segundo.
A = 01 00 10 01 10 01 01 10 00 00 00 10 11 01 00 10
Aplicando um AND binário ao valor de A para deixar apenas os valores dos bits pares
B = A and 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
Aplicando o mesmo procedimento em A, para que preserve apenas os valores dos bits impares, mas deslocado de uma posição à direita
A = (A shr 1) and 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
Ao final, teremos:
A = 00 00 01 00 01 00 00 01 00 00 00 01 01 00 00 01
B = 01 00 00 01 00 01 01 00 00 00 00 00 01 01 00 00
A = A + B
A = 01 00 01 01 01 01 01 01 00 00 00 01 10 01 00 01
Uma sequência de 16 números de 2 bits, cada qual com a quantidade de bits 1 no par de bits.
Agora, vamos agrupar esta sequência de 16 números de 2 bits e duas sequências de 8 números de 4 bits e somá-las
A = 0100 0101 0101 0101 0000 0001 1001 0001
B = A and 0011 0011 0011 0011 0011 0011 0011 0011
A = (A shr 2) and 0011 0011 0011 0011 0011 0011 0011 0011
A = 0001 0001 0001 0001 0000 0000 0010 0000
B = 0000 0001 0001 0001 0000 0001 0001 0001
A = A + B
A = 0001 0010 0010 0010 0000 0001 0011 0001
Temos agora, 8 números de 4 bits. Repetimos o procedimento para fazer 4 somas de 8 bits
A = 00010010 00100010 00000001 00110001
B = A and 00001111 00001111 00001111 00001111
A = (A shr 4) and 00001111 00001111 00001111 00001111
A = 00000001 00000010 00000000 00000011
B = 00000010 00000010 00000001 00000001
A = A + B
A = 00000011 00000100 00000001 00000100
Temos agora 4 números de 8 bits. Repetimos o procedimento para fazer 2 somas de 16 bits.
A = 0000001100000100 0000000100000100
B = A and 0000000011111111 0000000011111111
A = (A shr 8) and 0000000011111111 0000000011111111
A = 0000000000000011 0000000000000001
B = 0000000000000100 0000000000000100
A = A + B
A = 0000000000000111 0000000000000101
Temos 2 números de 16 bits e queremos fazer a última soma para obter o total com 32 bits.
A = 00000000000001110000000000000101
B = A and 00000000000000001111111111111111
A = (A shr 16) and 00000000000000001111111111111111
A = 00000000000000000000000000000111
B = 00000000000000000000000000000101
A = A + B
A = 00000000000000000000000000001100 = 12 bits 1
O código ficaria mais ou menos assim:
var v : Integer; begin v := 1234567890; v:= (v and $55555555) + ((v shr 1) and $55555555); v:= (v and $33333333) + ((v shr 2) and $33333333); v:= (v and $0F0F0F0F) + ((v shr 4) and $0F0F0F0F); v:= (v and $00FF00FF) + ((v shr 8) and $00FF00FF); v:= (v and $0000FFFF) + ((v shr 16) and $0000FFFF); writeln(v,' bits 1'); end;
Testando os dois métodos, obtive os seguintes tempos:
Metodo Pulsos Clock ---------------------------------------- ------------ 12 bits 1 Força Bruta 258155 12 bits 1 Somas Sucessivas 173871
A diferença não parece muito grande. Mas, como eu havia comentado em outra mensagem, escrever o resultado na tela consome muito recurso.
Então, vejamos os tempos sem escrever o resultado na tela.
Metodo Pulsos Clock ---------------------------------------- ------------ Força Bruta 87 Somas Sucessivas 29
Dá para ver que o resultado chega a ser quase 3 vezes melhor. Mas o mais importante, é a enorme diferença entre mostrar o valor na tela, ou não.
Hoje em dia, praticamente todos os computadores utilizam telas gráficas e, quando abrimos um terminal, embora pareça uma janela de texto simples, manipular o conteúdo da tela exige modificar milhares, senão, milhões de pixels.
11/04/2023
Frank Hosaka
<?php // método básico: contagem simples $dec=1234567890; $decbin=decbin($dec); $bits=strlen($decbin); $contagem=0; for($i=0;$i<$bits;$i++){ if($decbin[$i]){$contagem++;}} echo $contagem."</br>"; // resultado: 12 // método especulativo for($i=1;$i<=9;$i++){ echo "$i=>".decbin($i)."<br>";} /* resultado 1=>1 2=>10 3=>11 4=>100 5=>101 6=>110 7=>111 8=>1000 9=>1001 Somando cada bit de cada decimal dá 14. Mas se somar até a "segunda casa" aí dá 12. Prova dos 9. Se o número é 2204, então, pela tabela, dá 3 bits. Vamos ver: */ echo "2204 =>".decbin(2204); // resultado: 2204 =>100010011100, não deu certo. /* como a minha capacidade de pensar é menor que o de uma formiga, o jeito é apelar para o Google, e lá encontrei um código em C++, de Akanksha Rai, no endereço https://www.geeksforgeeks.org/count-set-bits-in-an-integer/, assim: Function to get no of set bits in binary representation of positive integer n unsigned int countSetBits(unsigned int n) { unsigned int count = 0; while (n) { count += n & 1; n >>= 1; } return count; } Program to test function countSetBits int main() { int i = 9; cout << countSetBits(i); return 0; } Como eu não manjo nada de C++, para mim o método mais eficiente de contar os bits é na unha. */
12/04/2023
Arthur Heinrich
<?php // método básico: contagem simples $dec=1234567890; $decbin=decbin($dec); $bits=strlen($decbin); $contagem=0; for($i=0;$i<$bits;$i++){ if($decbin[$i]){$contagem++;}} echo $contagem."</br>"; // resultado: 12 // método especulativo for($i=1;$i<=9;$i++){ echo "$i=>".decbin($i)."<br>";} /* resultado 1=>1 2=>10 3=>11 4=>100 5=>101 6=>110 7=>111 8=>1000 9=>1001 Somando cada bit de cada decimal dá 14. Mas se somar até a "segunda casa" aí dá 12. Prova dos 9. Se o número é 2204, então, pela tabela, dá 3 bits. Vamos ver: */ echo "2204 =>".decbin(2204); // resultado: 2204 =>100010011100, não deu certo. /* como a minha capacidade de pensar é menor que o de uma formiga, o jeito é apelar para o Google, e lá encontrei um código em C++, de Akanksha Rai, no endereço https://www.geeksforgeeks.org/count-set-bits-in-an-integer/, assim: Function to get no of set bits in binary representation of positive integer n unsigned int countSetBits(unsigned int n) { unsigned int count = 0; while (n) { count += n & 1; n >>= 1; } return count; } Program to test function countSetBits int main() { int i = 9; cout << countSetBits(i); return 0; } Como eu não manjo nada de C++, para mim o método mais eficiente de contar os bits é na unha. */
O código em C que voce encontrou tem uma otimização interessante.
Ao invés de testar os 32 bits, o algoritmo para a verificação quando o número se torna zero.
Isso retorna rápido para números positivos pequenos.
Por exemplo, se o número a ser testado é zero, ele nem entra no loop, já que todos os bits são zero.
É um bom algoritmo de uso geral, onde o esforço é variável e não determinístico.
12/04/2023
Arthur Heinrich
<?php $dec=1234567890; echo strlen(str_replace('0','',decbin($dec)));
Clique aqui para fazer login e interagir na Comunidade :)