对64位整数中相邻位进行OR运算的有效方法
对64位整数中相邻位进行OR运算的有效方法
提问于 2015-12-08 19:29:41
我想做的是获取一个由位对组成的64位无符号整数，如果对应的位对中的两个位都是0，则从它创建一个包含0的32位整数，否则为1。换句话说，转换看起来像这样的东西：
01 00 10 11变成像这样的东西
1 0 1 1两个显而易见的解决方案要么是暴力强制循环，要么是每个字节的查找表，然后执行八次查找，并使用or和位移位将它们组合成最终结果，但我相信应该有一种有效的方法来处理这一点。我将在C++中对64位整数执行此操作，但如果有人知道对较短整数执行此操作的有效方法，我相信我可以想出如何将其放大。
回答 3
Stack Overflow用户
发布于 2015-12-08 20:02:17
使用BMI2 instruction set的x86体系结构可能是最快的解决方案
#include <stdint.h>
#include <x86intrin.h>
uint32_t calc (uint64_t a)
{
return _pext_u64(a, 0x5555555555555555ull) |
_pext_u64(a, 0xaaaaaaaaaaaaaaaaull);
}这将编译为总共5条指令。
Stack Overflow用户
发布于 2015-12-08 21:40:16
对LUT方法稍有改进(4次查找而不是8次)：
计算逐位or，并清除每隔一位。然后将成对字节的比特交织在一起以产生四个字节。最后，通过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 bytesStack Overflow用户
发布于 2015-12-08 22:52:02
困难的部分似乎是在be之后打包比特。The是通过以下方式完成的：
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...)打包过程中发生的事情是，通过乘法，我们将数据与移位的数据组合在一起。在您的示例中，我们将在第一次乘法中使用(我将ored中的掩码中的零表示为o，另一个0 (来自原始数据))：
o1o0o1o1
x 11
----------
o1o0o1o1
o1o0o1o1
----------
o11001111
^^ ^^
o10oo11o < these are bits we want to keep.我们也可以通过done做到这一点：
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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/34154745
复制相关文章
相似问题