user1494080 - 29 days ago 10

C++ Question

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

`uint128_t`

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?

Answer

```
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?

Source (Stackoverflow)

Comments