14

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

7 回答 7

8

万岁指点！

该代码通过为每个字节向前看 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;

Justin 写道:
@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;
于 2008-08-27T04:02:45.970 回答
4

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

我通过

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

这向我展示了模式：

  • iL设为低 nybble（半字节）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 bits最后全部为零。
  • 我们必须避免读取数组之外的未定义内存。因为我们从不读取超过a[i+2]，这只会影响最后两个字节

所以，我们

  • 通过循环 forN-2 bytes并执行上面的一般计算来处理一般情况
  • 通过设置处理倒数第二个字节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 bits。它可以很容易地推广到 shift N bits，并指出我相信会有M赋值语句 where M = number of bits modulo 8。

通过转换为指针，可以使循环在某些机器上更有效

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

并使用 CPU 支持的最大整数数据类型。

（我刚刚输入了这个，所以现在是审查代码的好时机，特别是因为众所周知，位旋转很容易出错。）

于 2008-08-27T04:16:29.633 回答
3

让它成为在N8 位整数数组中移动位的最佳方法。

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位与计算溢出，并使用位移运算符进行移位：

// 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 位整数并执行移位。但这可能不是很便携，我建议不要这样做。只是一个可能的优化。

于 2008-08-27T03:40:39.347 回答
3

这是一个有效的解决方案，使用临时变量：

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

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

于 2008-08-27T04:23:41.520 回答
1

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;
}
于 2008-08-27T04:19:09.970 回答
0

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

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

于 2008-08-27T03:44:18.200 回答
0

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

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

这是一个简单的解决方案，它循环遍历数组，将下一个字节的低位半字节复制到其高阶半字节，并将下一个（+2）字节的高阶半字节复制到其低位半字节。为了节省对前瞻指针的解引用两次，它维护了一个包含“last”和“next”字节的双元素缓冲区：

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是一时，我们将唯一的元素设置为零。
  • 当length为 2 时，我们将第一个字节的高位半字节设置为第二个字节的低位半字节（即 12-16 位），将第二个字节设置为零。我们不激活循环。
  • 当length大于 2 时，我们进入循环，在两个元素的缓冲区中打乱字节。

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

于 2008-08-27T04:43:40.770 回答