比特黑客:扩大比特

Question

我试图将uint16_t输入转换为uint32_t位掩码.输入中的一位在输出位掩码中切换两位.以下是将4位输入转换为8位位掩码的示例:

Input    Output
ABCDb -> AABB CCDDb

A,B,C,D are individual bits

Example outputs:

0000b -> 0000 0000b
0001b -> 0000 0011b
0010b -> 0000 1100b
0011b -> 0000 1111b
....
1100b -> 1111 0000b
1101b -> 1111 0011b
1110b -> 1111 1100b
1111b -> 1111 1111b

有没有一种方法来实现这种行为？

Answer 1

Binary Magic Numbers的交错位包含了线索:

uint32_t expand_bits(uint16_t bits)
{
    uint32_t x = bits;

    x = (x | (x << 8)) & 0x00FF00FF;
    x = (x | (x << 4)) & 0x0F0F0F0F;
    x = (x | (x << 2)) & 0x33333333;
    x = (x | (x << 1)) & 0x55555555;

    return x | (x << 1);
}

前四个步骤以8位,4位,2位,1位的组连续地将源位交织为零位,导致在00AB00CD第一步0A0B0C0D之后,在第二步之后,依此类推.最后一步然后将每个偶数位(包含原始源位)复制到相邻奇数位中,从而实现所需的位排列.

许多变体都是可能的.最后一步也可以编码为x + (x << 1)或3 * x.所述|在前四个步骤操作员可以通过更换^运营商.也可以修改掩码,因为某些位自然为零并且不需要清除.在一些处理器上,短掩模可以作为中间体结合到机器指令中,减少了构造和/或加载掩模常数的努力.增加无序处理器的指令级并行性并针对具有shift-add或整数乘加指令的那些进行优化也可能是有利的.包含各种这些想法的一个代码变体是:

uint32_t expand_bits (uint16_t bits)
{
    uint32_t x = bits;

    x = (x ^ (x << 8)) & ~0x0000FF00;
    x = (x ^ (x << 4)) & ~0x00F000F0;
    x = x ^ (x << 2);
    x = ((x & 0x22222222) << 1) + (x & 0x11111111);
    x = (x << 1) + x;

    return x;
}

Answer 2

将4位输入映射到8位输出的最简单方法是使用16个输入表.那么这只是从一次提取4位uint16_t,进行表查找,并将8位值插入输出的问题.

uint32_t expandBits( uint16_t input )
{
    uint32_t table[16] = {
        0x00, 0x03, 0x0c, 0x0f,
        0x30, 0x33, 0x3c, 0x3f,
        0xc0, 0xc3, 0xcc, 0xcf,
        0xf0, 0xf3, 0xfc, 0xff
    };

    uint32_t output;
    output  = table[(input >> 12) & 0xf] << 24;
    output |= table[(input >>  8) & 0xf] << 16;
    output |= table[(input >>  4) & 0xf] <<  8;
    output |= table[ input        & 0xf];
    return output;
}

这在性能和可读性之间提供了适当的折衷.它没有cmaster的over-the-top查找解决方案的性能,但它肯定比thndrwrks神奇的神秘解决方案更容易理解.因此,它提供了一种可应用于更多种类问题的技术,即使用小型查找表来解决更大的问题.