Rolf B: Bitweiser NOT-Operator enttäuscht meine Erwartung

Beitrag lesen

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

--
sumpsi - posui - obstruxi
0 60

Bitweiser NOT-Operator enttäuscht meine Erwartung

Der Buchhalter
  • javascript
  1. 2
    Gunnar Bittersmann
    1. 0
      Der Buchhalter
      1. 0
        Gunnar Bittersmann
        1. 0
          Der Buchhalter
          1. 0
            Gunnar Bittersmann
            1. 0
              Der Buchhalter
          2. 0
            Rolf B
            1. 0
              Gunnar Bittersmann
              1. 0
                Rolf B
            2. 0
              Der Buchhalter
              1. 0
                Rolf B
              2. 0
                Christian Kruse
                1. 0

                  Zombies

                  Der Martin
                  • zu diesem forum
                  1. -1
                    Gunnar Bittersmann
        2. 0
          Der Buchhalter
          1. 0
            Robert B.
            1. 0
              Gunnar Bittersmann
              1. 0
                Robert B.
                1. 0
                  Der Martin
                  1. 0
                    Robert B.
                    1. 0
                      Der Martin
                      1. 0
                        Robert B.
                        • mathematik
                        1. 0
                          Rolf B
                          1. 0
                            Robert B.
                          2. 1
                            MudGuard
                            • sprache
                            1. 0
                              Gunnar Bittersmann
                              1. 0
                                Tabellenkalk
                              2. 0
                                Gunnar Bittersmann
                                1. 0
                                  Der Martin
                                  1. 0
                                    Auge
                                    • menschelei
                                    • sprache
                                    1. 0
                                      Der Martin
                                    2. 0
                                      Gunnar Bittersmann
                                      1. 0
                                        Gunnar Bittersmann
            2. 0
              Der Buchhalter
            3. 0
              Gunnar Bittersmann
  2. 0
    Rolf B
    1. 0
      Gunnar Bittersmann
      1. 0
        Rolf B
        1. 0
          Der Martin
          1. 0
            Rolf B
        2. 0
          Gunnar Bittersmann
  3. -3
    TS
    • javascript
    • versionsverwaltung
    1. 0
      Rolf B
      1. 0
        JürgenB
        1. 0
          Rolf B
          1. 0
            JürgenB
    2. 0
      Mitleser 2.0
      1. 0
        TS
        • javascript
        • mitarbeit
        • versionsverwaltung
        1. 0
          Mitleser 2.0
          1. 0
            TS
            • mitarbeit
          2. 0
            Rolf B
            1. -2
              TS
              1. 0
                Rolf B
  4. 0
    Samuel fiedler
    1. 0
      Gunnar Bittersmann
  5. 0
    Ich:
  6. 0
    Alexander Hein
    • php
    1. 1
      Rolf B
      1. 1
        TS
        • datentypen
        • php