Bitweiser NOT-Operator enttäuscht meine Erwartung

[Rolf B]

Hallo Buchhalter,

nach etwas nachdenken kommt mir der Gedanke, dass man Bits auch viel einfacher flippen kann. Der Weg dahin ist allerdings mit etwas Algebra gepflastert…

Beispiel: In einer 5-Bit Welt wird die 13 zur Binärzahl 01101 und kann als eine Summe ihrer Bitwerte dargestellt werden:

$$13 = 0b01101 = 0\cdot 16 + 1\cdot 8 + 1\cdot 4 + 0\cdot 2 + 1\cdot 1$$

Wenn ich die Bits rein mathematisch invertieren will, muss ich die Koeffizienten vor den Stellenwerten umdrehen, aus 0 1 machen und aus 1 0, dafür muss ich den Koeffizienten jeweils von 1 abziehen. Die Invertierung ergibt also

$$(1-0)\cdot 16 + (1-1)\cdot 8 + (1-1)\cdot 4 + (1-0)\cdot 2 + (1-1)\cdot 1$$
ausmultiplizieren
$$= 1\cdot 16 - 1\cdot 16 + 1\cdot 8 - 1\cdot 8 + 1\cdot 4 - 1\cdot 4 + 1\cdot 2 -0\cdot 2 + 1\cdot 1 -1 \cdot 1$$
umsortieren
$$= 1\cdot 16 + 1\cdot 8 + 1\cdot 4 + 1\cdot 2 + 1\cdot 1 - 0\cdot 16 - 1\cdot 8 - 1\cdot 4 - 0\cdot 2 - 1 \cdot 1$$
gruppieren
$$= (1\cdot 16 + 1\cdot 8 + 1\cdot 4 + 1\cdot 2 + 1\cdot 1) - (0\cdot 16 + 1\cdot 8 + 1\cdot 4 + 0\cdot 2 + 1 \cdot 1)$$

Ich habe das absichtlich so mühsam aufgedröselt. Denn jetzt sieht man, dass die linke Klammer der Binärzahl 11111 entspricht und die rechte Klammer dem Eingabewert in die Rechnung: 01101. Ich hätte das auch mit $$a_0$$ bis $$a_i$$ und einer Orgie von $$\sum$$ Zeichen schreiben können. Aber bevor Du schreiend wegrennst...

Bei einer Wortlänge L entspricht ein Wort aus lauter 1-Bits dem Wert $$2^L-1$$. Warum? Das ist eine der Übungsaufgaben zur Vollständigen Induktion aus der Schule: $$\sum_{i=0}^n 2^i= 2^{n+1}$$.

Was haben wir gesehen? Die Bits einer Binärzahl der Wortlänge L zu flippen, bedeutet, sie von $$2^L-1$$ abzuziehen.

In Code:

function flip16bit(a) {
   return 65535-a;
}

Natürlich nur unter der Annahme, dass irgendwo sichergestellt ist, dass a im richtigen Wertebereich ist. Sonst gibt's GIGO (garbage in, garbage out).

Rolf