我想将字节数组的内容向左移动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}

解决方案

回答

让我们将其作为移位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运算来计算溢出，并使用bitshift运算符进行移位：

// 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位整数并执行移位。但这大概不是很方便，我建议反对这一点。只是一个可能的优化。

回答

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

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

回答

为指针欢呼！

该代码的工作方式是为每个字节预备12位，并向前复制适当的位。 12位是下一个字节的下半部分(半字节)和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;

Justin wrote:

  @Mike, your solution works, but does not carry.

好吧，我想说一个普通的移位操作就是这样做的(称为溢出)，只是让多余的位从右边或者左边掉下来。如果我们只想在开始移位之前保存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;

回答

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

我通过以下方式解决了这个问题

• 从目标到源绘制内存单元并绘制箭头。
• 做了一张显示以上图纸的表格。
• 用相对字节地址标记表中的每一行。

这向我展示了模式：

• 令" iL"为" a [i]"的低字节(半字节)
• 令" iH"为" 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处理最后一个字节

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

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支持的最大整数数据类型。

(我刚刚输入了此内容，因此现在对于某些人来说是复习代码的好时机，特别是因为众所周知，位纠错很容易出错。

回答

32位版本... :-)处理1 <=计数<= 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;
}

回答

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

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位移位。

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

回答

有几个边缘情况使这成为一个整洁的问题：

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

这是一个简单的解决方案，它遍历数组，将下一个字节的低位半字节复制到其高位半字节，将下一个下一个(+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;
}

考虑边界情况，边界情况会依次激活函数的更多部分：

• 当"长度"为零时，我们将在不影响内存的情况下纾困。
• 当"长度"为1时，我们将一个元素和唯一的元素设置为零。
• 当"长度"为2时，我们将第一个字节的高位半字节设置为第二个字节的低位半字节(即位12-16)，并将第二个字节设置为零。我们不激活循环。
• 当" length"大于2时，我们进入循环，将字节跨两个元素的缓冲区进行混洗。

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