在 O(1) 中计算数字中的位数 [英] Counting number of digits in a number in O(1)

问题描述

我需要计算一个数字中的小数位数(例如:1002 为 4).我想以 O(1) 时间复杂度执行此操作，因为代码将在大量数字上迭代，从而显着节省 CPU 时间.

I need to count the number of decimal digits in a number(for ex: 4 for 1002). I want to do this in O(1) time complexity as the code shall be iterated over huge set of numbers, significantly saving cpu time.

我想出了两个解决方案:

I have come up with two solutions:

1. 循环除以 10，直到数字变为零.循环数是答案.但是，显然是 O(n) 时间.
2. log_base_10(num) + 1

问题:log10 是 O(1) 解决方案吗?我在 x86 机器上使用 glibc 运行代码.这是如何在幕后实施的?并且，是否有更好的解决方案?

The question: Is log10 an O(1) solution? I am running the code with glibc on an x86 machine. How is that implemented under the hood? and, are there better solutions for this?

推荐答案

这看起来像是 Bit Twiddling Hacks

unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of 
int r;          // result goes here

r = (v >= 1000000000) ? 9 : (v >= 100000000) ? 8 : (v >= 10000000) ? 7 : 
    (v >= 1000000) ? 6 : (v >= 100000) ? 5 : (v >= 10000) ? 4 : 
    (v >= 1000) ? 3 : (v >= 100) ? 2 : (v >= 10) ? 1 : 0;

"当输入均匀分布在 32 位值上时，此方法效果很好，因为 76% 的输入被第一次比较捕获，21% 被第二次比较捕获，2% 被第三次捕获，并且依此类推(每次比较将剩余的减少 90%).因此，平均需要的操作少于 2.6 次."

"This method works well when the input is uniformly distributed over 32-bit values because 76% of the inputs are caught by the first compare, 21% are caught by the second compare, 2% are caught by the third, and so on (chopping the remaining down by 90% with each comparision). As a result, less than 2.6 operations are needed on average."

这篇关于在 O(1) 中计算数字中的位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！