查找整数的位数

Question

找到正整数位数的最佳方法是什么？

我找到了这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).

首先我认为字符串方法是最脏的,但我想的越多,我认为这是最快的方法.或者是吗？

Answer 1

总有这种方法:

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

Answer 2

那么正确的答案就是测量它 - 但你应该能够猜测转换字符串并通过它们寻找结束标记所涉及的CPU步数

然后想想你的处理器可以做多少FPU操作以及计算单个日志是多么容易.

编辑:在星期一早上浪费更多时间:-)

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

高级语言的一个问题是猜测系统在一个看似简单的语句的幕后做了多少工作.强制Joel链接

此语句涉及为字符串分配内存,可能还有一些字符串的临时副本.它必须解析整数并将其数字复制到一个字符串中,如果数字很大,可能需要重新分配和移动现有内存.它可能必须检查一堆区域设置以确定您的国家/地区是使用","还是".",它可能需要进行一堆unicode转换.
然后找到长度必须扫描整个字符串,再次考虑unicode和任何本地特定设置,如 - 你是右 - >左语言吗？

或者:

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

只是因为这对你在纸上做起来更难,并不意味着它对电脑来说很难!事实上,高性能计算中的一个好规则似乎是 - 如果某些事情对于人类来说很难(流体动力学,3d渲染),那么对于计算机来说它很容易,并且如果它对于人类来说很容易(面部识别,检测到一个人的声音)嘈杂的房间)电脑很难!

你通常可以假设内置数学函数log/sin/cos等 - 已经成为计算机设计50年的重要部分.因此,即使它们没有直接映射到FPU中的硬件功能,您也可以打赌替代实现非常有效.

Answer 3

我不知道,答案可能会有所不同,具体取决于您的个人语言的实施方式.

所以,压力测试吧!实施所有三种解决方案 在1到1,000,000(或代表解决方案将要运行的数字的其他一些大数字)上运行它们,并计算每个数字所需的时间.

让你的解决方案相互对立,让他们对抗它.像智力角斗士一样.三种算法进入!一种算法离开!

Answer 4

这个算法可能也不错,假设:

• Number是整数和二进制编码(<<操作便宜)

• 我们不知道数字边界

  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.

Answer 5

测试条件

• 十进制数字系统
• 正整数
• 最多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

转换为字符串:724ms

对数计算: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));
        }
    }
}