c - 高效地对 int 数组进行位移？

Question

为了在同一页面上，我们假设 sizeof(int)=4 和 sizeof(long)=8。

给定一个整数数组，将数组逻辑上向左或向右移位的有效方法是什么？

我正在考虑一个辅助变量，例如 long，它将计算第一对元素(索引 0 和 1)的位移并设置第一个元素 (0)。以这种方式继续，元素(索引 1 和 2)的位移位将由计算机计算，然后设置索引 1。

我认为这实际上是一种相当有效的方法，但也有缺点。我不能位移大于 32 位。我认为使用多个辅助变量会奏效，但我设想沿线某处递归。

Answer 1

不需要使用 long 作为中介。如果您要左移，则从最高阶 int 开始，而右移则从最低阶开始。在修改之前添加相邻元素的进位。

void ShiftLeftByOne(int * arr, int len)
{
    int i;
    for (i = 0;  i < len - 1;  ++i)
    {
        arr[i] = (arr[i] << 1) | ((arr[i+1] >> 31) & 1);
    }
    arr[len-1] = arr[len-1] << 1;
}

可以扩展此技术以进行超过 1 位的移位。如果你做的超过 32 位，你将位计数模 32 并按它移动，同时在数组中进一步移动结果。例如，要左移 33 位，代码看起来几乎相同:

void ShiftLeftBy33(int * arr, int len)
{
    int i;
    for (i = 0;  i < len - 2;  ++i)
    {
        arr[i] = (arr[i+1] << 1) | ((arr[i+2] >> 31) & 1);
    }
    arr[len-2] = arr[len-1] << 1;
    arr[len-1] = 0;
}