Código C para contar o número de bits '1' em um char não assinado

Question

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.

Answer 1

O mesmo código funcionará para um char não assinado. Loop sobre todos os bits testando -os. Ver isto.

Answer 2

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.

Answer 3

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

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

Answer 5

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.

Answer 6

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;
}

Answer 7

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;
    }
}

Answer 8

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);
}