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

最佳答案

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 时不会崩溃:文档说结果未定义，但它只是未指定或未定义？

关于c++ - 计算 128 位整数中前导零的数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28423405/