了解128位数字的左右按位移位

Question

朝鲜蓟101 问这个:

假设我有一个由4个32位整数组成的数组,用于存储128位数字

如何在这个128位数字上执行左右移位？"

我的问题与Remus Rusanu给出的答案有关:

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.同样适用于右移,但是在右边.然后是单个"管道"| 是OR意味着任何32位数字中的任何1都将出现在结果中.

如何正确a = (a << k) | (b >> (32-k))移动128位数的第一部分(32)？

Answer 1

这种技术有些惯用.让我们简化为a和b.我们从:

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

我们想向左移一些金额来获得:

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

所以X很简单a << k. y是k单词中b右对齐的msbs .你获得了那个结果b >> (32-k).

总的来说,你得到:

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

[注意:此方法仅对1 <= k<= 31有效,因此您的代码实际上是错误的.]