Понимание левого и правого побитового сдвига на 128-битном числе

Question

Артишок101 спросил это :

Допустим, у меня есть массив из 4 32-разрядных целых чисел, который я использую для хранения 128-разрядного числа

Как мне выполнить сдвиг влево и вправо для этого 128-битного числа? "

Мой вопрос связан с ответом, который Ремус Русану дал:

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);
    }
}

Давайте просто сосредоточимся на одной смене, скажем, левой. В частности,

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

Как это сдвигает влево 128-битное число? Я понимаю, что такое сдвиг битов, << сдвигает биты влево, (8-разрядное число), например, 00011000, сдвиг влево 2 - это 01100000. То же самое относится к сдвигу вправо, но вправо. Тогда единственная «труба» | ИЛИ означает, что в результате будет любое 1 из 32-битных чисел. </p>

Как a = (a << k) | (b >> (32-k)) правильно сдвигает первую часть (32) 128-битного числа?

Answer 1

Эта техника несколько идиоматична.Давайте упростим до a и b.Мы начинаем с:

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

и хотим сдвинуть влево на некоторое количество, чтобы получить:

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

Так что X это просто a << k.y - это k msbs b, выровненных по правому краю в слове.Вы получаете этот результат с b >> (32-k).

Итак, в целом вы получаете:

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

[Примечание: этот подход действителен только для 1 <= <code>k <=31, поэтому ваш код на самом деле неверный.] </em>

Answer 2

Когда биты a сдвинуты влево, что-то должно заполнить пространство, оставшееся справа. Поскольку a и b концептуально примыкают друг к другу, пустота, оставленная смещением битов a, заполняется битами, сдвинутыми с конца b. Выражение b >> (32-k) вычисляет биты, которые сдвинуты от b.

Answer 3

Вы должны помнить, что при сдвиге допустимо "потерять" данные.

Самый простой способ понять сдвиг - это представить себе окно.Например, давайте работать с байтами.Вы можете просмотреть байт как:

  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        ]

Теперь сдвиг - это почти перемещение этого окна:

  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

Если вы посмотрите на направление стрелок, вы можете подумать об этомкак с фиксированным окном и движущимся контентом ... так же, как ваш модный сенсорный экран мобильного телефона!

Итак, что происходит в выражении a = (a << k) | (b >> (32-k))?

• a << k выбирает 32 - k крайние правые биты a и перемещает их влево, создавая пространство k 0 с правой стороны
• b >> (32-k) выбирает k крайние левые биты b и переместите их вправо, создавая пространство 32 - k 0 на левой стороне
• , оба слиты вместе

Возвращаясь к использованию байтовых укусов:

• Предположим, что a равно [a7, a6, a5, a4, a3, a2, a1, a0]
• Предположим, что b равно [b7, b6, b5. b4, b3, b2, b1, b0]
• Предположим, что k равно 3

Представленное число:

// 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           ]

Итак:

• a << 3 фактически становится a4 a3 a2 a1 a0 0 0 0
• b >> (8 - 3) becomes 0 0 0 0 0 b7 b6 b5
• в сочетании с | мы получаем a4 a3 a2 a1 a0 b7 b6 b5

промыть и повторить:)

Answer 4

мой вариант для логического сдвига влево 128-битного числа в среде с прямым порядком байтов:

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;
}

Answer 5

Для упрощения рассмотрим 16-разрядное короткое число без знака, где мы сохраняем старший и младший байты как unsigned char h, l соответственно. Чтобы упростить дальнейшее, давайте просто сдвинем его влево на один бит, чтобы посмотреть, как это происходит.

Я записываю это как 16 последовательных битов, так как это то, что мы моделируем:

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

так, [h, l] << 1 будет

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

(верхний бит, h7 повернут сверху, а младший бит заполнен нулями). Теперь давайте разберем это обратно на h и 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)

и т.д.

Answer 6

Обратите внимание, что в другом случае k гарантированно будет 32 или меньше. Таким образом, каждая часть вашего большего числа может быть сдвинута на k бит. Однако, сдвиг его влево или вправо приводит к тому, что k старших / младших битов становится равным 0. Чтобы сдвинуть все 128-битное число, необходимо заполнить эти k бит битами, «сдвинутыми» из соседнего числа.

В случае сдвига влево на k, k младших битов старшего числа должны быть заполнены k старшими битами младшего числа. чтобы получить эти старшие k битов, мы сдвигаем это (32-битное) число вправо на 32-k биты, и теперь мы получили эти биты в правильном положении, чтобы заполнить нулевые k битов из более высокого числа.

Кстати: код, приведенный выше, предполагает, что беззнаковое целое равно ровно 32 бита. Это не портативно.