计算 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

假设 'random' 分布，第一个非零位将在高 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 使用 bsrq 指令实现每个 __builtin_clzll - 位扫描反向，即最高有效位位置 - 结合 xor, (msb ^ 63) 或 sub、(63 - msb)，将其转换为前导零计数。 gcc 可能会使用正确的 -march=（体系结构）选项生成 lzcnt 指令。

编辑：其他人指出 'distribution' 在这种情况下不相关，因为无论如何都需要测试 HI uint64_t。

Answer 2

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

Answer 3

只要 gcc 支持，Yakk 的答案就适用于所有类型的目标目标的 128 位整数。但是，请注意，在 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 指令，很好定义为零输入（它 returns 64），与 gcc 的 __builtin_clzll() 相反。三元运算符编译为 cmove 指令。

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

Counting the number of leading zeros in a 128-bit integer

c++

gcc

sse

bit-manipulation