Finding the number of digits of an integer

Viewed 84337

What is the best method to find the number of digits of a positive integer?

I have found this 3 basic methods:

  • conversion to string

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

    for(long long int temp = number; temp >= 1;)
    {
        temp/=10;
        decimalPlaces++;
    } 
    
  • logaritmic calculation

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

where you can calculate log10(x) = ln(x) / ln(10) in most languages.

First I thought the string method is the dirtiest one but the more I think about it the more I think it's the fastest way. Or is it?

19 Answers

Regarding the three methods you propose for "determining the number of digits necessary to represent a given number in a given base", I don't like any of them, actually; I prefer the method I give below instead.

Re your method #1 (strings): Anything involving converting back-and-forth between strings and numbers is usually very slow.

Re your method #2 (temp/=10): This is fatally flawed because it assumes that x/10 always means "x divided by 10". But in many programming languages (eg: C, C++), if "x" is an integer type, then "x/10" means "integer division", which isn't the same thing as floating-point division, and it introduces round-off errors at every iteration, and they accumulate in a recursive formula such as your solution #2 uses.

Re your method #3 (logs): it's buggy for large numbers (at least in C, and probably other languages as well), because floating-point data types tend not to be as precise as 64-bit integers.

Hence I dislike all 3 of those methods: #1 works but is slow, #2 is broken, and #3 is buggy for large numbers. Instead, I prefer this, which works for numbers from 0 up to about 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;
}

Here is the measurement in Swift 4.

Algorithms code:

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
    }

}

Measurement code:

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

Output

timeInterval0: 1.92149806022644

timeInterval1: 0.557608008384705

timeInterval2: 2.83262193202972

On this measurement basis String conversion is the best option for the Swift language.

Adding one more approach to many of the already mentioned approaches. The idea is to use binarySearch on an array containing the range of integers based on the digits of the int data type.
The signature of Java Arrays class binarySearch is :
binarySearch(dataType[] array, dataType key) which returns the index of the search key, if it is contained in the array; otherwise, (-(insertion point) – 1).
The insertion point is defined as the point at which the key would be inserted into the array.
Below is the implementation:

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

Please note that the above approach only works for : Integer.MIN_VALUE <= N <= Integer.MAX_VALUE, but can be easily extended for Long data type by adding more values to the digits array.


For example,
I) for N = 555, digitCount = Arrays.binarySearch(digits , 555) returns -3 (-(2)-1) as it's not present in the array but is supposed to be inserted at point 2 between 9 & 99 like [9, 55, 99].
As the index we got is negative we need to take the bitwise compliment of the result. At last, we need to add 1 to the result to get the actual number of digits in the number N.

In Swift 5.x, you get the number of digit in integer as below :

  1. Convert to string and then count number of character in string
    let nums = [1, 7892, 78, 92, 90]
    for i in nums {
      let ch = String(describing: i)
      print(ch.count)
    }

  1. Calculating the number of digits in integer using loop
    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# Version, without casting to a string.

Related