7

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

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

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

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

4

3 回答 3

9

没有必要使用 along作为中介。如果你向左移动，从最高的 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;
}
于 2010-05-05T14:36:48.200 回答
3

对于其他任何人来说，这是 Mark Ransom 对于任何位数和任何类型的数组的上述答案的更通用版本：

/* This function shifts an array of byte of size len by shft number of
bits to the left. Assumes array is big endian. */

#define ARR_TYPE uint8_t

void ShiftLeft(ARR_TYPE * arr_out, ARR_TYPE * arr_in, int arr_len, int shft)
{
    const int int_n_bits = sizeof(ARR_TYPE) * 8;
    int msb_shifts = shft % int_n_bits;
    int lsb_shifts = int_n_bits - msb_shifts;
    int byte_shft = shft / int_n_bits;
    int last_byt = arr_len - byte_shft - 1;
    for (int i = 0;  i < arr_len;  i++){
        if (i <= last_byt){
            int msb_idx = i + byte_shft;
            arr_out[i] = arr_in[msb_idx] << msb_shifts;
            if (i != last_byt)
                arr_out[i] |= arr_in[msb_idx + 1] >> lsb_shifts;
        }
        else arr_out[i] = 0;
    }
}
于 2017-11-03T16:47:18.597 回答
1

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

于 2010-05-05T14:35:00.830 回答