对于所有2次方的数字，是否有快速计算log2的算法？
对于所有2次方的数字，是否有快速计算log2的算法？
提问于 2014-06-20 13:30:26
是否有任何快速算法来计算所有幂为2的数字的log2，例如：
log2(1), log2(2), log2(4), log2(1024), log2(4096)...我正在考虑使用它来实现位集迭代。
回答 2
Stack Overflow用户
回答已采纳
发布于 2014-06-20 13:47:14
假设您知道数字必须是2的幂，那么在二进制中，在1后面有n个0，其中n是您要寻找的数字。
如果您使用gcc或clang，您可以使用内建函数。
-内置函数: int __builtin_ctz (无符号int x) 返回x中的尾随0位数，从最小有效位位置开始。如果x为0，则结果未定义。
对于纯C实现，它已经得到了回答
Stack Overflow用户
发布于 2014-06-20 14:58:03
另外三种理论上可能是有效的算法，除了已经给出的算法或链接的算法。N是位数，N= 2^n
- 大LUT:一次查找
- 简单二进制搜索: log2(n)比较
- K位LUT的LUTN %k:一个模块，一个查找(32位k=37和64位数字67 )
实际上，#1对于小n很好，在某些硬件上#2可能是最快的(一些没有快速乘法的东西)，但是代码看起来很难看。#3在真正的机器上可能永远都比不上DeBruijn，但是它的运算量更少。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/24328489
复制相关文章
相似问题
腾讯云开发者
