logo标签列表

128位数的按位移位操作

c++cbit-manipulationbitwise-operatorsbit-shift
7

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

如何对这个128位数字进行左移和右移操作？

谢谢！

为什么不使用2个int64_t？这将比4个int32_t更简单。 - phuclv
2
https://dev59.com/N1zUa4cB1Zd3GeqP34N- - phuclv
5个回答
6

需要处理 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)

对于 n = 65..71, 73..79, … 121..127，可以通过两条指令来完成整个移位过程。

你应该展示相关的代码而不是链接到外部网站。我试着浏览了你的宏实现，但可能需要展开以使访问者更清晰地理解。 - jww
4
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);
    }
}
大于 32 时失败。你不认为一个函数比宏更好吗？ - Martin York
@Remus Rusanu和MArtin：非常感谢！ - artichoke101
除了提到的大于32位的移位问题之外，宏版本还存在许多常见的宏问题：使用的参数没有完全加括号，如果参数不是32位类型或有符号类型，则可能会得到不希望的行为，这些宏不是“语句安全”的（应该包装在do/while(0)或类似的语句中）。此外，这些宏似乎执行移位操作，但名称却暗示旋转 - 如果我遇到使用它们的代码，我会感到困惑。任何考虑使用它们的人都应该注意修复这些问题。或者使用函数版本。 - Michael Burr
1
@Remus Rusanu：这段代码仍然存在一个错误。递归的条件应该是 if (k >= 32)。 - Henry
请尝试使用GCC 4.8及以上版本或Clang 3.2及以上版本进行编译，并使用-fsanitize=undefined选项。UBsan就像一个小偷一样...... - jww
显示剩余5条评论
2
1
@C Johnson 我同意可以使用位集，但我更多地从逻辑的角度来看待它，并将这4个32位整数作为约束条件。 - artichoke101
1

首先，如果您要移位n位且n大于或等于32，请除以32并移动整数。这应该很简单。现在您还剩下一个从0到31的剩余移位计数。如果它为零，请提前返回，您已完成。

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

1

既然您提到将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;
        }
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接