查找正整数位数的最佳方法是什么？
我发现了这 3 种基本方法：
转换为字符串
String s = new Integer(t).toString();
int len = s.length();
for 循环
for(long long int temp = number; temp >= 1;)
{
temp/=10;
decimalPlaces++;
}
对数计算
digits = floor( log10( number ) ) + 1;
您可以在大多数语言中计算 log10(x) = ln(x) / ln(10)。
首先我认为字符串方法是最脏的方法，但我越想越觉得它是最快的方法。或者是吗？
总是有这个方法：
n = 1;
if ( i >= 100000000 ) { n += 8; i /= 100000000; }
if ( i >= 10000 ) { n += 4; i /= 10000; }
if ( i >= 100 ) { n += 2; i /= 100; }
if ( i >= 10 ) { n += 1; }
那么正确的答案是测量它 - 但您应该能够猜测转换字符串并通过它们寻找结束标记所涉及的 CPU 步骤数
然后想想你的处理器可以执行多少 FPU 操作/秒，以及计算单个日志有多容易。
编辑：在星期一早上浪费更多时间:-)
String s = new Integer(t).toString();
int len = s.length();
高级语言的问题之一是猜测系统在看似简单的语句背后做了多少工作。强制性乔尔链接
该语句涉及为字符串分配内存，可能还包括字符串的几个临时副本。它必须解析整数并将其数字复制到字符串中，如果数字很大，可能必须重新分配和移动现有内存。它可能需要检查一堆区域设置来决定你的国家使用“，”还是“。”，它可能需要进行一堆 unicode 转换。
然后查找长度必须扫描整个字符串，再次考虑 unicode 和任何本地特定设置，例如 - 你是使用右->左语言吗？
或者：
digits = floor( log10( number ) ) + 1;
仅仅因为这对你来说在纸上更难做并不意味着对计算机来说很难！事实上，高性能计算中的一条好规则似乎是——如果某件事对人类来说很难（流体动力学、3D 渲染），那么对计算机来说就很容易，如果对人类来说很容易（面部识别、检测语音嘈杂的房间）电脑很难！
您通常可以假设内置数学函数 log/sin/cos 等 - 50 年来一直是计算机设计的重要组成部分。因此，即使它们不直接映射到 FPU 中的硬件功能，您也可以打赌，替代实现非常有效。
我不知道，答案可能会有所不同，具体取决于您个人语言的实现方式。
所以，压力测试吧！实施所有三个解决方案。运行它们从 1 到 1,000,000（或代表解决方案将要运行的数字的其他一些庞大的数字集），并计算它们每个需要多长时间。
让您的解决方案相互竞争，让他们一决胜负。就像智力角斗士一样。三种算法进入！一种算法离开！
这个算法也可能很好，假设：
我们不知道数字边界
var num = 123456789L;
var len = 0;
var tmp = 1L;
while(tmp < num)
{
len++;
tmp = (tmp << 3) + (tmp << 1);
}
该算法的速度应该与提供的 for-loop (2) 相当，但由于（2 位移位，加减法，而不是除法）要快一些。
至于 Log10 算法，它只会给你一个近似的答案（接近真实，但仍然），因为计算 Log 函数的解析公式有无限循环，无法精确计算Wiki。
测试条件
结果
数字：[1,10]，
不。运行次数：1,000,000
随机样本：8777509,40442298,477894,329950,513,91751410,313,3159,131309,2
结果：7,8,6,6,3,8,3,4,6,1
转换为字符串：724 毫秒
对数计算：349ms
DIV 10 迭代：229 毫秒
手动调节：136ms
注意：作者避免对超过 10 位的数字做出任何结论。
脚本
package {
import flash.display.MovieClip;
import flash.utils.getTimer;
/**
* @author Daniel
*/
public class Digits extends MovieClip {
private const NUMBERS : uint = 1000000;
private const DIGITS : uint = 10;
private var numbers : Array;
private var digits : Array;
public function Digits() {
// ************* NUMBERS *************
numbers = [];
for (var i : int = 0; i < NUMBERS; i++) {
var number : Number = Math.floor(Math.pow(10, Math.random()*DIGITS));
numbers.push(number);
}
trace('Max digits: ' + DIGITS + ', count of numbers: ' + NUMBERS);
trace('sample: ' + numbers.slice(0, 10));
// ************* CONVERSION TO STRING *************
digits = [];
var time : Number = getTimer();
for (var i : int = 0; i < numbers.length; i++) {
digits.push(String(numbers[i]).length);
}
trace('\nCONVERSION TO STRING - time: ' + (getTimer() - time));
trace('sample: ' + digits.slice(0, 10));
// ************* LOGARITMIC CALCULATION *************
digits = [];
time = getTimer();
for (var i : int = 0; i < numbers.length; i++) {
digits.push(Math.floor( Math.log( numbers[i] ) / Math.log(10) ) + 1);
}
trace('\nLOGARITMIC CALCULATION - time: ' + (getTimer() - time));
trace('sample: ' + digits.slice(0, 10));
// ************* DIV 10 ITERATION *************
digits = [];
time = getTimer();
var digit : uint = 0;
for (var i : int = 0; i < numbers.length; i++) {
digit = 0;
for(var temp : Number = numbers[i]; temp >= 1;)
{
temp/=10;
digit++;
}
digits.push(digit);
}
trace('\nDIV 10 ITERATION - time: ' + (getTimer() - time));
trace('sample: ' + digits.slice(0, 10));
// ************* MANUAL CONDITIONING *************
digits = [];
time = getTimer();
var digit : uint;
for (var i : int = 0; i < numbers.length; i++) {
var number : Number = numbers[i];
if (number < 10) digit = 1;
else if (number < 100) digit = 2;
else if (number < 1000) digit = 3;
else if (number < 10000) digit = 4;
else if (number < 100000) digit = 5;
else if (number < 1000000) digit = 6;
else if (number < 10000000) digit = 7;
else if (number < 100000000) digit = 8;
else if (number < 1000000000) digit = 9;
else if (number < 10000000000) digit = 10;
digits.push(digit);
}
trace('\nMANUAL CONDITIONING: ' + (getTimer() - time));
trace('sample: ' + digits.slice(0, 10));
}
}
}
在您使用的任何编程语言中使用最简单的解决方案。我想不出在任何（有用的）程序中计算整数中的数字会成为瓶颈的情况。
char buffer[32];
int length = sprintf(buffer, "%ld", (long)123456789);
len = (length . show) 123456789
length = String(123456789).length;
$length = strlen(123456789);
length = Len(str(123456789)) - 1
转换为字符串：这将必须遍历每个数字，找到映射到当前数字的字符，将一个字符添加到字符集合中。然后获取生成的 String 对象的长度。将在 O(n) 中运行 n=#digits。
for-loop：将执行 2 个数学运算：将数字除以 10 并增加一个计数器。将在 O(n) 中运行 n=#digits。
对数：将调用 log10 和 floor，然后加 1。看起来像 O(1)，但我不确定 log10 或 floor 函数有多快。由于缺乏使用，我对这类事情的了解已经萎缩，因此这些功能可能隐藏着复杂性。
所以我想它归结为：查找数字映射是否比多个数学运算或发生的任何事情更快log10？答案可能会有所不同。可能存在字符映射更快的平台，而其他计算速度更快的平台。另外要记住的是，第一个方法将创建一个新的 String 对象，该对象仅用于获取长度。这可能会比其他两种方法使用更多的内存，但这可能或可能不重要。
您显然可以从竞争中消除方法 1，因为它使用的 atoi/toString 算法将类似于方法 2。
方法 3 的速度取决于代码是否正在为指令集包含 log base 10 的系统编译。
对于非常大的整数，log 方法要快得多。例如，对于一个 2491327 位的数字（第 11920928 个斐波那契数，如果你关心的话），Python 需要几分钟来执行除以 10 算法，而毫秒来执行1+floor(log(n,10)).
import math
def numdigits(n):
return ( int(math.floor(math.log10(n))) + 1 )
关于您提出的“确定在给定基数中表示给定数字所需的位数”的三种方法，实际上我不喜欢其中任何一种；我更喜欢下面给出的方法。
关于你的方法＃1（字符串）：任何涉及在字符串和数字之间来回转换的东西通常都非常慢。
Re your method #2 (temp/=10): 这是致命的缺陷，因为它假定 x/10 总是意味着“x 除以 10”。但是在很多编程语言（例如：C、C++）中，如果“x”是整数类型，那么“x/10”表示“整数除法”，这和浮点除法不是一回事，它引入了每次迭代的舍入误差，它们会在递归公式中累积，例如您的解决方案 #2 使用。
关于您的方法＃3（日志）：它对于大数（至少在 C 语言中，可能还有其他语言中）有问题，因为浮点数据类型往往不如 64 位整数那么精确。
因此，我不喜欢所有这 3 种方法：#1 有效但速度很慢，#2 坏了，#3 对于大量数据来说是错误的。相反，我更喜欢这个，它适用于从 0 到大约 18.44 quintillion 的数字：
unsigned NumberOfDigits (uint64_t Number, unsigned Base)
{
unsigned Digits = 1;
uint64_t Power = 1;
while ( Number / Power >= Base )
{
++Digits;
Power *= Base;
}
return Digits;
}
把事情简单化：
long long int a = 223452355415634664;
int x;
for (x = 1; a >= 10; x++)
{
a = a / 10;
}
printf("%d", x);
您可以使用递归解决方案而不是循环，但有些相似：
@tailrec
def digits (i: Long, carry: Int=1) : Int = if (i < 10) carry else digits (i/10, carry+1)
digits (8345012978643L)
使用 long 时，情况可能会发生变化 - 针对不同的算法独立测量小数和长数，并根据您的典型输入选择合适的数。:)
当然，没有什么比开关更重要了：
switch (x) {
case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: return 1;
case 10: case 11: // ...
case 99: return 2;
case 100: // you get the point :)
default: return 10; // switch only over int
}
除了普通数组：
int [] size = {1,1,1,1,1,1,1,1,1,2,2,2,2,2,... };
int x = 234561798;
return size [x];
有些人会告诉你优化代码大小，但是你知道，过早的优化......
这是 Swift 4 中的测量值。
算法代码：
extension Int {
var numberOfDigits0: Int {
var currentNumber = self
var n = 1
if (currentNumber >= 100000000) {
n += 8
currentNumber /= 100000000
}
if (currentNumber >= 10000) {
n += 4
currentNumber /= 10000
}
if (currentNumber >= 100) {
n += 2
currentNumber /= 100
}
if (currentNumber >= 10) {
n += 1
}
return n
}
var numberOfDigits1: Int {
return String(self).count
}
var numberOfDigits2: Int {
var n = 1
var currentNumber = self
while currentNumber > 9 {
n += 1
currentNumber /= 10
}
return n
}
}
测量代码：
var timeInterval0 = Date()
for i in 0...10000 {
i.numberOfDigits0
}
print("timeInterval0: \(Date().timeIntervalSince(timeInterval0))")
var timeInterval1 = Date()
for i in 0...10000 {
i.numberOfDigits1
}
print("timeInterval1: \(Date().timeIntervalSince(timeInterval1))")
var timeInterval2 = Date()
for i in 0...10000 {
i.numberOfDigits2
}
print("timeInterval2: \(Date().timeIntervalSince(timeInterval2))")
输出
时间间隔0：1.92149806022644
时间间隔1：0.557608008384705
时间间隔2：2.83262193202972
在此测量基础上，字符串转换是 Swift 语言的最佳选择。
看到@daniel.sedlacek 结果后我很好奇，所以我使用 Swift 对超过 10 位的数字进行了一些测试。我在操场上运行了以下脚本。
let base = [Double(100090000000), Double(100050000), Double(100050000), Double(100000200)]
var rar = [Double]()
for i in 1...10 {
for d in base {
let v = d*Double(arc4random_uniform(UInt32(1000000000)))
rar.append(v*Double(arc4random_uniform(UInt32(1000000000))))
rar.append(Double(1)*pow(1,Double(i)))
}
}
print(rar)
var timeInterval = NSDate().timeIntervalSince1970
for d in rar {
floor(log10(d))
}
var newTimeInterval = NSDate().timeIntervalSince1970
print(newTimeInterval-timeInterval)
timeInterval = NSDate().timeIntervalSince1970
for d in rar {
var c = d
while c > 10 {
c = c/10
}
}
newTimeInterval = NSDate().timeIntervalSince1970
print(newTimeInterval-timeInterval)
80 个元素的结果
0.105069875717163 for floor(log10(x))
0.867973804473877 for div 10 次迭代
log(x,n)-mod(log(x,n),1)+1
其中 x 是底数，n 是数。
为许多已经提到的方法添加了一种方法。这个想法是在包含基于数据类型的整数范围的数组上使用binarySearch 。
Java Arrays 类的签名是：binarySearch(dataType[] array, dataType key)，如果它包含在数组中，则返回搜索键的索引；否则，。
插入点定义为将键插入数组的点。
下面是实现：digitsintbinarySearch
(-(insertion point) – 1)
static int [] digits = {9,99,999,9999,99999,999999,9999999,99999999,999999999,Integer.MAX_VALUE};
static int digitsCounter(int N)
{
int digitCount = Arrays.binarySearch(digits , N<0 ? -N:N);
return 1 + (digitCount < 0 ? ~digitCount : digitCount);
}
请注意，上述方法仅适用于：Integer.MIN_VALUE <= N<= Integer.MAX_VALUE，但可以通过向数组Long添加更多值轻松扩展数据类型。digits
例如，
I) 对于 N = 555，digitCount = Arrays.binarySearch(digits, 555) 返回-3(-(2)-1)，因为它不存在于数组中，但应该插入到29 和 99 之间的点，例如 [ 9、55、99]。
由于我们得到的索引是负数，我们需要对结果进行按位补码。最后，我们需要将结果加 1 以得到 number 的实际位数N。
在 Swift 5.x 中，您会得到整数中的位数，如下所示：
let nums = [1, 7892, 78, 92, 90]
for i in nums {
let ch = String(describing: i)
print(ch.count)
}
var digitCount = 0
for i in nums {
var tmp = i
while tmp >= 1 {
tmp /= 10
digitCount += 1
}
print(digitCount)
}
let numDigits num =
let num = abs(num)
let rec numDigitsInner num =
match num with
| num when num < 10 -> 1
| _ -> 1 + numDigitsInner (num / 10)
numDigitsInner num
F# 版本，不强制转换为字符串。