如何将字节数组移动 12 位

Question

我想将字节数组的内容左移 12 位。

例如，从这个 uint8_t shift[10] 类型的数组开始：

{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0A, 0xBC}

我想将其向左移动 12 位，结果是：

{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xAB, 0xC0, 0x00}

Answer 1

让我们让它成为在 8 位整数数组中移动 N 位的最佳方式。

N            - Total number of bits to shift
F = (N / 8) - Full 8 bit integers shifted
R = (N % 8) - Remaining bits that need to be shifted

我想从这里开始，您必须找到利用这些数据在数组中移动整数的最佳方法。 通用算法是通过从数组右侧开始并移动每个整数 F 索引来应用完整的整数移位。 零填充新空的空间。 然后最后对所有索引执行 R 位移位，再次从右侧开始。

在将 0xBC 移位 R 位的情况下，您可以通过按位 AND 计算溢出，并使用位移运算符进行移位：

// 0xAB shifted 4 bits is:
(0xAB & 0x0F) >> 4   // is the overflow      (0x0A)
0xAB << 4            // is the shifted value (0xB0)

请记住，4 位是只是一个简单的掩码：0x0F 或只是 0b00001111。 这很容易计算、动态构建，甚至可以使用简单的静态查找表。

我希望这足够通用。 我根本不擅长 C/C++，所以也许有人可以清理我的语法或更具体。

额外奖励：如果您对 C 语言很熟练，您也许能够将多个数组索引编入单个 16、32 甚至 64 位整数并执行移位。 但这可能不太便携，我建议不要这样做。 只是一个可能的优化。

Answer 2

这是一个使用临时变量的可行解决方案：

void shift_4bits_left(uint8_t* array, uint16_t size)
{
    int i;
    uint8_t shifted = 0x00;    
    uint8_t overflow = (0xF0 & array[0]) >> 4;

    for (i = (size - 1); i >= 0; i--)
    {
        shifted = (array[i] << 4) | overflow;
        overflow = (0xF0 & array[i]) >> 4;
        array[i] = shifted;
    }
}

调用此函数 3 次以实现 12 位移位。

由于使用了临时变量，迈克的解决方案可能更快。

Answer 3

32 位版本...:-) 处理 1 <= count <= num_words

#include <stdio.h>

unsigned int array[] = {0x12345678,0x9abcdef0,0x12345678,0x9abcdef0,0x66666666};

int main(void) {
  int count;
  unsigned int *from, *to;
  from = &array[0];
  to = &array[0];
  count = 5;

  while (count-- > 1) {
    *to++ = (*from<<12) | ((*++from>>20)&0xfff);
  };
  *to = (*from<<12);

  printf("%x\n", array[0]);
  printf("%x\n", array[1]);
  printf("%x\n", array[2]);
  printf("%x\n", array[3]);
  printf("%x\n", array[4]);

  return 0;
}

Answer 4

求指点万岁！

该代码的工作原理是向前查看每个字节的 12 位并向前复制正确的位。 12 位是下一个字节的下半部分（nybble）和 2 个字节之外的上半部分。

unsigned char length = 10;
unsigned char data[10] = {0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0A,0xBC};
unsigned char *shift = data;
while (shift < data+(length-2)) {
    *shift = (*(shift+1)&0x0F)<<4 | (*(shift+2)&0xF0)>>4;
    shift++;
}
*(data+length-2) = (*(data+length-1)&0x0F)<<4;
*(data+length-1) = 0x00;

贾斯汀写道：
@Mike，你的解决方案有效，但不执行。

好吧，我想说正常的移位操作就是这样做的（称为溢出），并且只是让多余的位从右侧或左侧掉落。 如果您愿意的话，它很容易携带 - 只需在开始移位之前保存 12 位即可。 也许您想要循环移位，将溢出的位放回底部？ 也许您想重新分配数组并使其更大？ 将溢出返回给调用者？ 如果非零数据溢出，则返回布尔值？ 你必须定义进位对你来说意味着什么。

unsigned char overflow[2];
*overflow = (*data&0xF0)>>4;
*(overflow+1) = (*data&0x0F)<<4 | (*(data+1)&0xF0)>>4;
while (shift < data+(length-2)) {
    /* normal shifting */
}  
/* now would be the time to copy it back if you want to carry it somewhere */
*(data+length-2) = (*(data+length-1)&0x0F)<<4 | (*(overflow)&0x0F);
*(data+length-1) = *(overflow+1);  

/* You could return a 16-bit carry int, 
 * but endian-ness makes that look weird 
 * if you care about the physical layout */
unsigned short carry = *(overflow+1)<<8 | *overflow;

Answer 5

这是我的解决方案，但更重要的是我解决问题的方法。

我通过

• 绘制内存单元并绘制从目的地到源的箭头来解决这个问题。
• 制作了一个表格显示上面的图。
• 用相对字节地址标记表中的每一行。

这向我展示了这种模式：

• 让 iL 为 a[i] 的低位 nybble（半字节），
• 让 iH 为 iH 的高位 nybble code>a[i]
• iH = (i+1)L
• iL = (i+2)H

此模式适用于所有字节。

翻译成 C 语言，这意味着：

a[i] = (iH << 4) OR iL
a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4)

我们现在又做了三个观察：

• 因为我们从左到右执行赋值，所以我们不需要在临时变量中存储任何值。
• 尾部有一个特殊情况：末尾的所有 12 位都为零。
• 我们必须避免读取数组之外的未定义内存。 由于我们从未读取超过 a[i+2] 的内容，因此这只影响最后两个字节

因此，我们

• 通过循环 N-2 个字节 并执行来处理一般情况上面的一般计算
• 通过设置 iH = (i+1)L 来处理倒数第二个字节，在
• 通过将其设置为 0 来处理最后一个字节

给定 a 的情况下， 长度为 N，我们得到：

for (i = 0; i < N - 2; ++i) {
    a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4);
}
a[N-2] = (a[N-1) & 0x0f) << 4;
a[N-1] = 0;

就是这样……数组左移了 12 位。 它可以很容易地推广到移位N位，注意会有M赋值语句，其中M =位数模8，我相信。

可以在某些机器上提高循环的效率

for (p = a, p2=a+N-2; p != p2; ++p) {
    *p = ((*(p+1) & 0x0f) << 4) | (((*(p+2) & 0xf0) >> 4);
}

通过转换为指针并使用 CPU 支持的最大整数数据类型，

。 （我刚刚输入了这个，所以现在是某人检查代码的好时机，特别是因为位调整非常容易出错。）

Answer 6

有一些边缘情况使这成为一个巧妙的问题：

• 输入数组可能为空
• 最后一位和倒数第二位需要特殊处理，因为它们有零位移入其中

这是一个循环的简单解决方案在数组上，将下一个字节的低位半字节复制到其高位半字节中，并将下一个（+2）字节的高位半字节复制到其低位半字节中。 为了避免取消引用前瞻指针两次，它维护一个包含“最后”和“下一个”字节的双元素缓冲区：

void shl12(uint8_t *v, size_t length) {
  if (length == 0) {
    return; // nothing to do
  }

  if (length > 1) {
    uint8_t last_byte, next_byte;
    next_byte = *(v + 1);

    for (size_t i = 0; i + 2 < length; i++, v++) {
      last_byte = next_byte;
      next_byte = *(v + 2);
      *v = ((last_byte & 0x0f) << 4) | (((next_byte) & 0xf0) >> 4);
    }

    // the next-to-last byte is half-empty
    *(v++) = (next_byte & 0x0f) << 4;
  }

  // the last byte is always empty
  *v = 0;
}

考虑边界情况，这会连续激活函数的更多部分：

• 当 length 为零，我们在不触及内存的情况下退出。
• 当 length 为 1 时，我们将唯一的元素设置为零。
• 当length为2时，我们将第一个字节的高位半字节设置为第二个字节的低位半字节（即位12-16），并将第二个字节设置为零。 我们不激活循环。
• 当 length 大于 2 时，我们会进入循环，在两元素缓冲区中重新排列字节。

如果效率是您的目标，那么答案可能很大程度上取决于您的机器的架构。 通常，您应该维护两元素缓冲区，但一次处理一个机器字（32/64 位无符号整数）。 如果您要移动大量数据，则值得将前几个字节视为特殊情况，以便您可以使机器字指针字对齐。 如果访问落在机器字边界上，大多数 CPU 会更有效地访问内存。 当然，尾随字节也必须进行特殊处理，这样您就不会触及数组末尾之后的内存。

Answer 7

@Joseph，请注意变量是 8 位宽，而移位是 12 位宽。 您的解决方案仅适用于 N <= 可变大小。

如果您可以假设您的数组是 4 的倍数，您可以将数组转换为 uint64_t 数组，然后对其进行处理。 如果它不是 4 的倍数，您可以尽可能多地处理 64 位块，然后逐一处理剩余部分。
这可能需要更多的编码，但我认为最终会更优雅。