c++ - 计算 128 位整数中前导零的数量

Question

如何有效地计算 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 位整数是否有任何类似的、高效的内置功能？

Answer 1

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];
}

这是一个无分支的变体。请注意，与分支解决方案相比，完成了更多的工作，并且在实践中，分支可能是可预测的。

它还依赖于 __builtin_clzll 在输入 0 时不会崩溃:文档说结果未定义，但它只是未指定还是未定义？