code C pour compter le nombre de bits « 1 » dans un unsigned char

Question

J'ai besoin du code C pour retourner le nombre de 1 dans un unsigned char en C. Il me faut une expliquer pourquoi cela fonctionne si ce n'est pas évident. Je l'ai trouvé beaucoup de code pour un nombre de 32 bits, mais pas grand-chose pour un unsigned char.

Answer 1

Le même code fonctionnera pour un unsigned char. Boucle sur tous les bits les tester. Voir cette .

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
}

Avoir un tableau qui connaît le nombre de bits de 0 à 15. Ajouter les résultats pour chaque demi-octet.

Answer 3

HACKMEM a cet algorithme en 3 opérations (traduit grossièrement à C):

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

(ULL est de forcer l'arithmétique 64 bits. Il est nécessaire, à peine ... ce calcul nécessite des nombres entiers 33 bits).

En fait, vous pouvez remplacer la deuxième constante avec 042104210021ULL, puisque vous ne comptant que 8 bits, mais il ne semble pas aussi bien symétrique.

Comment ça marche? Pensez-sage bit c, et rappelez-vous que (a + b) % c = (a % c + b % c) % c et (a | b) == a + b ssi (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 vous ne disposez pas de calcul disponibles, 64 bits, vous pouvez diviser c vers le haut dans des amuse-gueules et faire chaque moitié, en 9 opérations. Cela ne nécessite que 13 bits, donc en utilisant l'arithmétique ou 16- 32 bits fonctionnera.

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

Par exemple, 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

Voir la page hacks tripotant bit: http://graphics.stanford.edu /~seander/bithacks.html#CountBitsSetKernighan

il y a beaucoup de bonnes solutions pour cela.

En outre, cette fonction dans sa mise en œuvre plus simple est assez trivial. Vous devez prendre le temps d'apprendre comment faire.

Answer 5

Pour un entier aussi petit que unsigned char vous obtenez les meilleures performances en utilisant une petite table de recherche.

Je sais ce que les algorithmes de comptage de la population que vous mentionnez. Ils travaillent en faisant arithmétique des mots multiples inférieur à un nombre entier stockée dans un registre.

Cette technique est appelée SWAR ( http://en.wikipedia.org/wiki/SWAR).

Pour plus d'informations, je vous suggère de vérifier les pirates délectent site: www.hackersdelight.org. Il a un exemple de code et écrit un livre qui explique ces trucs en détail.

Answer 6

Comme il a déjà répondu, les méthodes standard de bits de comptage fonctionnent également sur les caractères non signés.

Exemple:

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

Answer 7

un unsigned char est un « numéro » de la même manière qu'un flotteur 32 bits ou entier est un « numéro », ce que le compilateur les juge pour représenter est ce qui change.

si vous l'image d'un char comme ses bits:

01010011 (8 bits);

vous pouvez compter les bits de réglage en procédant comme suit:

prendre la valeur, disons x, et prendre x% 2, le reste sera 1 ou 0. qui est, selon le boutisme du char, la gauche ou à droite bit le plus. accumuler le reste dans une variable distincte (ce sera le nombre résultant de bits de consigne).

puis >> (décalage à droite) 1 bit.

répétition jusqu'à ce que 8 bits ont été décalés.

le code c devrait être assez simple à mettre en œuvre de mon pseudo, mais fondamentalement

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

de base sur le poste de Ephemient, nous avons la version sans ramifiée 8 bits. Il est dans l'expression hexadécimale.

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

Appliquer deux fois, nous avons une version 16bits, qui a besoin de 9 opérations.

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

Ici, j'écris une variante version 16bits qui a besoin de registres 64bits et 11 opérations. Il ne semble pas mieux que le précédent, mais il utilise simplement l'opération 1 modulo.

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