Am Bit packen - Bits in Ganzzahltypen zählen
Wieviele sind es?
Hin und wieder treibt es einen, die Zahl der gesetzten Bits einer Ganzzahlvariable herauszufinden. Im Umfeld der Zugsuche kommt es immer mal wieder vor, daß man wissen muss, wie viele Steine in einer Reihe, auf dem Feld etc. sind. Bei in Bitboards gespeicherten Spielefeldern bedeutet dies - Bits zählen. Unter Umständen muss diese Frage während des Programmlaufes millionenfach beantwortet werden. Die Antwort sollte daher schnell erfolgen. Üblicher Weise wird man das mit einer Variante der folgenden Funktion tun.
private int GetBitCount(ulong countThis)
{
if (0 == countThis) return 0;
int count = 0;
do {
count++;
} while ((countThis = countThis & (countThis - 1)) > 0);
return count;
}
Ihr Kern ist die Zeile: while ((countThis = countThis & (countThis - 1)) > 0).
Angenommen countThis hat den Wert 42 = 0010 1010.
- count hochzählen
- Der Ausdruck "countThis & (countThis - 1)" entfernt das niederwertigste Bit.
- Schritt 1: 0010 1010 & 0010 1001 = 0010 1000
- Schritt 2: Wert zuweisen
- Schritt 3: countThis > 0 = true -> weitermachen.
Das ist schön, braucht wenig Platz und ist einsichtig. Läuft solange es niederigste Bits gibt.
Aber wirklich schnell sind Berechnungsvarianten die auf dem Hamming Abstand beruhen.
public int bitcount(ulong countThis)
{
//binär: 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101
const ulong m1 = 0x5555555555555555;
//binär: 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011 0011
const ulong m2 = 0x3333333333333333;
//binär: 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111
const ulong m4 = 0x0f0f0f0f0f0f0f0f;
//binär: 0000 0000 1111 1111 0000 0000 1111 1111 0000 0000 1111 1111 0000 0000 1111 1111
const ulong m8 = 0x00ff00ff00ff00ff;
//binär: 0000 0000 0000 0000 1111 1111 1111 1111 0000 0000 0000 0000 1111 1111 1111 1111
const ulong m16 = 0x0000ffff0000ffff;
//binär: 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111 1111 1111 1111 1111
const ulong m32 = 0x00000000ffffffff;
countThis = (countThis & m1) + ((countThis >> 1) & m1);
countThis = (countThis & m2) + ((countThis >> 2) & m2);
countThis = (countThis & m4) + ((countThis >> 4) & m4);
countThis = (countThis & m8) + ((countThis >> 8) & m8);
countThis = (countThis & m16) + ((countThis >> 16) & m16);
countThis = (countThis & m32) + ((countThis >> 32) & m32);
return (int)countThis;
}
Was geht da vor? Schaun wir mal: für 42 als Byte.
Schritt 1: countThis = Bits an ungradem Index + Bits an gradem Index (wegen >> 1)
countThis = (00101010 & 01010101) + (00010101 & 01010101)
countThis = 00000000 + 00010101 = 00010101 = 21
Schritt 2: countThis = unteren 2 Bits im Nibble + oberen 2 Bits im Nibble (wegen >> 2)
countThis = (00010101 & 00110011) + (00000101 & 00110011)
countThis = 00010001 + 00000001 = 00010010 = 18
Schritt 3: countThis = unteres Nibble + oberes Nibble (wegen >> 4)
countThis = (00010010 & 00001111) + (00000001 & 00001111)
countThis = 00000010 + 00000001 = 00000011 = 3
Fertig
Bei größeren Typen
unteres Byte + oberes Byte
unteres Wort + oberes Wort
Usw.
