我想要做的是采用由位对组成的64位无符号整数,如果相应对中的两个位都为0,则从中创建一个包含0的32位整数,否则为1.换句话说,转换看起来像这样的东西:
01 00 10 11
进入看起来像这样的东西
1 0 1 1
两个明显的解决方案是每个字节的强力循环或查找表,然后执行8次查找并将它们组合成OR和位移的最终结果但我确信应该有一种有效的方法来进行比特纠缠.我将在C++中为64位整数执行此操作,但如果有人知道为更短的整数执行此操作的有效方法,我确信我可以弄清楚如何扩展它.
这是一个可移植的C++实现.它似乎在我的简短测试中起作用.解交织代码基于这个SO问题.
uint64_t calc(uint64_t n) { // (odd | even) uint64_t x = (n & 0x5555555555555555ull) | ((n & 0xAAAAAAAAAAAAAAAAull) >> 1); // deinterleave x = (x | (x >> 1)) & 0x3333333333333333ull; x = (x | (x >> 2)) & 0x0F0F0F0F0F0F0F0Full; x = (x | (x >> 4)) & 0x00FF00FF00FF00FFull; x = (x | (x >> 8)) & 0x0000FFFF0000FFFFull; x = (x | (x >> 16)) & 0x00000000FFFFFFFFull; return x; }
gcc,clang和msvc都将其编译为大约30条指令.
从评论中可以进行修改.
更改第一行以使用单个位掩码操作仅选择"奇数"位.
可能(?)改进的代码是:
uint64_t calc(uint64_t n) { // (odd | even) uint64_t x = (n | (n >> 1)) & 0x5555555555555555ull; // single bits // ... the restdeinterleave x = (x | (x >> 1)) & 0x3333333333333333ull; // bit pairs x = (x | (x >> 2)) & 0x0F0F0F0F0F0F0F0Full; // nibbles x = (x | (x >> 4)) & 0x00FF00FF00FF00FFull; // octets x = (x | (x >> 8)) & 0x0000FFFF0000FFFFull; // halfwords x = (x | (x >> 16)) & 0x00000000FFFFFFFFull; // words return x; }
对于具有BMI2指令集的 x86架构,可能是最快的解决方案:
#include#include uint32_t calc (uint64_t a) { return _pext_u64(a, 0x5555555555555555ull) | _pext_u64(a, 0xaaaaaaaaaaaaaaaaull); }
这总共编译了5条指令.
如果你没有pext
并且你仍然希望比平凡的方式做得更好,那么这个提取可以表示为位移动的对数(如果你用长度来概括它):
// OR adjacent bits, destroys the odd bits but it doesn't matter x = (x | (x >> 1)) & rep8(0x55); // gather the even bits with delta swaps x = bitmove(x, rep8(0x44), 1); // make pairs x = bitmove(x, rep8(0x30), 2); // make nibbles x = bitmove(x, rep4(0x0F00), 4); // make bytes x = bitmove(x, rep2(0x00FF0000), 8); // make words res = (uint32_t)(x | (x >> 16)); // final step is simpler
附:
bitmove(x, mask, step) { return x | ((x & mask) >> step); }
repk
就是这样我可以编写更短的常量.rep8(0x44) = 0x4444444444444444
等等
此外,如果你也有pext
,你可以只用其中的一个做到这一点,这可能是速度更快,至少短:
_pext_u64(x | (x >> 1), rep8(0x55));
好的,让我们把它变得更加hacky(可能是马车):
uint64_t x; uint64_t even_bits = x & 0xAAAAAAAAAAAAAAAAull; uint64_t odd_bits = x & 0x5555555555555555ull;
现在,我原来的解决方案是这样的:
// wrong even_bits >> 1; unsigned int solution = even_bits | odd_bits;
然而,正如Jack Aidley指出的那样,虽然这会将这些位对齐,但它并没有从中间移除空间!
值得庆幸的是,我们可以使用BMI2指令集中非常有用的_pext
指令.
u64 _pext_u64(u64 a, u64 m)
- 将掩码m指定的相应位位置的a中的位提取到dst中的连续低位; dst中的剩余高位设置为零.
solution = _pext_u64(solution, odd_bits);
或者,您可以只使用提供的掩码(将其分成两个连续的32位数字)在原始数字上使用两次,而不是使用&
和>>
分离这些位,_pext
然后简单地or
使用结果.
但是,如果您无法访问BMI2,我很确定删除间隙仍会涉及循环; 或许比你原来的想法更简单一点.
与LUT方法相比略有改进(4次查找而不是8次):
按位计算或清除每隔一位.然后将字节对的位交织在一起以产生四个字节.最后,通过256个条目的查找表重新排序四个字节中的位(映射在四字上):
Q= (Q | (Q << 1)) & 0xAAAAAAAAAAAAL; // OR in pairs Q|= Q >> 9; // Intertwine 4 words into 4 bytes B0= LUT[B0]; B1= LUT[B2]; B2= LUT[B4]; B3= LUT[B6]; // Rearrange bits in bytes
在硬化之后,困难的部分似乎就是打包.oring由以下人员完成:
ored = (x | (x>>1)) & 0x5555555555555555;
(假设int
s 足够大,所以我们不必使用后缀).然后我们可以按步骤打包,然后先将它们打包为2×2,4×4等:
pack2 = ((ored*3) >> 1) & 0x333333333333; pack4 = ((ored*5) >> 2) & 0x0F0F0F0F0F0F; pack8 = ((ored*17) >> 4) & 0x00FF00FF00FF; pac16 = ((ored*257) >> 8) & 0x0000FFFF0000FFFF; pack32 = ((ored*65537) >> 16) & 0xFFFFFFFF; // (or cast to uint32_t instead of the final & 0xFFF...)
包装中发生的事情是,通过乘以我们将数据与移位的数据相结合.在你的例子中,我们将在第一次乘法中(我表示来自ored
as o
和另一个0
(来自原始数据)的掩码中的零):
o1o0o1o1 x 11 ---------- o1o0o1o1 o1o0o1o1 ---------- o11001111 ^^ ^^ o10oo11o < these are bits we want to keep.
我们也可以通过oring做到这一点:
ored = (ored | (ored>>1)) & 0x3333333333333333; ored = (ored | (ored>>2)) & 0x0F0F0F0F0F0F0F0F; ored = (ored | (ored>>4)) & 0x00FF00FF00FF00FF; ored = (ored | (ored>>8)) & 0x0000FFFF0000FFFF; ored = (ored | (ored>>16)) & 0xFFFFFFFF; // ored = ((uint32_t)ored | (uint32_t)(ored>>16)); // helps some compilers make better code, esp. on x86