Am Bit packen

Wieviele sind es?

Hin und wieder treibt es einen, die Zahl der gesetzten Bits einer Variable herauszufinden.
Es kommt immer mal wieder vor, daß man wissen muß, wie viele Steine in einer Reihe, auf dem Feld etc. sind. Unter Umständen muß 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.