优化的字节数组移位器

Question

我相信以前有人问过这个问题，但我需要在长度可变的字节数组上实现一个移位运算符。我环顾了一下，但我还没有找到任何标准的方法。我想出了一个有效的实现，但我不确定它的效率如何。有没有人知道移动数组的标准方法，或者至少对如何提高我的实现的性能有什么建议；

char* baLeftShift(const char* array, size_t size, signed int displacement,char* result)
{
    memcpy(result,array,size);
    short shiftBuffer = 0;
    char carryFlag = 0;
    char* byte;
    if(displacement > 0)
    {
        for(;displacement--;)
        {
            for(byte=&(result[size - 1]);((unsigned int)(byte))>=((unsigned int)(result));byte--)
            {
                shiftBuffer = *byte;
                shiftBuffer <<= 1;
                *byte = ((carryFlag) | ((char)(shiftBuffer)));
                carryFlag = ((char*)(&shiftBuffer))[1];
            }
        }
    }
    else
    {
        unsigned int offset = ((unsigned int)(result)) + size;
        displacement = -displacement;
        for(;displacement--;)
        {
            for(byte=(char*)result;((unsigned int)(byte)) < offset;byte++)
            {
                shiftBuffer = *byte;
                shiftBuffer <<= 7;
                *byte = ((carryFlag) | ((char*)(&shiftBuffer))[1]);
                carryFlag = ((char)(shiftBuffer));
            }
        }
    }
    return result;
}

Answer 1

如果我可以补充@dwelch所说的，你可以试试这个。

1. 只需将字节移动到它们的最终位置。然后，例如，如果每个字节仍然需要左移3位到下一个更高的字节中，则会留下一个移位计数，例如3。(这假设在您的脑海中，字节是按从右到左的升序排列的。)然后，
2. 将每个字节向左旋转3。查找表可能比单独执行实际的旋转更快。然后，在每个字节中，要移位的3位现在位于字节的右端。
3. 现在制作一个掩码M，它是(1<<3)-1，它只是打开的低位3位。
4. 现在按照从高位字节到低位字节的顺序执行以下操作：

c[i] ^= M & (c[i] ^ c[i-1])

这将在掩码M下将位从c[i-1]复制到c[i]。

对于最后一个字节，只需使用0代替c[i-1]。

对于右移位，同样的想法。

Answer 2

我的第一个建议是消除位移周围的for循环。您应该能够在没有for(;displacement--;)循环的情况下执行必要的移位。对于大于7的位移，事情变得有点棘手，因为你的内部循环边界会改变，你的源偏移量不再是1。也就是说，你的输入缓冲区偏移量变成了magnitude / 8，你的移位变成了magnitude % 8。

Answer 3

它看起来确实效率低下，也许这就是内森所指的。

假设一个字符是8位，在代码运行的地方，有两件事要做，首先移动整个字节，例如，如果你的输入数组是0x00, 0x00，0x12 ,0x34，并且你左移了8位，那么你就会得到0x00 0x12 0x34 0x00，没有理由在循环中一次移动一位8次。因此，首先将数组中的整个字符移位(displacement>>3)位置，并使用某种形式的for(ra=(displacement>>3);ra>3)] = arrayra；arrayra来填充用零创建的孔一个好的编译器会预先计算(displacement>>3)，位移&7，7-(位移&7)，一个好的处理器会有足够的寄存器来保存所有这些值。您可以通过为每一项创建单独的变量来帮助编译器，但根据编译器和您如何使用它，这可能会使情况变得更糟。

不过，底线是代码的时间。执行一千次1位移位，然后执行一千次2位移位，等等，对整个事情进行计时，然后尝试不同的算法，以相同的方式计时，看看优化是否会产生影响，使其变得更好或更差。如果您提前知道此代码将仅用于单个或少于8位的移位，请相应地调整计时测试。

使用进位标志意味着您知道，许多处理器都有专门用于使用标准寄存器长度(一次一位)循环进位的无限长移位的指令。C语言不直接支持的。对于单个位移位的链接，您可以考虑使用汇编语言，并且可能优于C代码。至少单个位移位比C代码快。一种混合移动字节的方法，如果要移位的位数(位移&7)可能小于4，则使用汇编程序，否则使用C循环。同样，计时测试将告诉您优化在哪里。