c - 位破解 : Expanding bits

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

是否有一种 bithack-y 方法来实现这种行为？

Answer 1

Interleaving bits by 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 位和 0 位组，结果是 00AB00CD第一步之后，0A0B0C0D第二步之后，依此类推。最后一步将每个偶数位(包含原始源位)复制到相邻的奇数位中，从而实现所需的位排列。

许多变体是可能的。最后一步也可以编码为 x + (x << 1)或 3 * x . |前四步的运算符可以用^代替运营商。也可以修改掩码，因为某些位自然为零，不需要清除。在某些处理器上，短掩码可以作为立即数合并到机器指令中，从而减少构建和/或加载掩码常量的工作量。增加乱序处理器的指令级并行性并优化那些具有移位加法或整数乘法加法指令的处理器也可能是有利的。包含各种这些想法的一种代码变体是:

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