Código C para contar o número de bits '1' em um char não assinado
-
22-08-2019 - |
Pergunta
Preciso de código C para retornar o número de 1 em um char não assinado em C. Preciso de uma explicação sobre por que ele funciona se não for óbvio. Encontrei muito código para um número de 32 bits, mas não muito para um char não assinado.
Solução
O mesmo código funcionará para um char não assinado. Loop sobre todos os bits testando -os. Ver isto.
Outras dicas
const unsigned char oneBits[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
unsigned char CountOnes(unsigned char x)
{
unsigned char results;
results = oneBits[x&0x0f];
results += oneBits[x>>4];
return results
}
Tenha uma matriz que saiba o número de bits para 0 a 15. Adicione os resultados para cada mordidela.
Hackmem Tem esse algoritmo em 3 operações (traduzido aproximadamente para C):
bits = (c * 01001001001ULL & 042104210421ULL) % 017;
(ULL
é forçar a aritmética de 64 bits. É necessário, apenas apenas ... esse cálculo requer números inteiros de 33 bits.)
Na verdade, você pode substituir a segunda constante por 042104210021ULL
, já que você está contando apenas 8 bits, mas não parece tão bem simétrico.
Como é que isso funciona? Imagine c
em termos de um pouco, e lembre-se disso (a + b) % c = (a % c + b % c) % c
, e (a | b) == a + b
iff (a & b) == 0
.
(c * 01001001001ULL & 042104210421ULL) % 017
01 01001001001 01 1
02 02002002002 02000000000 1
04 04004004004 04000000 1
010 010010010010 010000 1
020 020020020020 020 1
040 040040040040 040000000000 1 # 040000000000 == 2 ** 32
0100 0100100100100 0100000000 1
0200 0200200200200 0200000 1
Se você não tem aritmética de 64 bits disponíveis, você pode dividir c
subir em petiscos e fazer cada metade, tomando 9 operações. Isso requer apenas 13 bits; portanto, o uso da aritmética de 16 ou 32 bits funcionará.
bits = ((c & 017) * 0421 & 0111) % 7 + ((c >> 4) * 0421 & 0111) % 7;
(c * 0421 & 01111) % 7
1 0421 01 1
2 01042 01000 1
4 02104 0100 1
8 04210 010 1
Por exemplo, se c == 105 == 0b11001001
,
c == 0100
| 040
| 010
| 01 == 0151
* 01001001001001ULL == 0100100100100
| 040040040040
| 010010010010
| 01001001001 == 0151151151151
& 0421042104210421ULL == 0100000000
| 04000000000
| 010000
| 01 == 04100010001
% 017 == 4
c & 017 == 8 | 1 == 011
011 * 0421 == 8 * 0421 | 1 * 0421 == 04210 | 0421 == 04631
04631 & 0111 == 04210 & 0111 | 0421 & 0111 == 010 | 01 == 011
011 % 7 == 2
c >> 4 == 4 | 2 == 06
06 * 0421 == 4 * 0421 | 2 * 0421 == 02104 | 01042 == 03146
03146 & 0111 == 02104 & 0111 | 01042 & 0111 == 0100 | 01000 == 01100
01100 % 7 == 2
2 + 2 == 4
Veja a página de hacks giratórios: http://graphics.stanford.edu/~seander/bithacks.html#countbitssetkernighan
Existem muitas boas soluções para isso.
Além disso, essa função em sua implementação mais simples é bastante trivial. Você deve reservar um tempo para aprender a fazer isso.
Para um número inteiro tão pequeno quanto um char não assinado, você obtém o melhor desempenho usando uma pequena mesa de pesquisa.
Eu sei que algoritmos de contagem populacional você está mencionando. Eles trabalham fazendo aritmética de várias palavras menores que um número inteiro armazenado em um registro.
Esta técnica é chamada SWAR (http://en.wikipedia.org/wiki/swar).
Para mais informações, sugiro que você confira o site Hackers Delight: www.hackersdelight.org. Ele tem código de exemplo e escreveu um livro que explica esses truques em detalhes.
Como já respondido, as formas padrão de contar os bits também funcionam em chars não assinados.
Exemplo:
unsigned char value = 91;
int bitCount = 0;
while(value > 0)
{
if ( value & 1 == 1 )
bitCount++;
value >>= 1;
}
Um char não assinado é um "número" da mesma maneira que um flutuador ou número inteiro de 32 bits é um "número", o que o compilador os considera representar é o que muda.
Se você imagina um char como seus bits:
01010011 (8 bits);
Você pode contar os bits definidos fazendo o seguinte:
Pegue o valor, digamos x e pegue x % 2, o restante será 1 ou 0. Ou seja, dependendo da endianidade do char, da esquerda ou da direita. acumule o restante em uma variável separada (este será o número resultante de bits definidos).
Então >> (mudança direita) 1 bit.
Repita até que 8 bits tenham sido deslocados.
O código C deve ser bem simples de implementar do meu pseudocódigo, mas basicamente
public static int CountSetBits(char c)
{
int x = 0;
int setBits = 0;
while (x < 7)
{
setBits = setBits + c % 2;
c = c >> 1;
x = x + 1;
}
}
Base na postagem da Efemient, temos a versão de 8 bits sem ramificação. Está na expressão hexadecimal.
typedef unsigned char UINT8;
typedef unsigned short UINT16;
typedef unsigned long long UINT64;
int hammingWeight8( const UINT8& c)
{
return ( c* 0x8040201ULL & 0x11111111)%0xF;
}
Aplique duas vezes, temos uma versão de 16bits, que precisa de 9 operações.
int hammingWeight16( const UINT16& c)
{
return ((c & 0xFF)* 0x8040201ULL & 0x11111111)%0xF +
((c >> 8)* 0x8040201ULL & 0x11111111)%0xF;
}
Aqui, escrevo uma versão variante de 16bits que precisa de 64 bits registradores e 11 operações. Parece não melhor que o anterior, mas apenas usa 1 operação de módulo.
int hammingWeight16( const UINT16& c)
{
UINT64 w;
w= (((( c* 0x8000400020001ULL)>> 3) & 0x1111111111111111)+14)%0xF;
return (c!=0)*(w+1+(c==0xFFFF)*15);
}