如何使用按位运算符交错2个布尔值？
假设我有两个4位值， ABCD和abcd 。 如何使用按位运算符对其进行交错，使其成为AaBbCcDd ？ 伪C中的示例：
nibble a = 0b1001; nibble b = 0b1100; char c = foo(a,b); print_bits(c); // output: 0b11010010
注意：4位仅用于说明，我想用两个32位整数执行此操作。
这被称为完美的随机操作，它在“抨击圣经”，“亨利·沃伦的黑客喜悦 ”，第7-2节“洗牌比特”中详细讨论过。
假设x是一个32位整数，其高位为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;
他还提供了一种替代forms，在某些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位版本几乎相同，第一行交换相邻的字节和混合，第二行下降到半字节，第三行下降到双位，最后一行下降到单行位。
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);
来自斯坦福大学的“Bit Twiddling Hacks”页面： https ：//graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious
uint32_t x = /*...*/, y = /*...*/; uint64_t z = 0; for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed... { z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1); }
看看他们提出的不同的页面和更快的算法来实现相同的目标。
像这样：
#include typedef unsigned int half; typedef unsigned long long full; full mix_bits(half a,half b) { full result = 0; for (int i=0; i>i)&1)<<(2*i+1))|(((b>>i)&1)<<(2*i+0)); return result; }
这是一个基于循环的解决方案，希望比这里已有的其他解决方案更具可读性。
#include #include #include uint64_t interleave(uint32_t a, uint32_t b) { uint64_t result = 0; int i; for (i = 0; i < 31; i++) { result |= (a >> (31 - i)) & 1; result <<= 1; result |= (b >> (31 - i)) & 1; result <<= 1; } // Skip the last left shift. result |= (a >> (31 - i)) & 1; result <<= 1; result |= (b >> (31 - i)) & 1; return result; } void printBits(uint64_t a) { int i; for (i = 0; i < 64; i++) printf("%lu", (a >> (63 - i)) & 1); puts(""); } int main(){ uint32_t a = 0x9; uint32_t b = 0x6; uint64_t c = interleave(a,b); printBits(a); printBits(b); printBits(c); }
我已经使用了这篇文章中使用的2个技巧/操作如何设置，清除和切换一个位？ setting a bit at particular index并checking the bit at particular index 。
以下代码仅使用这两个操作实现。
int a = 0b1001; int b = 0b1100; long int c=0; int index; //To specify index of c int bit,i; //Set bits in c from right to left. for(i=32;i>=0;i--) { index=2*i+1; //We have to add the bit in c at this index //Check a bit=a&(1<
输出： 210 ，即0b11010010