如何向移字节数组，由12位

StackOverflow https://stackoverflow.com/questions/29437

  •  09-06-2019
  •  | 
  •  

题

我想转变的内容字节数组由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}
有帮助吗？

解决方案

欢呼为指针!

这个代码工作的展望未来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;

贾斯汀写道：
@迈克，你的解决方案的工作，但不随身携带。

好吧，我想说一个正常的移操作做到了这一点(称为溢出)，而只是允许的额外的位掉下来的左右。这是很简单的进行如果你想到的只是保存的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 是低nybble(一半字节)的 a[i]
  • 让 iH 是高nybble的 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], 这不仅影响的最后两个字节

因此，我们

  • 处理一般情况下，用于通过循环 N-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.它可以很容易地推广到移 N bits, 注意到会有 M 分配的语句在哪里 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);
}

和通过使用最大的整数数据类型的支持。

(我只是输入该文本中，所以现在是个好时间用于个人审查的码，特别是因为点摆弄是众所周知的容易得到错误的。)

让它成为最好的方式转移 N 位列8位整数。

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 位可以计算出的溢出通过这样做位，和转移使用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位整数和执行的转移。但是prabably不是很便携式的，我会建议反对这一点。只是一个可能的优化。

这里的一个工作方案，采用临时变量：

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

迈克的解决方案或许更快，由于使用临时变量。

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;
}

@约瑟夫，注意到这些变量是8位，而转变为12位宽。你的解决方案只适用于N <=变量的大小。

如果你能承担你的阵列是一个多重的4你可以投阵列入一系列uint64_t然后在那工作。如果它不是一个4，你可以在64位块，你可以尽可能和工作在其余部分之一。这可能有点更多编码，但我认为这是更优雅的端。

有几个边缘情况，这使这一整个问题：

  • 输入阵列可能是空的
  • 最后一个和下一个比特需要特殊对待，因为他们有零位转移到他们

这里有一个简单的解决方案，其中的循环在过阵列复制低了轻咬下一个字节到其高了蚕食和高了轻咬下一个-下一个(+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 是的，我们设一个和唯一元零。
  • 时 length 是两个，我们设置高了半的第一个字节到低了轻咬的第二字节(这是位的12-16日),和第二字节到零。我们不用激活的循环。
  • 时 length 大于两个我们打的循环，洗字节横跨两个元素的缓冲区。

如果效率是你的目标，答案可能在很大程度上取决于你的机构。通常你应该维持两个元素的缓冲器，但是处理一个字机(32/64位unsigned integer)，在一段时间。如果你们转移大量的数据，它将是值得治疗的第一数字作为一个特殊的情况下，这样你可以得到你的机器一词指字-对准。最Cpu取存储器更有效果的访问落在字机的边界。当然，尾字节有待处理的专太，所以你不要碰过去的记忆结束阵列。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top