código C para contar el número de bits '1' en un unsigned char

Question

Necesito el código C para devolver el número de 1 de en un unsigned char en C. Necesito una explicación de por qué funciona si no es obvio. He encontrado una gran cantidad de código para un número de 32 bits, pero no mucho para un unsigned char.

Answer 1

El mismo código funcionará para un unsigned char. Lazo sobre todos los bits de prueba ellos. Ver este .

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
}

Tener una matriz que sabe el número de bits de 0 a 15. Añadir los resultados para cada mordisco.

Answer 3

HACKMEM tiene este algoritmo en 3 operaciones (aproximadamente traducido a C):

bits = (c * 01001001001ULL & 042104210421ULL) % 017;

(ULL es forzar la aritmética de 64 bits. Se necesita, apenas ... este cálculo requiere números enteros de 33 bits.)

En realidad, puede reemplazar la segunda constante con 042104210021ULL, ya que sólo está contando 8 bits, pero no se ve tan bien simétrica.

¿Cómo funciona esto? Piense en c bit a bit, y recordar que (a + b) % c = (a % c + b % c) % c, y si y sólo si (a | b) == a + b (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

Si usted no tiene 64 bits disponibles aritmética, puede dividir c arriba en cuartetos y hacer cada mitad, teniendo 9 operaciones. Esto sólo requiere 13 bits, así que usar 16 o 32 bits aritmética 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 ejemplo, si 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

Vea la página hacks poco twiddling: http://graphics.stanford.edu /~seander/bithacks.html#CountBitsSetKernighan

hay muchas buenas soluciones para esto.

Además, esta función en su aplicación más simple es bastante trivial. Usted debe tomar el tiempo para aprender cómo hacer esto.

Answer 5

Para un entero tan pequeño como un unsigned char se obtiene mejor rendimiento con una pequeña tabla de consulta.

Sé lo algoritmos población recuento que estás mencionando. Ellos trabajan por hacer aritmética de varias palabras más pequeñas que un entero almacenado en un registro.

Esta técnica se llama SWAR ( http://en.wikipedia.org/wiki/SWAR).

Para obtener más información le sugiero que echa un vistazo a los piratas informáticos delicia página web: www.hackersdelight.org. Él tiene el código de ejemplo y ha escrito un libro que explica estos trucos en detalle.

Answer 6

Como ya se ha contestado, las formas estándar de bits contando también funcionan en caracteres sin signo.

Ejemplo:

    unsigned char value = 91;
int bitCount = 0;
while(value > 0)
{
    if ( value & 1 == 1 ) 
        bitCount++;
    value >>= 1;
}

Answer 7

un unsigned char es un "número" en la misma forma que un flotador de 32 bits o entero es un "número", lo que el compilador las considere para representar es lo que cambia.

Si usted representa un char como sus bits:

01010011 (8 bits);

puede contar los bits fijados de la siguiente manera:

tomar el valor, digamos x, y tomar x 2%, el resto será de 1 o 0. Es decir, según el orden de bits del carbón, la izquierda o la derecha poco más. acumular el resto en una variable independiente (esto será el número resultante de bits puestos).

A continuación, >> (desplazamiento a la derecha) de 1 bit.

repetir hasta 8 bits se han desplazado.

c del código debería ser bastante fácil de implementar de mi pseudocódigo, pero básicamente

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 en el post de Ephemient, tenemos la ninguna versión 8 bits ramificada. Es en la expresión hexadecimal.

typedef unsigned char       UINT8;
typedef unsigned short      UINT16;
typedef unsigned long long  UINT64;
int hammingWeight8( const UINT8& c)
{
    return ( c* 0x8040201ULL & 0x11111111)%0xF;
}

Aplicar dos veces, tenemos una versión de 16 bits, que necesita 9 operaciones.

int hammingWeight16( const UINT16& c)
{
    return ((c & 0xFF)* 0x8040201ULL & 0x11111111)%0xF + 
             ((c >> 8)* 0x8040201ULL & 0x11111111)%0xF;
}

Aquí escribo una versión de 16 bits variante que necesita 64bits registros y 11 operaciones. Parece no es mejor que el anterior, pero sólo utiliza la operación de módulo 1.

int hammingWeight16( const UINT16& c)
{
    UINT64  w;
    w= (((( c* 0x8000400020001ULL)>> 3) & 0x1111111111111111)+14)%0xF;
    return (c!=0)*(w+1+(c==0xFFFF)*15);
}