查找整数的位数

find一个正整数的数字的最佳方法是什么?

我发现了这3个基本的方法:

  • 转换为string

    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)。

首先,我认为string方法是最肮脏的方法,但我越想越多,我认为这是最快的方法。 还是呢?

总是有这个方法:

 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; } 

我不知道,根据你的个人语言如何实施,答案可能会有所不同。

所以,压力testing吧! 实施这三个解决scheme。 在1到100万的范围内(或其他一些庞大的数字代表解决scheme将运行的数字)以及每个时间需要多长时间来运行它们。

把你的解决scheme对彼此,让他们打出来。 像知识分子angular斗士一样。 三种algorithm进入! 一个algorithm离开!

那么正确的答案是衡量它 – 但是你应该能够猜测转换string所涉及的CPU步骤的数量,并通过它们查找结束标记

然后考虑一下您的处理器可以执行多less个FPU操作,以及计算单个日志有多容易。

编辑:星期一上午浪费更多的时间:-)

 String s = new Integer(t).toString(); int len = s.length(); 

高级语言的问题之一是猜测系统在幕后做了多less工作。 强制性的Joel链接

这个语句涉及为一个string分配内存,可能还会分配一个string的临时副本。 它必须parsing整数并将其数字复制到一个string中,如果数字很大,可能不得不重新分配和移动现有的内存。 它可能需要检查一堆语言环境设置,以确定您的国家是否使用“,”或“。”,它可能需要做一堆的Unicode转换。
然后find长度必须扫描整个string,再次考虑unicode和任何本地特定的设置,如 – 你在一个右 – >左语言?

或者:

 digits = floor( log10( number ) ) + 1; 

只是因为这会让你更难在纸上做并不意味着对电脑来说很难! 事实上,在高性能计算中,一个好的规则似乎就是 – 如果对于一个人来说(stream体动力学,三维渲染)是一件很难的事情,那么计算机很容易,而且对于一个人来说很容易(人脸识别,检测嘈杂的房间)电脑很难!

一般认为内build的math函数log / sin / cos等已经是计算机devise50年的重要组成部分。 所以,即使它们不直接映射到FPU中的硬件function,也可以相信替代实现非常高效。

假设:这个algorithm也可能是好的,

  • 数字是整数和二进制编码(<<操作便宜)
  • 我们不知道号码边界

      var num = 123456789L; var len = 0; var tmp = 1L; while(tmp < num) { len++; tmp = (tmp << 3) + (tmp << 1); } 

该algorithm应该具有与提供的for-loop(2)相当的速度,但是由于(2位移位,加法和减法而不是除法),速度要快一些。

至于Log10algorithm,只会给出近似的答案(即接近真实,但仍然),因为计算Log函数的parsing公式具有无限循环,不能精确计算Wiki 。

testing条件

  • 十进制数字系统
  • 正整数
  • 最多10位数字
  • 语言:ActionScript 3

结果

数字:[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

转换为STRING:724ms

LOGARITMIC计算:349ms

DIV 10 ITERATION:229ms

手动调节: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)); } } } 
  • 转换为string:这将不得不遍历每个数字,find映射到当前数字的字符,将字符添加到字符集合。 然后获取生成的String对象的长度。 将在O(n)中运行n =#个数字。

  • for-loop:将执行2次math运算:将数字除以10并递增计数器。 将在O(n)中运行n =#个数字。

  • 对数:将调用log10和floor,并添加1.看起来像O(1),但我不确定log10或floor函数有多快。 我对这种事情的了解已经萎缩,缺乏使用,所以这些function可能会隐藏起来

所以我想它归结为:查找数字映射比多个math运算或log10发生的任何事情? 答案可能会有所不同。 可能有一些平台的字符映射速度更快,其他的计算速度更快。 另外要记住的是,第一种方法将创build一个新的string对象,只为了获得长度的目的而存在。 这可能会比其他两种方法使用更多的内存,但它可能或可能不重要。

你明显可以从竞争中消除方法1,因为它使用的atoi / toStringalgorithm将类似于方法2。

方法3的速度取决于代码是否正在为其指令集包含日志库10的系统编译。

使用您使用的任何编程语言的最简单的解决scheme。 我想不出一个计数整数中的数字将成为任何(有用)程序的瓶颈的情况。

C,C ++:

 char buffer[32]; int length = sprintf(buffer, "%ld", (long)123456789); 

哈斯克尔:

 len = (length . show) 123456789 

JavaScript的:

 length = String(123456789).length; 

PHP:

 $length = strlen(123456789); 

Visual Basic(未经testing):

 length = Len(str(123456789)) - 1 
 import math def numdigits(n): return ( int(math.floor(math.log10(n))) + 1 ) 

把事情简单化:

 long long int a = 223452355415634664; int x; for (x = 1; a >= 10; x++) { a = a / 10; } printf("%d", x); 

对于非常大的整数,日志方法要快得多。 例如,用2491327的数字(第11920928个斐波那契数字,如果你在意),Python需要几分钟才能执行除10algorithm,而执行1+floor(log(n,10))需要几毫秒。

你可以使用一个recursion的解决scheme,而不是一个循环,但有点类似:

 @tailrec def digits (i: Long, carry: Int=1) : Int = if (i < 10) carry else digits (i/10, carry+1) digits (8345012978643L) 

长期以来,图像可能会发生变化 – 根据不同的algorithm独立测量小数和长数,并根据您的典型inputselect合适的数字。 🙂

当然,没有什么比击败开关:

 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]; 

有些人会告诉你优化代码的大小,但是,现在,过早的优化…

我看到@ daniel.sedlacek结果后很好奇,所以我做了一些使用Swift进行testing的数字超过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楼(log10(x))
div 10迭代的0.867973804473877

log(x,n)-mod(log(x,n),1)+1

其中x是基数,n是数字。