Exercício para pensar: Como contar o número de bits 1 em um inteiro de 32 bits?
10/04/2023
0
Um inteiro de 32 bits é representado por uma sequência de 4 bytes.
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
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
Curtir tópico
+ 0
Responder
Post mais votado
12/04/2023
// método especulativo
for($i=1;$i<=9;$i++){
echo "$i=>".decbin($i)."<br>";}
/* resultado
1=>1
2=>10
3=>11
4=>100
...
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
Responder
Mais Posts
11/04/2023
Arthur Heinrich
Um dos métodos que podemos utilizar para contar os bits 1 de um número de 32 bits é utilizar a "força bruta" e testar todos os bits.
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:
Testando os dois métodos, obtive os seguintes tempos:
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.
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.
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.
Responder
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. */
Responder
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.
Responder
12/04/2023
Arthur Heinrich
Deixando de lado a performance, acho que daria para fazer algo como:
<?php
$dec=1234567890;
echo strlen(str_replace('0','',decbin($dec)));
Responder
Clique aqui para fazer login e interagir na Comunidade :)
