Exercício para pensar: Como contar o número de bits 1 em um inteiro de 32 bits?

Algoritmo

Performance

10/04/2023

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
Arthur Heinrich

Arthur Heinrich

Curtidas 0

Melhor post

Arthur Heinrich

Arthur Heinrich

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
...


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.
GOSTEI 1

Mais Respostas

Arthur Heinrich

Arthur Heinrich

10/04/2023

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.

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.
GOSTEI 0
Frank Hosaka

Frank Hosaka

10/04/2023

<?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. */
GOSTEI 0
Arthur Heinrich

Arthur Heinrich

10/04/2023

<?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.
GOSTEI 1
Arthur Heinrich

Arthur Heinrich

10/04/2023

Deixando de lado a performance, acho que daria para fazer algo como:

<?php
$dec=1234567890;
echo strlen(str_replace('0','',decbin($dec)));

GOSTEI 1
POSTAR