高效的bithifting一个int数组？

Question

要在同一页面上,我们假设sizeof(int)= 4和sizeof(long)= 8.

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

我正在考虑一个辅助变量,如long,它将计算第一对元素(索引0和1)的bitshift并设置第一个元素(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位,你将位数mod 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;
}

Answer 2

看一下Java 中的 BigInteger 实现，它在内部将数据存储为字节数组。具体可以查看函数leftShift()。语法与 C 语言相同，因此编写一对这样的函数不会太困难。还要考虑到，当涉及到位移位时，您可以利用 C 中的 unsinged 类型。这意味着在 Java 中，为了安全地移位数据而不弄乱符号，您通常需要更大的类型来保存数据（即要移位的 int ）一个短的，一个长的来移动一个整数，...）