c - 使移动位更有效

Question

在我们公司的最新项目中，我们想将一个字符数组左移半字节，例如

char buf[] = {0x12, 0x34, 0x56, 0x78, 0x21} 

我们想让 buf 像

0x23, 0x45, 0x67, 0x82, 0x10

如何使过程更高效，如果要处理 N 个字节，您能否使时间复杂度小于 O(N)？

SOS...

Answer 1

如果没有更多上下文，我什至会质疑对实际数组的需求。如果您有 4 个字节，则可以使用 a 轻松表示uint32_t，然后您可以执行O(1)移位操作：

uint32_t x = 0x12345678;
uint32_t offByHalf = x << 4;

这样，您将使用位掩码替换数组访问，如下所示：

array[i]

相当于

(x >> 8 * (3 - i)) & 0xff

谁知道呢，算术甚至可能比内存访问更快。但不要相信我的话，对它进行基准测试。

Answer 2

不，如果你想实际移动数组，你需要至少命中每个元素一次，所以它是 O(n)。没有办法解决这个问题。您可以使用以下方法来执行此操作：

#include <stdio.h>

void shiftNybbleLeft (unsigned char *arr, size_t sz) {
    for (int i = 1; i < sz; i++)
        arr[i-1] = ((arr[i-1] & 0x0f) << 4) | (arr[i] >> 4);
    arr[sz-1] = (arr[sz-1] & 0x0f) << 4;
}

int main (int argc, char *argv[]) {
    unsigned char buf[] = {0x12, 0x34, 0x56, 0x78};
    shiftNybbleLeft (buf, sizeof (buf));
    for (int i = 0; i < sizeof (buf); i++)
        printf ("0x%02x ", buf[i]);
    putchar ('\n');
    return 0;
}

这给了你：

0x23 0x45 0x67 0x80

这并不是说您不能提高效率^(a)。如果您改为修改提取代码以使其行为不同，则可以避免移位操作。

换句话说，不要移动数组，只需设置一个偏移变量并使用它来修改提取过程。检查以下代码：

#include <stdio.h>

unsigned char getByte (unsigned char *arr, size_t index, size_t shiftSz) {
    if ((shiftSz % 2) == 0)
        return arr[index + shiftSz / 2];
    return ((arr[index + shiftSz / 2] & 0x0f) << 4)
        | (arr[index + shiftSz / 2 + 1] >> 4);
}

int main (int argc, char *argv[]) {
    unsigned char buf[] = {0x12, 0x34, 0x56, 0x78};
    //shiftNybbleLeft (buf, sizeof (buf));
    for (int i = 0; i < 4; i++)
        printf ("buf[1] with left shift %d nybbles -> 0x%02x\n",
            i, getByte (buf, 1, i));
    return 0;
}

设置为 0 ，shiftSz就好像数组没有移动。通过设置shiftSz为非零，O(1) 操作getByte()实际上将返回元素，就好像你已经将它移动了那个量一样。输出如您所料：

Index 1 with left shift 0 nybbles -> 0x34
Index 1 with left shift 1 nybbles -> 0x45
Index 1 with left shift 2 nybbles -> 0x56
Index 1 with left shift 3 nybbles -> 0x67

现在这似乎是一个人为的例子（因为它是），但在使用这样的技巧来避免潜在的昂贵操作方面有很多先例。您可能还想添加一些边界检查以捕获在数组外引用的问题。

请记住，这是一个权衡。不必移动数组所获得的收益可能会在一定程度上被提取期间完成的计算所抵消。它是否真的值得取决于你如何使用数据。如果数组很大，但您没有从中提取那么多值，那么这个技巧可能是值得的。

---

作为使用“技巧”来防止代价高昂的操作的另一个示例，我看到文本编辑器也不会费心改变行的内容（例如，在删除字符时）。相反，他们只是将字符设置为 0 代码点并在显示行时处理它（忽略 0 代码点）。

它们通常最终会清理干净，但通常会在不会影响您的编辑速度的后台进行清理。

---

^(a)虽然您可能想真正确保这是必要的。

您的一条评论指出，您的数组长度约为 500 个条目，我可以告诉您，我的非至高无上的开发框可以将该数组以每秒大约 50 万次的速度向左移动一个 nybble。

因此，即使您的分析器指出大部分时间都花在了那里，但这并不一定意味着它是大量时间。

如果存在特定的、已确定的瓶颈，您应该只考虑优化代码。

Answer 3

我将解决问题中唯一可以客观回答的部分，即：

如果要处理 N 个字节，您能否使时间复杂度小于 O(N)？

如果您需要整个输出数组，那么不，您不能做得比O(N).

如果您只需要输出数组的某些元素，那么您可以只计算这些元素。

Answer 4

由于对齐，它可能无法很好地编译，但您可以尝试在结构中使用位域偏移量。

struct __attribute__((packed)) shifted{
 char offset:4; // dump data
 char data[N]; // rest of data
};

或在某些系统上

struct __attribute__((packed)) shifted{
 char offset:4; // dump data
 char data[N]; // rest of data
 char last:4; // to make an even byte
};

struct shifted *shifted_buf=&buf;
//now operate on shifted_buf->data

或者你可以试着把它变成一个工会

union __attribute__((packed)) {
  char old[N];
  struct{
    char offset:4;
    char buf[N];
    char last:4; // to make an even byte
  }shifted;
}data;

另一种方法是将每个 int 转换为 int 和 <<4 的数组，将其减少到 N/4，但这取决于字节序。