Eine Sammlung klassischer Bit-Hacks: Power-of-two prüfen, lowest set bit isolieren, Bits zählen, schnelles Absolutwert. Mit Erklärung, warum sie funktionieren.

Bit-Tricks sind Idiome, mit denen sich häufige Aufgaben in einer einzigen oder ganz wenigen Operationen lösen lassen. In modernem Anwendungs-Code sind sie selten Pflicht, weil Compiler vieles selbst erkennen. In Systemprogrammierung, Embedded-Software oder Performance-kritischen Schleifen sind sie aber Werkzeuge, die man kennen sollte. Hier eine Auswahl der wichtigsten Klassiker mit Erklärung.

1. Prüfen, ob eine Zahl Zweierpotenz ist

bool isPowerOfTwo(unsigned int x) {
    return x != 0 && (x & (x - 1)) == 0;
}

Hintergrund: eine Zweierpotenz hat genau ein gesetztes Bit. x - 1 setzt dieses Bit zurück und alle Bits darunter auf 1. Das AND zwischen den beiden ist nur dann 0, wenn x tatsächlich eine Zweierpotenz war.

Beispiel mit x = 8:

x     = 0001000
x - 1 = 0000111
AND   = 0000000  ✓

Mit x = 6:

x     = 0000110
x - 1 = 0000101
AND   = 0000100  ≠ 0, also keine Zweierpotenz

2. Niedrigstes gesetztes Bit isolieren

unsigned int lowestSetBit(unsigned int x) {
    return x & -x;
}

In Zweierkomplement-Darstellung ist -x dasselbe wie ~x + 1. Das ergibt eine Zahl, die genau das niedrigste 1-Bit von x gemeinsam mit x hat. Alle höheren Bits unterscheiden sich.

Beispiel x = 12 (00001100):

x   = 00001100
-x  = 11110100
AND = 00000100   (das LSB-Bit von x)

Wird gerne in Algorithmen wie Fenwick-Trees genutzt, wo man wiederholt das niedrigste Bit braucht.

3. Niedrigstes gesetztes Bit löschen

x = x & (x - 1);

Schon im ersten Trick gesehen. In einer Schleife angewandt, kann man damit elegant alle gesetzten Bits einer Zahl durchgehen.

int popcount(unsigned int x) {
    int count = 0;
    while (x) {
        count++;
        x &= x - 1;
    }
    return count;
}

Die Schleife läuft genau so oft, wie x gesetzte Bits hat, nicht so oft wie x Bits hat. Bei dünn besetzten Zahlen ist das deutlich schneller als das Bit-für-Bit-Prüfen.

Hinweis: moderne CPUs haben einen eigenen POPCNT-Befehl. In GCC nutzt man __builtin_popcount(x), das den Befehl auf unterstützten Architekturen nutzt.

4. Maximum oder Minimum ohne Branch

int max_int(int a, int b) {
    return a - ((a - b) & ((a - b) >> 31));
}

Wirkung: wenn a < b, ist a - b negativ, das oberste Bit ist 1, der arithmetische Shift produziert lauter 1en, das AND lässt a - b durch, dann wird es von a abgezogen, Ergebnis ist b. Ansonsten wird 0 abgezogen, Ergebnis ist a.

Der praktische Wert ist heute begrenzt: moderne CPUs erkennen branch-frei rechnen meist selbst und nutzen Conditional-Move-Instruktionen. Aber im Verständnis von Bit-Operationen ist es ein lehrreiches Beispiel.

5. Absolutwert ohne Branch

int abs_int(int x) {
    int mask = x >> 31;
    return (x + mask) ^ mask;
}

Wenn x positiv ist, ist mask = 0, und der Ausdruck wird zu x XOR 0 = x. Wenn x negativ ist, ist mask = -1 (alle Bits 1), und der Ausdruck wird zu (x - 1) XOR -1, was dem Zweierkomplement und damit dem Negieren entspricht.

Funktioniert nicht für den niedrigsten negativen Wert (INT_MIN), weil dessen Absolutwert nicht in int passt.

6. Vorzeichen ohne Vergleich

int sign(int x) {
    return (x > 0) - (x < 0);
}

Nicht streng bitorientiert, aber elegant. Liefert -1, 0 oder +1. Beide Boolean-Vergleiche werden zu 0 oder 1 ausgewertet, die Subtraktion ergibt das Vorzeichen.

7. Werte tauschen ohne Hilfsvariable (XOR-Swap)

a ^= b;
b ^= a;
a ^= b;

Funktioniert wegen der Selbstinversen-Eigenschaft von XOR. Allerdings: in modernen Compilern ist die Variante mit Hilfsvariable schneller, weil sie keine Datenabhängigkeit zwischen den drei Anweisungen hat. Der XOR-Swap ist eher ein historisches Curiosum als ein echter Performance-Trick.

Wichtig: funktioniert nicht, wenn a und b denselben Speicherplatz haben (z. B. zwei Verweise auf dasselbe Array-Element). Dann wird der Wert genullt.

8. Modulo mit Zweierpotenz

y = x % 8;
y = x & 7;   // dasselbe, schneller

Funktioniert nur für vorzeichenlose Zahlen und nur, wenn die Modulo-Zahl eine Zweierpotenz ist. % 7 lässt sich nicht so vereinfachen.

9. Nächste Zweierpotenz nach oben

unsigned int nextPowerOfTwo(unsigned int x) {
    x--;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x + 1;
}

Setzt nach dem -- zuerst alle Bits ab dem höchsten gesetzten auf 1 (durch die Shift-OR-Kette), dann +1 macht daraus die nächste reine Zweierpotenz. Wird gerne in Hashtable-Implementierungen oder Speicher-Pools genutzt.

10. Anzahl führender Nullen

// GCC built-in, in einem CPU-Takt auf modernen Prozessoren
int leading_zeros = __builtin_clz(x);

Wer manuell will, kann es mit einer Binärsuche aufbauen. Aber für die meisten Fälle reicht der Built-in.

Wann lohnen sich solche Tricks?

In einer Web-Anwendung mit Datenbank-Roundtrips von Millisekunden verschwendet niemand Zeit mit Bit-Tricks. In einer Inner Loop, die Milliarden Mal pro Sekunde läuft (Bildverarbeitung, Kompression, Krypto), zählt jeder eingesparte Takt. In Embedded-Code mit knappen Ressourcen sind Bit-Tricks oft sogar die einzige Option.

Faustregel: erst messen, dann optimieren. Wer einen Trick einsetzt, sollte ihn kommentieren, sonst versteht ihn der nächste Leser nicht.

Klassische Quelle

Wer tiefer einsteigen will: das Buch Hacker’s Delight von Henry S. Warren (zweite Auflage 2012) sammelt Hunderte solcher Idiome inklusive Beweisen. Die Online-Sammlung Bit Twiddling Hacks von Sean Eron Anderson an der Stanford University ist eine kostenlose Kurzfassung.

Bit-Tricks: schnelle Idiome für Performance-Code