计算128位整数中前导零的数量 [英] Counting the number of leading zeros in a 128-bit integer

问题描述

如何有效地计算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位整数。 / p>

有没有128位整数的类似，高效的内置功能？ div>

  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：文档说结果是未定义的，但它只是未指定或未定义？

How can I count the number of leading zeros in a 128-bit integer (uint128_t) efficiently?

I know GCC's built-in functions:

• __builtin_clz, __builtin_clzl, __builtin_clzll
• __builtin_ffs, __builtin_ffsl, __builtin_ffsll

However, these functions only work with 32- and 64-bit integers.

I also found some SSE instructions:

• __lzcnt16, __lzcnt, __lzcnt64

As you may guess, these only work with 16-, 32- and 64-bit integers.

Is there any similar, efficient built-in functionality for 128-bit integers?

解决方案

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

this is a branch free variant. Note that more work is done than in the branchy solution, and in practice the branching will probably be predictable.

It also relies on __builtin_clzll not crashing when fed 0: the docs say the result is undefined, but is it just unspecified or undefined?

这篇关于计算128位整数中前导零的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！