bitcount em C, já implementaram, vale a pena?

[rockcavera]

35 minutos atrás, Omesmo disse:

GCC

para int use __builtin_popcount(n)

para int longo use __builtin_popcountl(n)

para long long int use __builtin_popcountll(n)

Quando se usa esses builtins no gcc, tem que passar -mpopcnt ao compilar para ele usar a instrução popcnt. Caso contrário ele usa um hack que não é de instrução única.

[Omesmo]

19 minutos atrás, rockcavera disse:

Quando se usa esses builtins no gcc, tem que passar -mpopcnt ao compilar para ele usar a instrução popcnt. Caso contrário ele usa um hack que não é de instrução única.

é eu estava lendo sobre isso, aliais o proprio gpt tinha escrito sobre isso ao passar o exemplo de função
mas mesmo que eu quisesse nao daria, já que esse all in lerdo nao tem , o meu antigo só tinha  sse4.2
no caso como eu prefiro o vba e usar o excel  eu faria primeiro uma função em dll que fizesse bitwise em 2 inteiros e retornasse a contagem de bit do resultado, e no proprio vba teria uma função para criar previamente a matriz de inteiros das combinações

[Omesmo]

tenho reparado que sempre que pedimos para o gpt algo de codigo sem especificar a linguagem ele faz em python

parece que é uma linguagem que já tem bastante coisa incorporada, TensorFlow, PyTorch, Scikit-learn, Keras e outros, para desenvolver algoritmos de aprendizado de máquina por exemplo , talvez seja uma escolha mais inteligente para se mexer em loteria

[Guest]

2 hours ago, Omesmo said:

tenho reparado que sempre que pedimos para o chatgpt algo de código sem especificar a linguagem ele faz em python

parece que é uma linguagem que já tem bastante coisa incorporada, TensorFlow, PyTorch, Scikit-learn, Keras e outros, para desenvolver algoritmos de aprendizado de máquina por exemplo , talvez seja uma escolha mais inteligente para se mexer em loteria

 

tem tudo a ver !

 

afinal, python é uma cobra, que está no jogo do bicho  

[sam88]

Eu costumo usar o std::bitset<100> no c++ para criar um vetor de bits e ai contar tudo que é igual 1.

É um pouco mais lento que setar bit a bit mas muito mais compreensível. 

 

Python é bom mas pra loteria é muito lento por ser uma linguagem interpretada.

C++ é mais rápido, C é mais ainda e Assembly é o suprassumo da velocidade mas muito mais complexo.

 

Se quer mais velocidade, tem que diminuir o processamento e aumentar o uso de memória.

Opração bit bit pode ser mais custosa em execução, dependendo da quanidade de bits, do que acessar uma posição num vetor e contar bits com um for ou while.

[Omesmo]

7 horas atrás, sam88 disse:

Opração bit bit pode ser mais custosa em execução, dependendo da quanidade de bits, do que acessar uma posição num vetor e contar bits com um for ou while.

cara estamos falando em converter as combinações em inteiros, fazer bitwise entre 2 inteiros e um popcount que seria uma instrução "unica" de processador

creio ser muito mais rápido do que contar bits em posição de vetor

claro que todo o processo tem que ser trabalhado, saber qual processador tem para escolher o melhor metodo, converter as combinações em inteiros, ...

 

Citar

Python é bom mas pra loteria é muito lento por ser uma linguagem interpretada.

python foi cogitado para o caso de se usar outros metodos de avaliação como o uso de redes neurais

é uma linguagem interpretada mas suas bibliotecas são executáveis em c e cpp, então ao usar as bibliotecas estaria usando um executável diretamente , ou melhor , seria como usar uma dll

[DixieJoe]

17 horas atrás, sam88 disse:

Eu costumo usar o std::bitset<100> no c++ para criar um vetor de bits e ai contar tudo que é igual 1.

É um pouco mais lento que setar bit a bit mas muito mais compreensível. 

 

Python é bom mas pra loteria é muito lento por ser uma linguagem interpretada.

C++ é mais rápido, C é mais ainda e Assembly é o suprassumo da velocidade mas muito mais complexo.

 

Se quer mais velocidade, tem que diminuir o processamento e aumentar o uso de memória.

Opração bit bit pode ser mais custosa em execução, dependendo da quanidade de bits, do que acessar uma posição num vetor e contar bits com um for ou while.

Sam88,

 

Já se aventurou com Assembly para loterias?

 

Vale a pena?

 

Na verdade, acredito que a única função que merece um tratamento rápido para loterias é a de CONTAR DEZENAS ENTRE 2 CONJUNTOS.

 

Quando tivermos alguma coisa que nos ajude a criar e utilizar uma função rápida (em Assembly) chamada por outros comandos de outra linguagem qualquer, estaremos no céu quanto à velocidade.

 

Quase tudo que é feito para loterias pode ser feito em qualquer linguagem. É rápido.

 

Mas muita coisa é feita nos estudos e programas para loterias que vão precisar dessa rotina de comparar (RAPIDAMENTE) 2 conjuntos. Ou dois jogos. Ou dois Integers de 32 bits, 64 bits, 128 bits (loterias como Quina ou Lotomania precisam de mais de mais de 64 bits para representar seus conjuntos em Integers).

 

Estou apanhando para conseguir chegar nessa função, rsrsrs

[sam88]

4 horas atrás, DixieJoe disse:

Sam88,

 

Já se aventurou com Assembly para loterias?

 

Vale a pena?

Já sim, mas é muito complexo de aprender e ai prefiro ficar pelo C++ rsrsrs

 

Uma coisa que quase não se vê comentar é o uso de threads (paralelismo), a linguagem pode ser fraca mas o processador tem mais de um núcleo e pode ser usado para processamento paralelo.

 

No momento eu tenho estudado threads pra cortar caminho no processamento. Com meu i3 usando 4 theads o tempo de processamento é diminuido quase que exponencialmente. Muito em breve meus programas vão voar em cada núcleo do processador.

[DixieJoe]

11 horas atrás, sam88 disse:

Já sim, mas é muito complexo de aprender e ai prefiro ficar pelo C++ rsrsrs

 

Uma coisa que quase não se vê comentar é o uso de threads (paralelismo), a linguagem pode ser fraca mas o processador tem mais de um núcleo e pode ser usado para processamento paralelo.

 

No momento eu tenho estudado threads pra cortar caminho no processamento. Com meu i3 usando 4 theads o tempo de processamento é diminuido quase que exponencialmente. Muito em breve meus programas vão voar em cada núcleo do processador.

Maravilha. Confesso que não tenho explorado o uso de threads nos meus programas.

 

O Delphi, que uso, oferece esse recurso. Vou precisar aprender a usar.

 

Você utiliza no C++? 

 

 

E, o que você chama de voar???  Me dê um exemplo de tempo que gasta para gerar e conferir todos os jogos da Lotofacil, usando o C++, por favor?

 

No Delphi, no meu notebook i5 antigo está levando 6.619 milisegundos para gerar todos os 3,2 milhões de jogos e conferir cada linha e mostrar um resumo dos acertos em tela.

Sei que poderia ser bem menos de 1 segundo se estivesse utilizando Assembly na função de CONTAR ACERTOS entre 2 linhas.

 

 

 

 

 

[DixieJoe]

Veja ai...

 

Essa velocidade é razoável? Para a Lotofacil, acho que até posso aceitar e conviver com essa velocidade.

Mas... para Megasena, aplicando filtros, etc. leva uma eternidade...

 

 

[sam88]

6 horas atrás, DixieJoe disse:

Maravilha. Confesso que não tenho explorado o uso de threads nos meus programas.

 

O Delphi, que uso, oferece esse recurso. Vou precisar aprender a usar.

 

Você utiliza no C++? 

 

 

E, o que você chama de voar???  Me dê um exemplo de tempo que gasta para gerar e conferir todos os jogos da Lotofacil, usando o C++, por favor?

 

No Delphi, no meu notebook i5 antigo está levando 6.619 milisegundos para gerar todos os 3,2 milhões de jogos e conferir cada linha e mostrar um resumo dos acertos em tela.

Sei que poderia ser bem menos de 1 segundo se estivesse utilizando Assembly na função de CONTAR ACERTOS entre 2 linhas.

 

Usando duas threads o que antes levaria tipo 10 segundos num programa normal, passa a levar 2 segundos. É uma grande otimização.

Eu ainda estou aprendendo aplicar nos meus programas, mas basicamente é dividir as iterações de for e while em funções que processam cada parte em paralelo.

 

Por exemplo:

se tu quer conferir uma única combinação contra todas as 3.2 milhões da LF, tu usando threads faz algo como:
thread_1 processa do 1 ao 1.6 milhões

thread_2 processa do 1.6 milhões até a 3.2 milhões.

Dai fica como se fossem dois programas num só, porém, cada thread executa em paralelo em núcleos do processador diferente, e por isso o grande aumento de velocidade de processamento.

 

Não uso Delphi, mas nesse teu processador ai, deve dá pra usar umas 4 ou 8 threads por programa.

[sam88]

6 horas atrás, DixieJoe disse:

 

Você utiliza no C++? 

E, o que você chama de voar???  Me dê um exemplo de tempo que gasta para gerar e conferir todos os jogos da Lotofacil, usando o C++, por favor?

 

No Delphi, no meu notebook i5 antigo está levando 6.619 milisegundos para gerar todos os 3,2 milhões de jogos e conferir cada linha e mostrar um resumo dos acertos em tela.

Sei que poderia ser bem menos de 1 segundo se estivesse utilizando Assembly na função de CONTAR ACERTOS entre 2 linhas.

 

SIm uso C++. Esses 6.619 milissegundos é para comparar uma única combinação contra as 3.2 milhões?

Se sim, calculei aqui e meu programa leva 0.320 segundos (320 milissegundos) pra fazer o mesmo.

[DixieJoe]

25 minutos atrás, sam88 disse:

SIm uso C++. Esses 6.619 milissegundos é para comparar uma única combinação contra as 3.2 milhões?

Se sim, calculei aqui e meu programa leva 0.320 segundos (320 milissegundos) pra fazer o mesmo.

Sim, compara a combinação do resultado com cada linha das 3,2 milhões. Só que vai gerando as 3,2 milhões e conferindo 4 vezes (sorteio desejado e 3 sorteios anteriores)

Maravilha! Com 2 threads apenas, é muito bom mesmo!

 

Claro, grava também a conferência em 4 arrays (1 para cada soteio em que conferiu). 

 

[rockcavera]

Em 11/03/2023 em 01:14, sam88 disse:

Se quer mais velocidade, tem que diminuir o processamento e aumentar o uso de memória.

Concordo. É o que acontece quando se divide o processamento em threads. Aumenta-se a quantidade de memória para dividir o processamento.

 

Em 11/03/2023 em 01:14, sam88 disse:

Opração bit bit pode ser mais custosa em execução, dependendo da quanidade de bits, do que acessar uma posição num vetor e contar bits com um for ou while.

Não concordo com isso. A operação bit a bit é a melhor forma de se verificar acertos para loterias, pelo menos para CPU. Com operações bits a bits, você pode comparar a quantidade de bits iguais entre dois INTEIROS com duas instruções. Ou seja, se o processador é 64 bits, até 64 bits você vai usar duas instruções para comparar.

 

Em 11/03/2023 em 01:14, sam88 disse:

C++ é mais rápido, C é mais ainda e Assembly é o suprassumo da velocidade mas muito mais complexo.

Depois de anos de otimizações que receberam os compiladores C, muito difícil ele não gerar o melhor código assembly possível. Mas há casos que é preciso se socorrer ao assembly para se obter o melhor mesmo.

 

Em 12/03/2023 em 17:10, sam88 disse:

Usando duas threads o que antes levaria tipo 10 segundos num programa normal, passa a levar 2 segundos. É uma grande otimização.

Bom, ou você não sabe o que diz ou foi muito infeliz no exemplo sem números reais. Na verdade essa diferença pode até acontecer se levarmos em consideração os processadores Intel atuais que possuem núcleos diferentes. Mas se tratando de núcleos idênticos, um programa que faz uma operação em 10 segundos com um thread, no mínimo - NO MÍNIMO MESMO! - vai fazer essa mesma operação com dois threads em 5 segundos. Mas na vida real nunca cai de fato pela metade, pois pode haver um gargalo de hardware em outra parte, como memória, ssd/hd, transferência de dados... que faz o tempo ficar acima da metade. Quanto mais thread se adiciona, mesmo tendo núcleos ou threads ociosas para realizar o trabalho, sempre pode haver um outro gargalo que impede a diminuição do tempo pelo fator de threads rodando.

 

Em 12/03/2023 em 10:32, DixieJoe disse:

 

No Delphi, no meu notebook i5 antigo está levando 6.619 milisegundos para gerar todos os 3,2 milhões de jogos e conferir cada linha e mostrar um resumo dos acertos em tela.

Em 12/03/2023 em 17:29, sam88 disse:

Se sim, calculei aqui e meu programa leva 0.320 segundos (320 milissegundos) pra fazer o mesmo.

Para comparar um único resultado com as 3.268.760 de combinações da lotofácil demora 5,944806 milissegundos.

 

Agora, para gerar as 3.268.760 de combinações da lotofácil e comparar um único resultado demora 39,307152 milissegundos. Ou seja, 33,362346 milissegundos para alocar memória para as 3.268.760 de combinações e gerá-las.

 

Para impedir otimizações em tempo de compilação, os parâmetros são passados durante a execução. Exemplo:

Digito: brincar.exe 25 15 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

25 = v

15 = k

14 = número de acertos que pretendo

"1 2 3 4 5 6 7 8 9 10 11 12 13 14 15" = combinação que será verificada contra as 3.268.760 de combinações da lotofácil.

Ele vai me retornar a quantidade de combinações que fizeram 14 pontos.

 

Isso impede otimizações de tempo de compilação e torna a comparação mais justa, pois posso mudar os parâmetros. Lembrando que o programa é single thread, ou seja, roda em um único thread.

 

Os números podem variar de acordo com o computador. Aqui é um Intel(R) Core(TM) i7-4810MQ CPU @ 2.80GHz com 16 gb de RAM 1600MHz DDR3, em dual channel.

 

Edit:

Estava deitado e lembrei que poderia fazer uma refatoração.

Agora, gerando cada combinação das 3.268.760 de combinações da lotofácil e logo em seguida comparando com a combinação que será verificada, sem armazenar as 3.268.760 de combinações, obtenho um tempo de 26,712895 milissegundos. Disso, pode se extrair que 6 milissegundos eram gastos, aproximadamente, para alocação da memória para caber as 3.268.760 de combinações. Dessa abordagem se extrair o melhor desempenho e o uso eficiente de memória, pois não armazena as combinações geradas que já foram testadas.

[DixieJoe]

rockavera,

 

Obrigado pelas elucidações e análises.

 

No Delphi, eu utilizo SETs para gerar as 3268260, conferir contra 5 sorteios (Atual e mais 4 anteriores) e gravar os conjuntos (pro meu caso, o gargalo mesmo parece ser a gravação...)

Então o meu tempo gasto é realmente de 6561 milisegundos (não apenas os seus 6 milisegundos!)

 

Acho fantástico o seu resultado!

 

Poderia nos ajudar a entender o que você faz de tão diferente? Seu programa é em C++? 

Compara integers com integers e utiliza popcount? 

 

Se puder compartilhar alguma luz a respeito, agradeceria muito. Afinal seus resultados em velocidade são maravilhosos.

 

E quanto a fazer o mesmo para outras loterias? Tipo Megasena (60 dezenas - integer com 64 bits?) E Quina/Lotomania com 80 e 100 dezenas?

Não tenho a menor idéia de como fazer isso com integers acima de 32 bits. Talvez até 64 eu consiga.

 

[rockcavera]

4 horas atrás, DixieJoe disse:

Poderia nos ajudar a entender o que você faz de tão diferente? Seu programa é em C++? 

Compara integers com integers e utiliza popcount? 

Escrevo meus programas em Nim.

 

O que eu faço é utilizar inteiros como combinações. Na mega-sena precisa de um inteiro que caiba 60 bits, então uso um inteiro de 64 bits. Nisso, os bits de 0 a 64 são marcados como 1 ou 0 de acordo com o número da combinação, que para mega-sena sempre serão 6 bits marcados como 1. A verificação é praticamente 2 instruções, um AND e um POPCNT. Para loterias você tem que entender o que todos os operadores bitwise fazem para extrair o melhor do programa. São 4 instruções: AND, OR, XOR e NOT. AND para verificar bits iguais, OR para concatenar combinações, XOR e NOT para inverter. Além disso é bom ter conhecimento de operações de deslocamento SHIFT (RIGHT e LEFT).

 

Além disso, é importante conhecer bem a linguagem e o compilador para extrair o máximo de otimizações.

 

4 horas atrás, DixieJoe disse:

Não tenho a menor idéia de como fazer isso com integers acima de 32 bits. Talvez até 64 eu consiga.

No Delphi se tem o tipo LONG, que é um inteiro de 64 bits.

 

4 horas atrás, DixieJoe disse:

E quanto a fazer o mesmo para outras loterias? Tipo Megasena (60 dezenas - integer com 64 bits?) E Quina/Lotomania com 80 e 100 dezenas?

Lotomania não vale a pena, né? São trilhões de combinações...

 

Para mega-sena:

103,738484 milissegundos - comparar uma combinação com todas as 50.063.860 combinações já geradas.
482,397266 milissegundos - gerar as 50.063.860 combinações armazenando-as e compará-las com uma única combinação.
197,240098 milissegundos - gerar as 50.063.860 combinações e a cada nova combinação, sem armazenar, já comparar com uma única combinação.

 

Para quina:

88,364074 milissegundos - comparar uma combinação com todas as 50.063.860 combinações já geradas.
603,023102 milissegundos - gerar as 24.040.016 combinações armazenando-as e compará-las com uma única combinação.
319,673796 milissegundos - gerar as 24.040.016 combinações e a cada nova combinação, sem armazenar, já comparar com uma única combinação.

 

Para a quina eu uso um inteiro de 128 bits (nint128) que eu mesmo desenvolvi a biblioteca para Nim.

[sam88]

10 horas atrás, rockcavera disse:

Não concordo com isso. A operação bit a bit é a melhor forma de se verificar acertos para loterias, pelo menos para CPU. Com operações bits a bits, você pode comparar a quantidade de bits iguais entre dois INTEIROS com duas instruções. Ou seja, se o processador é 64 bits, até 64 bits você vai usar duas instruções para comparar.

E como que tu conta os bits iguais?

Não me refiro a operação bit a bit AND. Ainda desconheço um jeito de saber quantos bits 1 são iguais sem que se use um for. Ali eu me referia a ter de usar um for pra ir movendo os bis e ir contando o que é 1 num inteiro a parte do resultado da operação bit a bit and.

[rockcavera]

25 minutos atrás, sam88 disse:

E como que tu conta os bits iguais?

Basta dar um COMB3 = COMB1 AND COMB2, depois contar quantos bits continuam ON, ou seja, marcados como 1 em COMB3.

 

O loop for você vai realizar várias operações para verificar apenas 1 bit por vez.

 

Antes de tudo, é preciso ter um conhecimento básico da lógica de programação. Operadores bit a bit (bitwise) precisam ser dominados para enxergar o seu uso.

[sam88]

1 hora atrás, rockcavera disse:

Basta dar um COMB3 = COMB1 AND COMB2, depois contar quantos bits continuam ON, ou seja, marcados como 1 em COMB3.

 

O loop for você vai realizar várias operações para verificar apenas 1 bit por vez.

 

Antes de tudo, é preciso ter um conhecimento básico da lógica de programação. Operadores bit a bit (bitwise) precisam ser dominados para enxergar o seu uso.

Justamente o que eu faço. Mas pensando melhor, adicionei uma lookup table e ai, excluindo o carregamento em memória, agora meu programa compara uma combinação de 15 contra as 3.2M em apenas 28 ms, mais de dez vezes menos que antes. Com uma lookup table, não preciso ficar contando todos os bits, basta pular de 8 em 8 bits e tá tudo contado.

 

Valeu a ideia.

[Omesmo]

3 horas atrás, sam88 disse:

Com uma lookup table, não preciso ficar contando todos os bits, basta pular de 8 em 8 bits e tá tudo contado.

oq se fala é sobre contabem de bit com instruções de processador, nao precisa de tabelas nem contar um a um,

é uma unica instrução que já entrega a quantidade de bits do inteiro POPCNT
 

#include <immintrin.h>

int main() {
    unsigned int value = 0xA5A5A5A5;
    int num_bits = _mm_popcnt_u32(value);
    printf("O valor 0x%X possui %d bits definidos.\n", value, num_bits);
    return 0;
}

esse é c e usa isntrução do sse4.2

A função "popcnt_u32" mencionada faz parte da biblioteca "immintrin.h" e usa instruções SIMD para contar o número de bits definidos em um valor de 32 bits. Essa função é mais rápida do que outras abordagens de contagem de bits disponíveis em C++, especialmente para grandes conjuntos de dados.

esse é para cpp, mas acho que faz verificação do tipo de processador

#include <bitset>
#include <iostream>

int main() {
    unsigned int value = 0xA5A5A5A5;
    int num_bits = std::popcount(value);
    std::cout << "O valor 0x" << std::hex << value << " possui " << num_bits << " bits definidos.\n";
    return 0;
}

 

[sam88]

@Omesmo

Vou testar aqui.

[rockcavera]

3 horas atrás, sam88 disse:

Com uma lookup table, não preciso ficar contando todos os bits, basta pular de 8 em 8 bits e tá tudo contado.

Aqui eu trouxe vários métodos e uma comparação deles.

[sam88]

@Omesmo

Testei aqui com std::popcount (e seu equivalente __builtin_popcount) e não teve diferença significativa com a lookup table.

 

@rockcavera

Não sei se tu testou exatamente do mesmo jeito que fiz.

 

Mas deixa eu explicar pra tu testar ai se quiser:

-a lookup table que falo é apenas uma tabela de 256 valores (8 bits cada) u_char table[256] //variável global ou estática na função

-dai eu inicio ela com as quantidades de bits 1 em cada um dos 256 valores, ex: table[1] = 1 bit table[7] = 3 bits etc

-para contar eu pego a uint64_t combA & combB e salvo em uint64_t combC

-como combC é um tipo de 64 bits (uint64_t), eu uso um for assim:

for (; c; c = c >> 8 ) //desloco 8 bits a cada iteração até que não haja mais nenhum valor em c

-então, dentro do for eu só faço algo como: contador += table[c & 0xFF]

Dai é instantaneamente somado os bits 1 atuais que já estavam previamente configurado.

No máximo 8 iterações (se usar mais números), na lotofácil fica como apenas 4 iterações quando tem a dz 25

 

Tentei com uma table de 256*256 mas ficou muito lento. A mais rápida foi de 256.

Edited March 14, 2023 by sam88
Corrigir código anteriormente errado

[rockcavera]

23 minutos atrás, sam88 disse:

@Omesmo

Testei aqui com std::popcount (e seu equivalente __builtin_popcount) e não teve diferença significativa com a lookup table.

 

@rockcavera

Não sei se tu testou exatamente do mesmo jeito que fiz.

 

Mas deixa eu explicar pra tu testar ai se quiser:

-a lookup table que falo é apenas uma tabela de 256 valores (8 bits cada) u_char table[256] //variável global ou estática na função

-dai eu inicio ela com as quantidades de bits 1 em cada um dos 256 valores, ex: table[1] = 1 bit table[7] = 3 bits etc

-para contar eu pego a uint64_t combA & combB e salvo em uint64_t combC

-como combC é um tipo de 64 bits (uint64_t), eu uso um for assim:

for (; c; c = c >> 8 ) //desloco 8 bits a cada iteração até que não haja mais nenhum valor em c

-então, dentro do for eu só faço algo como: contador += table[c & 0xFF]

Dai é instantaneamente somado os bits 1 atuais que já estavam previamente configurado.

No máximo 8 iterações (se usar mais números), na lotofácil fica como apenas 4 iterações quando tem a dz 25

 

Tentei com uma table de 256*256 mas ficou muito lento. A mais rápida foi de 256.

Testei deste modo. Qual compilador C++ você usa? Se for clang ou gcc, passe -mpopcnt para o builtin usar popcnt instrução. O seu processador também precisa suportar tal instrução. Leia minha postagem que tem tudo sobre.

 

Os testes que fiz usam ticks de processador, injetando assembly no meio do código para ter menos ruído possível na medição. Se não me engano, eu também digo que quanto mais loops você der, mais próximos vão ser os resultados mesmo com métodos diferentes, devido ao fato do processador habilitar o cache.

 

Uma tabela de consulta de 256 é mais provável que seja carregada no cache mais rápido do processador em loops longos que uma tabela de 65535 (16bits).

[Omesmo]

16 minutos atrás, sam88 disse:

Testei aqui com std::popcount (e seu equivalente __builtin_popcount) e não teve diferença significativa com a lookup table.

se nao me engano se voce nao ativar a instrução SIMD o compilador vai usar oq tiver
tipo voce tem que liberar uso de mmx e sse com -mavx -msse4.2 -mpopcnt