3

检查一个数字中是否有数字“0”的最快方法是什么？

我需要开发一种快速方法，因为我必须在 20 美元以下的时间内对接近 10 ^ 9 美元的数字执行这些检查。

将其转换为字符串后搜索零会起作用吗？

4

5 回答 5

14

除以 $2$ 的幂以外的数字，无论数字是多少，都将执行相同数量的操作。因此，不要重复将 $x$ 除以 $10$ 并针对 $0$ 测试每个余数，而是考虑重复将 $x$ 除以 $10^6$（例如）并根据 $[0, 10^6) 上的查找表测试每个余数美元。如果余数包含内部零，则查找表应该说“是”，如果它不包含零，则应该说“否”，如果余数只有初始零，则应该说“可能”（在这种情况下，检查 $x$ 当前是否为非零并返回“是”或“否”相应）。

于 2012-04-05T17:00:35.633 回答
1

二进制零：如果有零位，(~x) 将不为零。我的猜测是你不关心二进制数。

如果您的数据以字符串开头，请保持这种状态。如果不是，请不要转换为字符串然后检查。到字符串的转换比检测零位所需的工作更多。这可能是特定于语言的。在 c 或汇编中，转换将比您自己的检测算法慢。

例如，如果您将基数为 10 的数字存储为整数（如在 c 中），您可以创建一个包含 1000 个条目的查找表。Lookup[100] = 1, Lookup[123] = 0 等。然后您必须将输入数字除以 1000 而不是 10。余数是查找索引。这可能比除以 10 快 3 倍。一个小的查找表将适合缓存。表太大，由于 ram 太慢，您将获得性能损失。在 c 中，无符号整数可能比有符号整数除法更快，因为优化器可能会采取一些捷径。

最后，为此考虑多个线程。

于 2012-04-05T22:43:05.623 回答
1

如果您可以编写汇编程序或强制编译器进行整数除法，请重复执行整数除法 $10$，直到余数为 $0$ 或被除数为 $0$。如果是余数，则有一个“$0$”数字。如果是股息，则没有“$0$”数字。

于 2012-04-05T15:33:50.137 回答
0

这是一些 Mathematica 代码，它使数字中的每个数字除一。

n = 34560116; d = IntegerLength[n]; m = 0; x = 1;  
While[d >= x, If[m == (k = Mod[n, 10^(x++)]), Break[], m = k]];
If[d >= x, Print["First zero found at: ", 10^(x - 2)]];

First zero found at: 1000
于 2012-04-10T23:15:46.697 回答
0

我需要开发一种快速方法，因为我必须在 20 秒内对接近 109 个数字执行这些检查。

啊，编程问题。

将其转换为字符串后搜索零会起作用吗？

如果您提供给输入的所有内容都是在其自己的行上没有前导或尾随零的数字，那么 /0/ 就可以了。但是，是的，字符串将是最快的。对于混合中包含零或非数字的更复杂的表示，那么您将使用这个正则表达式来表示整数：

/^[1-9]+0[0-9]*$|^0$/

这需要一个具有非前导零的数字，或者是数字零。它还假设整数。

$ cat numbers
    375
    391
    940
    493
    566
    804
    800
    453
    726
    527
    428
    77
    984
    510
    795
    077
    0

    $ egrep '^[1-9]+0[0-9]*$|^0$' numbers
940
804
800
510
0

如果十进制数字是固定宽度的，那么它们可能会更具挑战性。如果不是，则在两个括号中添加一个句点就足够了，除非您的小数以“0.nnn”而不是“.nnn”开头。告诉我你的号码，我会给你正确的解决方法。

于 2012-04-05T20:40:52.987 回答