3

我需要计算一个数字中的小数位数（例如：4 表示 1002）。我想以 O(1) 的时间复杂度执行此操作，因为代码应在大量数字上进行迭代，从而显着节省 cpu 时间。

我想出了两个解决方案：

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

问题：log10 是 O(1) 解决方案吗？我在 x86 机器上使用 glibc 运行代码。这是如何在幕后实现的？并且，有没有更好的解决方案？

4

6 回答 6

2

假设无符号整数和 Intel 平台（BSR 指令），您可以获得最高设置位。然后你知道：

2^i <= num < 2^(i+1)

i的最高设置位在哪里num。如此简单的查找表（i由

但是你真的使用这么大的数字需要这种不可移植的优化吗？

于 2012-05-23T15:56:17.333 回答
2

这看起来像是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 次操作。

于 2012-05-23T15:56:53.460 回答
1

我不会使用 log 来解决这个问题，因为它涉及双重计算，并且可能会比除以 10 的周期慢。牺牲一些内存和一些时间进行预计算，您可能会在一些整数指令中得到答案。例如，预先计算最多 10 000 的数字的位数：

int num_digits[10000];
for (int i = 0; i < 10000; ++i) {
  if (i < 10) {
    num_digits[i] = 1;
  } else if (i < 100) {
    num_digits[i] = 2;
  } else if (i < 1000) {
    num_digits[i] = 3;
  }
}

现在这里是你如何在大约 4 个整数运算中得到一个数字的位数：

int get(int n) {
  int result = 0;
  while (n > 10000) {
    result += 4;
    n /= 10000;
  }
  return result + num_digits[n];
}

这当然会为了速度而牺牲记忆，但正如我们所知，没有免费的午餐。

于 2012-05-23T15:48:37.590 回答
1

您需要做的就是：

1 + floor(log(N)/log(10))

（这不适用于 0。如果输入浮点数，它将返回小数点左侧的位数，并且仅适用于大于 0.1 的浮点数。）

几乎可以肯定有一条 FPU 指令，不是在原始 x86 中，而是在您的 CPU 支持的扩展中。log(N)您可以通过在循环中多次评估来测试这一点。

这是假设您将数字存储为 int 或 float。如果您使用某个库将数字存储为可变长度数组，如果库预先计算数组的长度（正确的做法），这是 O(1) 时间，否则是 O(N) 时间（坏库）。

与所有浮动操作一样，如果您真的接近过渡 99-100、999-1000 等，则准确性可能是一个问题。正如史蒂夫杰索普在此答案的评论中指出的那样，您可以根据到所需的语义。我什至可以说你有一点余地：你可以从 N 中添加/减去 0.1 之类的东西，如果这些转换数字以某种方式失败（没有那么多数字：你可以自己手动测试它们，看看这是否是必要的）。

于 2012-05-23T15:39:39.387 回答
-1 
import java.util.*;
import java.lang.*;
class Main
{
  public static void main (String args[])
  {
    Scanner in = new Scanner (System.in);
    System.out.print ("Enter the number : ");
    int n = in.nextInt ();
    double ans = 1 + Math.floor (Math.log (n) / Math.log (10));
    int intANS = (int) (ans);
    System.out.println ("No. of digits in " + n + " = " + intANS);
  }
}

// 在 JAVA 中

于 2020-07-07T15:04:41.670 回答
-2 
class NumberOfDigits{

    public static void main(String ar[]){
        int n=99;
        System.out.println(""+(1+Math.floor(Math.log10(n))));
    }
}
于 2020-07-16T09:25:13.757 回答