如何使用按位运算符交错 2 个布尔值？

假设我有两个 4 位值，ABCD and abcd。如何交错它，所以它变成AaBbCcDd，使用按位运算符？伪 C 语言示例：

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

注意：4 位仅用于说明，我想用两个 32 位整数来完成此操作。

这被称为完美洗牌操作，并且在《比特攻击圣经》中有详细讨论，黑客的喜悦 http://www.hackersdelight.org/作者：Henry Warren，第 7-2 节“洗牌位”。

假设x是一个 32 位整数a在其高阶 16 位和b其低 16 位：

   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 位。首先，我将每个常量的长度加倍。然后我在开头添加了一行来交换相邻的双字节并将它们混合。下面的 4 行与 32 位版本几乎相同，第一行交换了相邻的内容bytes并混合后，第二行下降为半字节，第三行下降为双位，最后一行下降为单位。

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