计算128位整数中的前导零数。
如何有效地计算128位整数(uint128_t)中的前导零数？
我知道GCC的内置功能：
__builtin_clz，__builtin_clzl，__builtin_clzll__builtin_ffs，__builtin_ffsl，__builtin_ffsll
然而，这些函数只适用于32位和64位整数.
我还找到了一些SSE指令：
__lzcnt16，__lzcnt，__lzcnt64
正如您可能猜到的，这些只适用于16位、32位和64位整数。
对于128位整数是否有类似的、高效的内置功能？
回答 3
Stack Overflow用户
发布于 2015-02-10 14:14:48
inline int clz_u128 (uint128_t u) {
uint64_t hi = u>>64;
uint64_t lo = u;
int retval[3]={
__builtin_clzll(hi),
__builtin_clzll(lo)+64,
128
};
int idx = !hi + ((!lo)&(!hi));
return retval[idx];
}这是一个没有分支的变体。请注意，所做的工作比分支解决方案中的工作要多，而且在实践中，分支可能是可预测的。
当美联储设为0时，它也依赖于__builtin_clzll，而不是崩溃:文档说结果是未定义的，但它只是未指定的还是未定义的？
Stack Overflow用户
发布于 2015-02-10 04:53:33
假设一个“随机”分布，第一个非零位将在高64位，以一个压倒性的概率，所以这是有意义的测试这一半的第一。
查看为以下目的生成的代码：
/* inline */ int clz_u128 (uint128_t u)
{
unsigned long long hi, lo; /* (or uint64_t) */
int b = 128;
if ((hi = u >> 64) != 0) {
b = __builtin_clzll(hi);
}
else if ((lo = u & ~0ULL) != 0) {
b = __builtin_clzll(lo) + 64;
}
return b;
}我期望gcc使用__builtin_clzll指令--位扫描反向，即最重要的位位置--与xor，(msb ^ 63)，或sub，(63 - msb)一起实现每个xor，(msb ^ 63)，或sub，(63 - msb)，将其转化为前导零计数。gcc可能会用正确的lzcnt (体系结构)选项生成-march=指令。
编辑:其他人指出，在这种情况下，“分发”与此无关，因为HI uint64_t需要进行测试。
Stack Overflow用户
发布于 2016-11-10 13:23:15
只要gcc为目标支持128位整数，Yakk的答案就能很好地适用于各种目标。但是，请注意，在x86-64平台上，使用Intel Haswell处理器或更新版本，有一个更有效的解决方案：
#include <immintrin.h>
#include <stdint.h>
// tested with compiler options: gcc -O3 -Wall -m64 -mlzcnt
inline int lzcnt_u128 (unsigned __int128 u) {
uint64_t hi = u>>64;
uint64_t lo = u;
lo = (hi == 0) ? lo : -1ULL;
return _lzcnt_u64(hi) + _lzcnt_u64(lo);
}_lzcnt_u64内部编译(gcc 5.4)为lzcnt指令，该指令定义为零输入(返回64)，这与gcc的__builtin_clzll()相反。三元运算符编译为cmove指令。
https://stackoverflow.com/questions/28423405
复制相似问题
腾讯云开发者
