Verständnis der bitweisen Verschiebung nach links und rechts bei einer 128-Bit-Zahl

Question

Artischocke101 fragte dies :

Angenommen, ich habe ein Array mit 4 32-Bit-Ganzzahlen, die ich zum Speichern der 128-Bit-Zahl verwende

Wie kann ich bei dieser 128-Bit-Zahl eine Links- und Rechtsverschiebung durchführen?"

Meine Frage bezieht sich auf die Antwort, die Remus Rusanu gegeben hat:

void shiftl128 (
    unsigned int& a,
    unsigned int& b,
    unsigned int& c,
    unsigned int& d,
    size_t k)
{
    assert (k <= 128);
    if (k > 32)
    {
        a=b;
        b=c;
        c=d;
        d=0;
        shiftl128(a,b,c,d,k-32);
    }
    else
    {
        a = (a << k) | (b >> (32-k));
        b = (b << k) | (c >> (32-k));
        c = (c << k) | (d >> (32-k));
        d = (d << k);
    }
}

void shiftr128 (
    unsigned int& a,
    unsigned int& b,
    unsigned int& c,
    unsigned int& d,
    size_t k)
{
    assert (k <= 128);
    if (k > 32)
    {
        d=c;
        c=b;
        b=a;
        a=0;
        shiftr128(a,b,c,d,k-32);
    }
    else
    {
        d = (c << (32-k)) | (d >> k); \
        c = (b << (32-k)) | (c >> k); \
        b = (a << (32-k)) | (b >> k); \
        a = (a >> k);
    }
}

Konzentrieren wir uns auf eine Schicht, sagen wir die linke Schicht. Genauer gesagt,

a = (a << k) | (b >> (32-k));
b = (b << k) | (c >> (32-k));
c = (c << k) | (d >> (32-k));
d = (d << k);

Wie wird die 128-Bit-Zahl dadurch nach links verschoben? Ich weiß, was Bit-Shifting ist, << verschiebt Bits nach links, (8-Bit-Zahl) wie 00011000 links verschoben 2 ist 01100000. Dasselbe gilt für die Rechtsverschiebung, aber nach rechts. Dann ist die einzelne "pipe" | ODER, was bedeutet, dass jede 1 in jeder 32-Bit-Zahl im Ergebnis enthalten ist.

Wie ist a = (a << k) | (b >> (32-k)) den ersten Teil (32) der 128-Bit-Zahl korrekt zu verschieben?

Answer 1

Diese Technik ist einigermaßen idiomatisch. Vereinfachen wir einfach auf a y b . Wir beginnen mit:

+----------+----------+
|    a     |    b     |
+----------+----------+

und wir wollen einen gewissen Betrag nach links verschieben, um ihn zu erhalten:

+----------+----------+
|  a    :  |  b    :  |  c  ...
+----------+----------+
|<--x-->|  |
      ->|y |<-

Also X ist einfach a << k . y es el k msbs von b , rechtsbündig im Wort. Sie erhalten dieses Ergebnis mit b >> (32-k) .

Sie erhalten also insgesamt:

a = x | y
  = (a << k) | (b >> (32-k))

[Hinweis: Dieser Ansatz gilt nur für 1 <= k <= 31, also ist Ihr Code eigentlich falsch].

Answer 2

Wenn die Bits von a nach links verschoben werden, muss etwas den Platz ausfüllen, der am rechten Ende übrig bleibt. Da a y b sind konzeptionell angrenzend die Lücke, die durch das Verschieben der Bits von a wird durch die Bits aufgefüllt, die vom Ende der Tabelle verschoben werden. b . Der Ausdruck b >> (32-k) berechnet die Bits, die von der b .

Answer 3

Sie müssen bedenken, dass es bei einer Verschiebung akzeptabel ist, Daten zu "verlieren".

Am einfachsten lässt sich die Verschiebung verstehen, wenn man sich ein Fenster vorstellt. Lassen Sie uns zum Beispiel mit Bytes arbeiten. Sie können sich ein Byte wie folgt vorstellen:

  0 0 0 0 0 0 0 0 a b c d e f g h 0 0 0 0 0 0 0 0
                 [      B        ]

Beim Verschieben geht es nur darum, dieses Fenster zu verschieben:

  0 0 0 0 0 0 0 0 a b c d e f g h 0 0 0 0 0 0 0 0
 [     B >> 8    ]
   [     B >> 7    ]
     [     B >> 6    ]
       [     B >> 5    ]
  0 0 0 0 0 0 0 0 a b c d e f g h 0 0 0 0 0 0 0 0
         [     B >> 4    ]
           [     B >> 3    ]
             [     B >> 2    ]
               [     B >> 1    ]
  0 0 0 0 0 0 0 0 a b c d e f g h 0 0 0 0 0 0 0 0
                   [     B << 1    ]
                     [     B << 2    ]
                       [     B << 3    ]
                         [     B << 4    ]
  0 0 0 0 0 0 0 0 a b c d e f g h 0 0 0 0 0 0 0 0
                           [     B << 5    ]
                             [     B << 6    ]
                               [     B << 7    ]
                                 [     B << 8    ]
  0 0 0 0 0 0 0 0 a b c d e f g h 0 0 0 0 0 0 0 0

Wenn Sie sich die Richtung der Pfeile ansehen, können Sie sich vorstellen, dass es ein festes Fenster und einen beweglichen Inhalt gibt... genau wie Ihr schicker Handy-Touchscreen!

Was geschieht also mit dem Ausdruck a = (a << k) | (b >> (32-k)) ?

• a << k wählt die 32 - k die äußersten rechten Bits von a und verschieben sie nach links, wodurch ein Raum von k 0 auf der rechten Seite
• b >> (32-k) wählt die k die äußersten linken Bits von b und verschieben sie nach rechts, wodurch ein Raum von 32 - k 0 auf der linken Seite
• die beiden werden miteinander verschmolzen

Zurück zur Verwendung von Bites mit Byte-Länge:

• Angenommen, dass a es [a7, a6, a5, a4, a3, a2, a1, a0]
• Angenommen, dass b es [b7, b6, b5. b4, b3, b2, b1, b0]
• Angenommen, dass k es 3

Die dargestellte Zahl ist:

// before
 a7 a6 a5 a4 a3 a2 a1 a0 b7 b6 b5 b4 b3 b2 b1 b0
[           a           ]
                        [           b           ]

// after (or so we would like)
 a7 a6 a5 a4 a3 a2 a1 a0 b7 b6 b5 b4 b3 b2 b1 b0
         [           a           ]
                                 [           b           ]

Also:

• a << 3 wird tatsächlich a4 a3 a2 a1 a0 0 0 0
• b >> (8 - 3) wird 0 0 0 0 0 b7 b6 b5
• kombiniert mit | erhalten wir a4 a3 a2 a1 a0 b7 b6 b5

spülen und wiederholen :)

Answer 4

Beachten Sie, dass im anderen Fall k garantiert 32 oder weniger ist. Jeder Teil Ihrer größeren Zahl kann also tatsächlich um k Bits verschoben werden. Durch die Verschiebung nach links oder rechts werden die k höheren/niedrigeren Bits jedoch zu 0. Um die gesamte 128-Bit-Zahl zu verschieben, müssen Sie diese k Bits mit den "herausgeschobenen" Bits der Nachbarzahl auffüllen.

Bei einer Linksverschiebung um k müssen die k unteren Bits der höheren Zahl mit den k oberen Bits der niedrigeren Zahl aufgefüllt werden. Um diese oberen k Bits zu erhalten, verschieben wir die (32-Bit-)Zahl um 32-k Bits nach rechts, und nun haben wir diese Bits an der richtigen Position, um die null k Bits der höheren Zahl aufzufüllen.

Übrigens: Der obige Code geht davon aus, dass ein unsigned int genau 32 Bit hat. Das ist nicht portabel.

Answer 5

Zur Vereinfachung betrachten wir eine vorzeichenlose 16-Bit-Short-Datei, bei der wir die High- und Low-Bytes wie folgt speichern unsigned char h, l beziehungsweise. Zur weiteren Vereinfachung verschieben wir sie einfach um ein Bit nach links, um zu sehen, wie das geht.

Ich schreibe es als 16 aufeinanderfolgende Bits, denn das ist das, was wir modellieren:

[h7 h6 h5 h4 h3 h2 h1 h0 l7 l6 l5 l4 l3 l2 l1 l0]

also, [h, l] << 1 wird

[h6 h5 h4 h3 h2 h1 h0 l7 l6 l5 l4 l3 l2 l1 l0 0]

(das oberste Bit, h7, wurde von oben nach unten gedreht, und das unterste Bit ist mit Null gefüllt). Nun zerlegen wir das wieder in h y l ...

[h, l] = [h6 h5 h4 h3 h2 h1 h0 l7 l6 l5 l4 l3 l2 l1 l0 0]
=> h = [h6 h5 h4 h3 h2 h1 h0 l7]
     = (h << 1) | (l >> 7)

usw.