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

Meine Variante für die logische Linksverschiebung von 128-Bit-Zahlen in Little-Endian-Umgebung:

typedef struct { unsigned int component[4]; } vector4; 
vector4 shift_left_logical_128bit_le(vector4 input,unsigned int numbits) {
    vector4 result;
    if(n>=128) {
         result.component[0]=0;
         result.component[1]=0;
         result.component[2]=0;
         result.component[3]=0;
         return r;
    }
    result=input;
    while(numbits>32) {
        numbits-=32;
        result.component[0]=0;
        result.component[1]=result.component[0];
        result.component[2]=result.component[1];
        result.component[3]=result.component[2];
    }
    unsigned long long temp;
    result.component[3]<<=numbits;
    temp=(unsigned long long)result.component[2];
    temp=(temp<<numbits)>>32;
    result.component[3]|=(unsigned int)temp;
    result.component[2]<<=numbits;
    temp=(unsigned long long)result.component[1];
    temp=(temp<<numbits)>>32;
    result.component[2]|=(unsigned int)temp;
    result.component[1]<<=numbits;
    temp=(unsigned long long)result.component[0];
    temp=(temp<<numbits)>>32;
    result.component[1]|=(unsigned int)temp;
    result.component[0]<<=numbits;
    return result;
}