如何计算O(1)中的二进制长度？
如何计算O(1)中的二进制长度？
提问于 2016-09-24 02:01:40
通常，我必须在std::string中将整数转换为二进制，然后使用std::string::size()方法来获取二进制数字的长度。
因此，100给出了"1100100“(长度为7)。
但这是一个O(n)算法(至少)，我正在编写一个性能密集型程序，需要大量的位计数。是否有任何算法可以让我们知道任何给定的二进制数的长度，而不必事先将该数字转换为std::string？谢谢。
回答 2
Stack Overflow用户
回答已采纳
发布于 2016-09-24 02:10:10
你正在计算一个二进制对数。在bit twiddling hacks page上描述了很多方法来实现它。
一种简单的方法是使用查找表。首先，在启动时做一个查找表：
LogTable256[0] = LogTable256[1] = 0;
for (int i = 2; i != 256; i++) {
LogTable256[i] = 1 + LogTable256[i / 2];
}
LogTable256[0] = -1; // if you want log(0) to return -1现在，您可以如下所示使用它：
if (tt = v >> 24) {
r = 24 + LogTable256[tt];
} else if (tt = v >> 16) {
r = 16 + LogTable256[tt];
} else if (tt = v >> 8) {
r = 8 + LogTable256[tt];
} else {
r = LogTable256[v];
}Stack Overflow用户
发布于 2016-09-24 02:11:31
这是我的一个线性答案，但这取决于log2()是如何在您的机器上实现的。
length = ceil(log2(number))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39671795
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号