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.
						

Kommentar(e)

Kommentarformular ein-/ausblenden