如何通过c程序在O(1)时间内计算log n(base r )
1) 时间方法来计算以 2 为底的 n 的对数，我也无法找到 O(1) 方法来查找 n 的对数
即使您可以确定 O( ，这将非常感谢。 我遇到的链接是这个 http://geeksforgeeks.org/?p=10879 （请阅读相关评论）。 他们说要计算数字前面的零的数量，但是如何在 O(1) 时间内完成...... 我再次求助于这个网站，其链接是如何使用 C 查找数字中零的前导数 但 O(1) 对我来说是个大问题。 任何帮助将不胜感激。
i am unable to find the O(1) way to find log of n with any base
even if you can determine O(1) time way to calculate log of n with base 2 ,it would be thank full.
the link which i encountered is this http://geeksforgeeks.org/?p=10879 (please read the comments on that).
they are saying to calculate the number of zero's in front of a number but how that can be done in O(1) time...
again i took help of this site whose link is How To Find The Leading Number Of Zero's In a Number using C
but O(1) is big issue for me.
any help would be highly appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
对于任意大的数，你不能在 O(1) 内做到这一点。您至少需要 O(log(n)) 才能查看该数字的二进制表示一次。
如果对 n 的值进行限制（例如 64 位），那么一切都可以在 O(1) 内完成！在这种情况下，O 表示法没有任何实际意义。
You cannot do that in O(1) for arbitrarily large numbers. You need at least O(log(n)) to look at the binary representation of the number once.
If you put a bound on the value of n (e.g. 64 bits), then everything is doable in O(1)! O-notation will not make any real sense in that case.
如果我理解正确的话，你只想计算以 b 为底的数字 n 的对数。在这种情况下，请使用
log()函数：If I've undertood correctly, you just want to calculate the log of a number n in base b. In that case, use the
log()function:根据您的 CPU 和编译器，您可能能够以 O(1) 的时间复杂度获得 log2 的整数。请参阅此此的答案例如问题。查找二进制数的最左边位与 log2 相同。
Depending on your CPU and your compiler you may be able to get log2 in O(1) for integer numbers. See the answers of this this question for example. Finding the left most bit of a binary number is the same as log2.