C Code, um die Anzahl der '1' Bits in einem nicht signierten Zeichen zu zählen

Question

Ich brauche C -Code, um die Anzahl der 1 in einem nicht signierten Zeichen in C zurückzugeben. Ich brauche eine Erklärung dafür, warum es funktioniert, wenn es nicht offensichtlich ist. Ich habe viel Code für eine 32-Bit-Nummer gefunden, aber nicht viel für einen nicht signierten Zeichen.

Answer 1

Der gleiche Code funktioniert für einen nicht signierten Zeichen. Schleifen Sie über alle Bits, die sie testen. Sehen Dies.

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
}

Haben Sie ein Array, das die Anzahl der Bits für 0 bis 15 kennt. Fügen Sie die Ergebnisse für jedes Knabbern hinzu.

Answer 3

Hackmem hat diesen Algorithmus in 3 Operationen (grob übersetzt auf C):

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

(ULL ist 64-Bit-Arithmetik zu erzwingen. Es ist kaum erforderlich ... diese Berechnung erfordert 33-Bit-Ganzzahlen.)

Eigentlich können Sie die zweite Konstante durch ersetzen 042104210021ULL, da Sie nur 8 Bit zählen, aber es sieht nicht so symmetrisch aus.

Wie funktioniert das? Denk an c bitweise und erinnere dich daran (a + b) % c = (a % c + b % c) % c, und (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

Wenn Sie keine 64-Bit-Arithmetik zur Verfügung haben, können Sie sich teilen c In Knabbereien und jede Hälfte durchführen, 9 Operationen nehmen. Dies erfordert nur 13 Bits, daher funktioniert die Verwendung von 16- oder 32-Bit-Arithmetik.

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

Zum Beispiel wenn 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

Sehen Sie sich die Seite "Bit Twiddling Hacks" an: http://graphics.stanford.edu/~seanner/bithacks.html#countbitssetKernighan

Dafür gibt es viele gute Lösungen.

Auch diese Funktion in ihrer einfachsten Implementierung ist ziemlich trivial. Sie sollten sich die Zeit nehmen, um zu lernen, wie das geht.

Answer 5

Für eine Ganzzahl, die so klein wie ein nicht signiertes SHAR ist, erhalten Sie die beste Leistung mit einem kleinen Lookup-Tisch.

Ich weiß, welche Bevölkerungszahlalgorithmen Sie erwähnen. Sie arbeiten, indem sie die Arithmetik von mehreren Wörtern machen, die kleiner sind als eine Ganzzahl, die in einem Register gespeichert ist.

Diese Technik heißt SWAR (http://en.wikipedia.org/wiki/swar).

Für weitere Informationen empfehlen Sie Ihnen, die Website von Hackers Delight zu sehen: www.hackersdelight.org. Er hat einen Beispielcode und hat ein Buch geschrieben, das diese Tricks im Detail erklärt.

Answer 6

Wie bereits beantwortet, funktionieren die Standardmethoden des Zählens von Bits auch auf nicht signierten Zeichen.

Beispiel:

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

Answer 7

Ein nicht signiertes Zeichen ist genauso eine "Nummer", die ein 32-Bit-Schwimmer oder eine 32-Bit-Schwimmerin oder eine Ganzzahl ist, eine "Zahl", was der Compiler für sie für darstellt, was sich darstellt.

Wenn Sie sich einen Char als Bits vorstellen:

01010011 (8 Bit);

Sie können die festgelegten Bits zählen, indem Sie Folgendes ausführen:

Nehmen Sie den Wert, sagen wir x und nehmen Sie x % 2, der Rest beträgt entweder 1 oder 0. Das heißt, abhängig von der Endiantheit des Zeichens, der linken oder rechts am meisten. Akkumulieren Sie den Rest in einer separaten Variablen (dies ist die resultierende Anzahl von festgelegten Bits).

Dann >> (rechte Schicht) 1 Bit.

Wiederholen Sie, bis 8 Bit verschoben wurden.

Der C -Code sollte ziemlich einfach aus meinem Pseudocode zu implementieren sein, aber im Grunde genommen im Grunde genommen

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

Basis auf dem Post -E -Post haben wir die No -verzweigte 8 -Bit -Version. Es ist im hexadezimalen Ausdruck.

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

Wenden Sie es zweimal an, wir haben eine 16bits -Version, die 9 Operationen benötigt.

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

Hier schreibe ich eine Variante 16bits -Version, die 64Bit -Register und 11 Operationen benötigt. Es scheint nicht besser als das vorherige, aber es verwendet nur 1 Modulo -Betrieb.

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