c - 如何使用按位运算符交错 2 个 bool 值？

Question

假设我有两个 4 位值，ABCD 和 abcd。如何使用按位运算符交错它，使其变为 AaBbCcDd？伪 C 中的示例:

nibble a = 0b1001;
nibble b = 0b1100;
char c = foo(a,b);
print_bits(c); 
// output: 0b11010010

注意:4 位只是为了说明，我想用两个 32 位整数来做到这一点。

Answer 1

这称为完美洗牌 操作，在 Bible Of Bit Bashing 中有详细讨论，Hacker's Delight作者 Henry Warren，第 7-2 节“改组位”。

假设x是一个32位整数，高16位为a，低16位为b :

   unsigned int x = (a << 16) | b;   /* put a and b in place */

以下简单明了的类 C 代码完成了完美的洗牌:

x = (x & 0x0000FF00) << 8 | (x >> 8) & 0x0000FF00 | x & 0xFF0000FF;
x = (x & 0x00F000F0) << 4 | (x >> 4) & 0x00F000F0 | x & 0xF00FF00F;
x = (x & 0x0C0C0C0C) << 2 | (x >> 2) & 0x0C0C0C0C | x & 0xC3C3C3C3;
x = (x & 0x22222222) << 1 | (x >> 1) & 0x22222222 | x & 0x99999999;

他还提供了一种替代形式，这种形式在某些 CPU 上速度更快，而且(我认为)更加清晰和可扩展:

unsigned int t;  /* an intermediate, temporary variable */
t = (x ^ (x >> 8)) & 0x0000FF00;  x = x ^ t ^ (t << 8);
t = (x ^ (x >> 4)) & 0x00F000F0;  x = x ^ t ^ (t << 4);
t = (x ^ (x >> 2)) & 0x0C0C0C0C;  x = x ^ t ^ (t << 2);
t = (x ^ (x >> 1)) & 0x22222222;  x = x ^ t ^ (t << 1);

我看到您已将问题编辑为要求从两个 32 位输入获得 64 位结果。我不得不考虑如何扩展沃伦的技术。我认为这不会太难，但我必须考虑一下。如果其他人想从这里开始并提供 64 位版本，我很乐意为他们投票。

为 64 位编辑

我直接将第二个解决方案扩展到 64 位。首先，我将每个常量的长度加倍。然后我在开头添加了一行来交换相邻的 double-bytes 并将它们混合。在接下来的 4 行中，与 32 位版本几乎相同，第一行交换相邻的 字节 并混合，第二行下降为半字节，第三行为双位, 最后一行到单个位。

unsigned long long int t;  /* an intermediate, temporary variable */
t = (x ^ (x >> 16)) & 0x00000000FFFF0000ull;  x = x ^ t ^ (t << 16);
t = (x ^ (x >> 8))  & 0x0000FF000000FF00ull;  x = x ^ t ^ (t << 8);
t = (x ^ (x >> 4))  & 0x00F000F000F000F0ull;  x = x ^ t ^ (t << 4);
t = (x ^ (x >> 2))  & 0x0C0C0C0C0C0C0C0Cull;  x = x ^ t ^ (t << 2);
t = (x ^ (x >> 1))  & 0x2222222222222222ull;  x = x ^ t ^ (t << 1);