How to shift an array of bytes by 12-bits
我想将字节数组的内容向左移动12位。
例如，从此类型为uint8_t shift[10]的数组开始：
1
| {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0A, 0xBC} |
我想将它向左移动12位，结果是：
1
| {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xAB, 0xC0, 0x00} |
为指针欢呼！
此代码的工作原理是为每个字节预备12位，然后向前复制适当的位。 12位是下一个字节的下半部分(半字节)和相距2个字节的上半部分。
1
2
3
4
5
6
7
8
9
| 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位，然后再开始移位即可。也许您想循环移位，以将溢出的位放回底部？也许您想重新分配数组并使它变大？将溢出返回给调用方？如果非零数据溢出，是否返回布尔值？您必须定义"进位"对您意味着什么。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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，表示：
1
2
| 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来处理最后一个字节
给定长度为N的
a，我们得到：
1
2
3
4
5
| 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 = number of bits modulo 8中将存在M赋值语句。
通过转换为指针，可以在某些机器上使循环更有效
1
2
3
| for (p = a, p2=a+N-2; p != p2; ++p) {
*p = ((*(p+1) & 0x0f) << 4) | (((*(p+2) & 0xf0) >> 4);
} |
并使用CPU支持的最大整数数据类型。
(我刚刚输入了这个内容，所以现在对于某些人来说是复习代码的好时机，特别是因为众所周知，位纠错很容易弄错。)
让它成为移位8位整数数组中的N位的最佳方法。
1
2
3
| 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位，则可以通过按位与运算，并使用位移位运算符进行移位来计算溢出：
1
2
3
| // 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位整数并执行移位。但这大概不是很方便，我建议反对这一点。只是一个可能的优化。
这是一个使用临时变量的可行解决方案：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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 <=计数<= num_words
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #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\
", array[0]);
printf("%x\
", array[1]);
printf("%x\
", array[2]);
printf("%x\
", array[3]);
printf("%x\
", array[4]);
return 0;
} |
有一些边缘情况使这成为一个整洁的问题：
-
输入数组可能为空
-
最后一位和倒数第二位需要特别处理，因为它们的移位为零
这是一个简单的解决方案，它遍历数组，将下一个字节的低位半字节复制到其高位半字节，然后将下一个下一个(2)字节的高位半字节复制到其低位-点菜。为了节省两次对预读指针的取消引用，它维护了一个带有" last "和" next "字节的两个元素的缓冲区：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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可以更有效地访问内存。当然，尾随字节也必须进行特殊处理，以免在数组末尾触及内存。
@Joseph，请注意，变量为8位宽，而移位为12位宽。您的解决方案仅适用于N <=可变大小。
如果可以假设您的数组是4的倍数，则可以将该数组转换为uint64_t数组，然后对其进行处理。如果不是4的倍数，则可以尽可能多地使用64位块，然后一个接一个地处理其余部分。
这可能需要更多的编码，但是我认为最终它会更优雅。
|
