计算快速对数基数 2 上限

Question

什么是快速计算 (long int) ceiling(log_2(i)) 的方法，其中输入和输出是 64 位整数？有符号或无符号整数的解决方案是可以接受的。我怀疑最好的方法是类似于找到的方法 here ，但我不想自己尝试，而是想使用已经过良好测试的东西。通用解决方案适用于所有正值。

例如，2,3,4,5,6,7,8 的值为 1,2,2,3,3,3,3

编辑:到目前为止，最好的方法似乎是使用任意数量的快速现有的 bithacks 或寄存器方法来计算以 2 为底的整数/底对数(MSB 的位置)，如果输入不是，则添加一个2 的幂。对 2 的幂的快速按位检查是 (n&(n-1))。

编辑 2:关于整数对数和前导零方法的一个很好的来源是 Hacker's Delight 中的第 5-3 和 11-4 节。亨利·S·沃伦 (Henry S. Warren)。这是我发现的最完整的治疗方法。

编辑 3:这项技术看起来很有前途:https://stackoverflow.com/a/51351885/365478

编辑 4:C23 显然添加了 stdc_first_(leading/trailing)_(one/zero)

Answer 1

如果您可以限制自己使用 gcc，那么有一组内置函数可以返回前导零位的数量，并且可以用来做一些您想要做的事情:

int __builtin_clz (unsigned int x)
int __builtin_clzl (unsigned long)
int __builtin_clzll (unsigned long long)