在内存块上实现位移的最佳方法

Question

我想对任意大小的指定内存块进行位移。我考虑过 char 解决问题 char，我发现这个解决方案有效。

void rshift(void *self, int shift, size_t size) {
    char *s = self;
    bool take, pass;
    for (int i = 0; i < shift; i++) {
        take = false;
        for (int j = 0; j < size; j++, take = pass) {
            pass = *(s + j) & 1;
            *(s + j) >>= 1;
            *(s + j) ^= (-take ^ *(s + j)) & (1 << (CHAR_BIT - 1));
        }
    }
}

其中 self 是要移动的内存块，size 是它在 chars 中的大小，shift 是要移动的位数。基本上我正在做的是，对于每个字节，我将它移动一个，将丢失的位传递给下一个字节。

但是这个算法很糟糕，我认为它就像一个 O(shift * size) 之类的东西，我很确定整个事情可以用 O(size).

来解决

注意：我展示的是右移，左移是一回事

Answer 1

首先，你不需要shift循环。你可以先做一个模数：int n = shift % CHAR_BIT;和一个除法int m = shift / CHAR_BIT;。实际上，将 char 变量旋转 k * CHAR_BIT 次等同于直接将字节移动 k。此外，您可以使用 int pass = *(s + j) & ((1 << n) - 1); 直接精确提取 *(s + j) 的 n 最低有效位。然后，n位的移位可以直接用简单的左移（*(s + j) >>= n;）。最后，可以使用 *(s + j) |= pass << (CHAR_BIT - n)); 完成 pass 与先前左移值的“合并”。请注意，在这种情况下，先前的操作对 unsigned char 变量更安全（比带符号的 char），因为负符号类型的 右移是实现定义的 .这使得算法运行在 O(size) 时间内。

优化是如果 shift 为 0 则不执行任何操作，否则当 n 为 0 时使用 memmove。

另一个优化是使用更大的类型（如 uint64_t）同时处理多个 char 项目。但是，这假设 CHAR_BIT 是 8，世界上几乎所有（理智的）现代处理器都是这种情况。但是，您应该非常小心这种优化，因为 loaded/stored 值需要正确对齐并且 type punning must be safe (using either memcpy or a unions) so to not break the strict aliasing rule （导致未定义的行为）。

另一种优化方法是在大多数 ARM 处理器上使用 SIMD intrinsics (like SSE, AVX2 on modern x86-64 processors or NEON）。这种优化比处理更大的类型更有效，也更安全。但是，使用内在函数需要高级编程技能，并且会降低代码的可移植性并且通常几乎不可读。 SSE/NEON 每个周期可以同时处理 16 个 8 位项目，而 AVX2 最多可以处理 32 个 8 位项目，从而使代码速度大大加快。请注意，编译器有时可以自动为您执行此操作（假设 优化标志已启用 ）。

请注意，写 s[j] 而不是 *(s + j) 更易于阅读且更短。另请注意，表达式 -take ^ *(s + j) 肯定会导致 实现定义的 行为，因为 -1 可以在不同的体系结构上以不同的方式表示（参见 two's complement and one's complement），尽管几乎所有现代处理器都使用二进制补码。

在内存块上实现位移的最佳方法

Best way to implement bit shifting over a block of memory

c

algorithm

performance

bit-shift