64位整数中OR相邻位的有效方法

我想要做的是采用由位对组成的64位无符号整数,如果相应对中的两个位都为0,则从中创建一个包含0的32位整数,否则为1.换句话说,转换看起来像这样的东西:

01 00 10 11

进入看起来像这样的东西

1 0 1 1

两个明显的解决方案是每个字节的强力循环或查找表,然后执行8次查找并将它们组合成OR和位移的最终结果但我确信应该有一种有效的方法来进行比特纠缠.我将在C++中为64位整数执行此操作,但如果有人知道为更短的整数执行此操作的有效方法,我确信我可以弄清楚如何扩展它.

1> Blastfurnace..：

---

这是一个可移植的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;
}

---

尼斯.您也可以删除至少一个原始位掩码,因为在最后不收集的位上发生的事情并不重要.

---

因为我们是去交错的,所以我们不需要用0x555和0xAAA进行掩码......只需执行`(n |(n >> 1))`并且去交错将消除不需要的位.这应该至少削减两条指令.

2> Nils Pipenbr..：

---

对于具有BMI2指令集的 x86架构,可能是最快的解决方案:

#include 
#include 

uint32_t calc (uint64_t a)
{
   return _pext_u64(a, 0x5555555555555555ull) |
          _pext_u64(a, 0xaaaaaaaaaaaaaaaaull);
}

这总共编译了5条指令.

---

@Nils:可能更快:`_pext_u64(a | a >> 1,0b01010101 ...)`.英特尔Haswell的吞吐量更高,延迟相同.(`pext/pext/OR`是5个周期的延迟,因为pext是3个周期的延迟,只能在port1上运行.所以两个结果都不会准备好,直到'a`准备就绪后的第4个周期,此时`OR `需要一个周期.)吞吐量是每2个周期一个,在port1上为`pext`瓶颈.`shr /或/ pext`也是5c:shr(1) - >或(1) - > pext(3)dep链,但是shr可以在port0/6上运行,`或`可以在p0/1/5上运行/ 6.因此吞吐量=每个周期一个,在port1上为pext瓶颈.

---

下一个问题:对于没有它的CPU,`pext`的最佳实现是什么？

3> harold..：

---

如果你没有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));

4> Bartek Banac..：

---

好的,让我们把它变得更加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,我很确定删除间隙仍会涉及循环; 或许比你原来的想法更简单一点.

5> Yves Daoust..：

---

与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

6> skyking..：

---

在硬化之后,困难的部分似乎就是打包.oring由以下人员完成:

ored  = (x | (x>>1)) & 0x5555555555555555;

(假设ints 足够大,所以我们不必使用后缀).然后我们可以按步骤打包,然后先将它们打包为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...)

包装中发生的事情是,通过乘以我们将数据与移位的数据相结合.在你的例子中,我们将在第一次乘法中(我表示来自oredas 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