128 位数字的按位移位运算

Question

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

如何对这个 128 位数字执行左移和右移？

谢谢！

Answer 1

使用uint128？如果可以的话，请使用 x86 SSE 指令，它们正是为此而设计的。 （然后，当您对值进行位移后，您就可以执行其他 128 位操作了...）

SSE2 位移平均需要约 4 条指令，其中有一个分支（一个 case 语句）。移位超过 32 位也没有问题。执行此操作的完整代码是使用 gcc 内在函数而不是原始汇编程序，位于 sseutil.c 中（github：“SSE2 的不寻常用途”）——粘贴到这里有点太大了。

许多人使用 SSE2 的障碍是轮班操作需要立即（恒定）轮班计数。您可以通过一些 C 预处理器调整来解决这个问题（wordpress：C 预处理器技巧)。之后，您将获得如下操作序列：

LeftShift(uint128 x, int n) = _mm_slli_epi64(_mm_slli_si128(x, n/8), n%8)

for n = 65..71, 73..79, … 121..127
...用两条指令完成整个轮班。

Answer 2

void shiftl128 (
    unsigned int& a,
    unsigned int& b,
    unsigned int& c,
    unsigned int& d,
    size_t k)
{
    assert (k <= 128);
    if (k >= 32) // shifting a 32-bit integer by more than 31 bits is "undefined"
    {
        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) // shifting a 32-bit integer by more than 31 bits is "undefined"
    {
        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);
    }
}

Answer 3

为什么不使用位集而不使用 128 位数字？使用位集，您可以调整您想要的大小。另外，您可以对其执行相当多的操作。

您可以在此处找到有关这些内容的更多信息：

http://www.cppreference。 com/wiki/utility/bitset/start?do=backlink

Answer 4

首先，如果您要移位 n 位且 n 大于或等于 32，则除以 32 并移位整个整数。这应该是微不足道的。现在，您剩下的班次计数从 0 到 31。如果为零，请早点返回，您就完成了。

对于每个整数，您需要将剩余的 n 移位，然后将相邻整数移位相同的量，并合并每个整数的有效位。

Answer 5

既然您提到要将 128 位值存储在 4 个整数的数组中，您可以执行以下操作：

void left_shift(unsigned int* array)
{   
    for (int i=3; i >= 0; i--)
    {
        array[i] = array[i] << 1;

        if (i > 0)
        {
            unsigned int top_bit = (array[i-1] >> 31) & 0x1;
            array[i] = array[i] | top_bit;
        }
    }
}

void right_shift(unsigned int* array)
{   
    for (int i=0; i < 4; i++)
    {
        array[i] = array[i] >> 1;

        if (i < 3)
        {
            unsigned int bottom_bit = (array[i+1] & 0x1) << 31;
            array[i] = array[i] | bottom_bit;
        }
    }
}