查找整数的位数

Question

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

我发现了这 3 种基本方法：

• 转换为字符串

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

• for 循环

  for(long long int temp = number; temp >= 1;)
  {
      温度/=10；
      小数位数++；
  } 
  

• 对数计算

  数字 = 下限( log10( 数字 ) ) + 1;
  

，您可以在大多数语言中计算 log10(x) = ln(x) / ln(10)。

首先，我认为字符串方法是最脏的方法，但我想得越多，我就越认为它是最快的方法。或者是吗？

Answer 1

正确的答案是测量它 - 但您应该能够猜测转换字符串并遍历它们寻找结束标记所涉及的 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 2

我不知道，而且答案可能会有所不同，具体取决于您的个人语言的实现方式。

所以，压力测试吧！实施所有三个解决方案。在 1 到 1,000,000（或代表解决方案将运行的数字的其他一些巨大数字集）上运行它们，并计算每个数字所需的时间。

让您的解决方案相互竞争，然后让他们一决胜负。就像智力角斗士一样。三种算法登场！一种算法离开！

Answer 3

这个算法也可能很好，假设：

• 数字是整数和二进制编码（<<操作很便宜）

• 我们不知道数字边界

  var num = 123456789L;
  var 长度 = 0;
  var tmp = 1L；
  while(tmp < num)
  {
      伦++;
      tmp = (tmp << 3) + (tmp << 1);
  }
  

该算法的速度应该与提供的 for-loop (2) 相当，但由于（2 位移位、加法和减法，而不是除法），速度要快一些）。

至于Log10算法，它只会给你近似的答案（接近真实，但仍然），因为计算Log函数的解析公式有无限循环，无法精确计算 维基。

Answer 4

测试条件

• 十进制数字系统
• 正整数
• 最多 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 迭代：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));
        }
    }
}

Answer 5

关于您提出的“确定在给定基数中表示给定数字所需的位数”的三种方法，实际上我不喜欢其中任何一个；我更喜欢下面给出的方法。

关于你的方法#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;
}

Answer 6

• 转换为字符串：这将必须迭代每个数字，找到映射到当前数字的字符，将一个字符添加到字符集合中。然后获取生成的 String 对象的长度。将在 O(n) 中运行 n=#digits。

• for循环：将执行2个数学运算：将数字除以10并递增计数器。将在 O(n) for n=#digits 中运行。

• 对数：将调用log10和floor，并加1。看起来像O(1)，但我不太确定log10或floor函数有多快。由于缺乏使用，我对这类事情的了解已经萎缩，因此这些函数中可能存在隐藏的复杂性。

所以我想这可以归结为：查找数字映射是否比多个数学运算或 log10 中发生的任何事情更快？答案可能会有所不同。可能有一些平台的字符映射速度更快，而其他平台的计算速度也更快。另外要记住的是，第一个方法将创建一个新的 String 对象，该对象仅出于获取长度的目的而存在。这可能会比其他两种方法使用更多的内存，但这可能重要也可能无关紧要。

Answer 7

显然，您可以将方法 1 从竞争中排除，因为它使用的 atoi/toString 算法与方法 2 类似。

方法 3 的速度取决于是否为指令集包含 log base 10 的系统编译代码。

Answer 8

无论您使用什么编程语言，都使用最简单的解决方案。我想不出计算整数中的数字会成为任何（有用）程序的瓶颈的情况。

C、C++：

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

Haskell：

len = (length . show) 123456789

JavaScript：

length = String(123456789).length;

PHP：

$length = strlen(123456789);

Visual Basic（未经测试）：

length = Len(str(123456789)) - 1

Answer 9

对于非常大的整数，对数方法要快得多。例如，对于 2491327 位数字（第 11920928 个斐波那契数，如果你关心的话），Python 需要几分钟来执行除以 10 算法，并需要几毫秒来执行 1+floor(log(n,10) ）。

Answer 10

import math
def numdigits(n):
    return ( int(math.floor(math.log10(n))) + 1 )

Answer 11

保持简单：

long long int a = 223452355415634664;

int x;
for (x = 1; a >= 10; x++)
{
   a = a / 10;
}

printf("%d", x);

Answer 12

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

其中 x 是底数，n 是数字。

Answer 13

这是 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 语言的最佳选择。

Answer 14

您可以使用递归解决方案而不是循环，但在某种程度上相似：

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

digits (8345012978643L)

对于长数，情况可能会改变 - 针对不同的算法独立地测量小数和长数，并根据您的典型输入选择合适的算法。 :)

当然，没有什么比 switch 更好的了：

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

有些人会告诉你优化代码大小，但是你知道，过早的优化......

Answer 15

看到 @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 为楼层(log10(x))
0.867973804473877 对于 div 10 迭代

Answer 16

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# 版本，无需转换为字符串。

Answer 17

在 Swift 5.x 中，您可以按如下方式获取整数中的位数：

1. 转换为字符串，然后计算字符串中的字符数

    let nums = [1, 7892, 78, 92, 90]
    for i in nums {
      let ch = String(describing: i)
      print(ch.count)
    }

2. 使用循环计算整数中的位数

    var digitCount = 0
   for i in nums {
     var tmp = i
     while tmp >= 1 {
       tmp /= 10
       digitCount += 1
     }
     print(digitCount)
   }

Answer 18

在许多已经提到的方法中添加一种方法。
这个想法是在包含基于 int 数据类型的 digits 的整数范围的数组上使用 binarySearch。
Java Arrays 类 binarySearch 的签名是：
binarySearch(dataType[] array, dataType key) 返回搜索键的索引（如果它包含在数组中）；否则，(-(插入点) – 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，但可以轻松扩展为 <通过向 digits 数组添加更多值来实现 code>Long 数据类型。

---

例如，
I) 对于 N = 555，digitCount = Arrays.binarySearch(digits , 555) 返回 -3 (-(2)-1)，因为它不存在于数组中，但应该在点处插入2 位于 9 和 之间99 类似于 [9, 55, 99]。
由于我们得到的索引是负数，因此我们需要对结果进行按位补。
最后，我们需要将结果加 1，以获得数字 N 中的实际位数。

Answer 19

总是有这样的方法：

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