对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位整数执行此操作，但如果有人知道对较短整数执行此操作的有效方法，我相信我可以想出如何将其放大。
回答 5
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:02:16
如果你没有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));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 bytes页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/34154745
复制相关文章
相似问题
腾讯云开发者
