user1494080 user1494080 - 1 year ago 83
C++ Question

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

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

) efficiently?

I know GCC's built-in functions:

  • __builtin_clz

  • __builtin_ffs

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

I also found some SSE instructions:

  • __lzcnt16

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?

Answer Source
inline int clz_u128 (uint128_t u) {
  uint64_t hi = u>>64;
  uint64_t lo = u;
  int retval[3]={
  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?

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download