如何进行二进制扇形

Question

我想导出二进制数据，如下面的示例所示：

8 bit to 16 bit: 
     0 0 0 1   0 0 0 1  (0x11)    becomes 
    0000 0011 0000 0011 (0x0303)

8 bit to 32 bit: 
       0    1    0    0    0    1    1    0 (0x46)       becomes 
    0000 1111 0000 0000 0000 1111 1111 0000 (0x0F000FF0)

16 to 32 bit: 
     0 0 0 1   0 0 1 1   0 1 1 1   1 1 1 1  (0x137F)     becomes 
    0000 0011 0000 1111 0011 1111 1111 1111 (0x030F3FFF)

由于这个问题是用bit-manipulation标记的，所以我正在寻找一个紧凑的解决方案，不需要任何循环或额外的变量。代码也应该是独立于平台的，所以内联程序集也不是我想要的。

这可能是一个重复的问题，但我不知道如何寻找它。当然，我想做的事情有一个合适的名字，但我只是不知道。

编辑：来澄清您的一些评论，下面列出了解决方案而不是包含的方法列表：

• 汇编代码(依赖于平台)
• 像循环一样的“复杂”计算(这就是为什么我用bit-fiddling标记这个问题)
• 附加的运行时变量(例如助手常量、查找表、.)

既然您要求这样做，下面是关于我的用例的一些更详细的信息:我正在研究嵌入式平台(微控制器)，并希望屏蔽注册。这个具体的例子是关于IO寄存器的，在这里，每个端口有16个pad，还有几个端口寄存器来配置pad。其中一些配置寄存器使用2位每垫，约4位。因此，如果我想在访问寄存器时掩蔽单个磁盘，我需要相应地屏蔽这些寄存器。

假设我有两个配置寄存器，并希望访问pad 4和8：

uint32_t configreg_2perpad;       // the first configuration register
uint32_t configreg_4perpad_low;   // lower half of the second configuration register
uint32_t configreg_4perpad_high;  // higher half of the second configuration register

uint8_t pad4 = 3;                 // we start counting at 0, of course
uint8_t pad8 = 7;
uint16_t pad_mask = (1 << pad4) |
                    (1 << pad8);  // this is now 0x0088

所以，我现在要寻找的是对pad_mask的一些明智的操作，因此我得到了寄存器的掩码，这将是

uint32_t configreg_2perpad_mask = 0x0000C0C0;
uint32_t configreg_4perpad_low_mask = 0xF000F000;
uint32_t configreg_4perpad_high_mask = 0x00000000;

显然，由于内存( RAM和flash)在Cs上都是非常稀缺的资源，所以我更喜欢不需要其他静态变量的解决方案，比如查找表(浪费RAM)或静态函数(浪费flash)。

Answer 1

扇8位到16位可以在几行代码中完成：

uint16_t n = 0x11;
n = (n | (n << 4)) & 0x0f0f;
n = (n | (n << 2)) & 0x3333;
n = (n | (n << 1)) & 0x5555;
n = (n | (n << 1));
printf("0x%04x\n", n);  // prints 0x0303

这就是它的工作原理。从16位变量中的8位开始：

0000 0000 abcd efgh     // letters a to h represent the bits of the 8-bit number

左移4位和OR：n = n | (n << 4)

0000 abcd ???? efgh     // bits with a '?' are garbage we don't want

屏蔽垃圾：n = n & 0x0f0f

0000 abcd 0000 efgh

左移2位和OR：n = n | (n << 2)

00ab ??cd 00ef ??gh

屏蔽垃圾：n = n & 0x3333

00ab 00cd 00ef 00gh

左移1位，OR：n = n | (n << 1)

0a?b 0c?d 0e?f 0g?h

屏蔽垃圾：n = n & 0x5555

0a0b 0c0d 0e0f 0g0h

现在剩下的就是复制比特：n = n | (n << 1)

aabb ccdd eeff gghh

这也可以通过查找表来完成。表本身正好是16个字节。将其声明为static const允许编译器将表放入ROM中。节省的代码大小(较少的移位和掩蔽操作)通常可以弥补表使用的ROM。查找方法应该更快(2次查找，2次转移，1次掩码，1次OR)，而不是(4次，3次，4次)。

static const uint8_t table[16] = {
    0x00, 0x03, 0x0c, 0x0f, 0x30, 0x33, 0x3c, 0x3f,
    0xc0, 0xc3, 0xcc, 0xcf, 0xf0, 0xf3, 0xfc, 0xff
};

uint16_t n = 0x11;
n = (table[n >> 4] << 8) | table[n & 0xf];
printf("0x%04x\n", n);  // prints 0x0303

从8位到32位的扇形大约与8到16位相同，但它最终需要更多的重复：

uint32_t n = 0x46;
n = (n | (n << 12)) & 0x000f000f;
n = (n | (n <<  6)) & 0x03030303;
n = (n | (n <<  3)) & 0x11111111;
n = (n | (n << 1));
n = (n | (n << 2));
printf("0x%08x\n", n);  // prints 0x0f000ff0

复制注释中的位(由@wim建议)的替代方法是替换

n = (n | (n << 1));
n = (n | (n << 2));

使用

n = (n << 4) - n;

从16位到32位的扇形需要额外的移位和掩码步骤：

uint32_t n = 0x137f;
n = (n | (n << 8)) & 0x00ff00ff;
n = (n | (n << 4)) & 0x0f0f0f0f;
n = (n | (n << 2)) & 0x33333333;
n = (n | (n << 1)) & 0x55555555;
n = (n | (n << 1));
printf("0x%08x\n", n);  // prints 0x030f3fff

Answer 2

假设每字节8位。2补体弓。

这就是我一开始的想法：

uint32_t Eight_To_Sixteen(const uint8_t source)
{

    uint32_t result = (source & 1);
    result |= ((source & 2) << 1);        
    result |= ((source & 4) << 2);
    result |= ((source & 8) << 3);
    result |= ((source & 0x10) << 4);
    result |= ((source & 0x20) << 5);
    result |= ((source & 0x40) << 6);
    result |= ((source & 0x80) << 7);
    return (result | (result << 1));
}

上面的情况还不错。请注意，它是如何将结果折叠起来复制所有位的。

然后，我开始比较一种2位表查找方法：

uint32_t Eight_To_Sixteen(const uint8_t source)
{
    static const int table[] = { 0, 3, 0xc, 0xf };
    uint32_t result = table[(source & 0x03)];
    result |= (table[(source & 0x0c)>>2]) << 4;
    result |= (table[(source & 0x30) >> 4]) << 8;
    result |= (table[(source & 0xc0) >> 6]) << 12;
    return result;
}

仍然是基准测试，但后者生成的代码要少得多。您可以扩展它，使其具有更大的查找表，并支持更广泛的输入。