Как найти количество цифр целого положительного числа

There’s always this method:

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

Well the correct answer would be to measure it – but you should be able to make a guess about the number of CPU steps involved in converting strings and going through them looking for an end marker

Then think how many FPU operations/s your processor can do and how easy it is to calculate a single log.

edit: wasting some more time on a monday morning 🙂

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

One of the problems with high level languages is guessing how much work the system is doing behind the scenes of an apparently simple statement. Mandatory Joel link

This statement involves allocating memory for a string, and possibly a couple of temporary copies of a string. It must parse the integer and copy the digits of it into a string, possibly having to reallocate and move the existing memory if the number is large. It might have to check a bunch of locale settings to decide if your country uses “,” or “.”, it might have to do a bunch of unicode conversions.
Then finding the length has to scan the entire string, again considering unicode and any local specific settings such as – are you in a right->left language?.

Alternatively:

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

Just because this would be harder for you to do on paper doesn’t mean it’s hard for a computer! In fact a good rule in high performance computing seems to have been – if something is hard for a human (fluid dynamics, 3d rendering) it’s easy for a computer, and if it’s easy for a human (face recognition, detecting a voice in a noisy room) it’s hard for a computer!

You can generally assume that the builtin maths functions log/sin/cos etc – have been an important part of computer design for 50years. So even if they don’t map directly into a hardware function in the FPU you can bet that the alternative implementation is pretty efficient.

answered Jul 11, 2011 at 15:14

I don’t know, and the answer may well be different depending on how your individual language is implemented.

So, stress test it! Implement all three solutions. Run them on 1 through 1,000,000 (or some other huge set of numbers that’s representative of the numbers the solution will be running against) and time how long each of them takes.

Pit your solutions against one another and let them fight it out. Like intellectual gladiators. Three algorithms enter! One algorithm leaves!

answered Jul 11, 2011 at 15:13

Test conditions

• Decimal numeral system
• Positive integers
• Up to 10 digits
• Language: ActionScript 3

Results

digits: [1,10],

no. of runs: 1,000,000

random sample: 8777509,40442298,477894,329950,513,91751410,313,3159,131309,2

result: 7,8,6,6,3,8,3,4,6,1

CONVERSION TO STRING: 724ms

LOGARITMIC CALCULATION: 349ms

DIV 10 ITERATION: 229ms

MANUAL CONDITIONING: 136ms

Note: Author refrains from making any conclusions for numbers with more than 10 digits.

Script

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

answered Jul 12, 2011 at 13:11

This algorithm might be good also, assuming that:

• Number is integer and binary encoded (<< operation is cheap)

• We don’t known number boundaries

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

This algorithm, should have speed comparable to for-loop (2) provided, but a bit faster due to (2 bit-shifts, add and subtract, instead of division).

As for Log10 algorithm, it will give you only approximate answer (that is close to real, but still), since analytic formula for computing Log function have infinite loop and can’t be calculated precisely Wiki.

Use the simplest solution in whatever programming language you’re using. I can’t think of a case where counting digits in an integer would be the bottleneck in any (useful) program.

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 (untested):

length = Len(str(123456789)) - 1

answered Jul 11, 2011 at 19:48

• conversion to string: This will have to iterate through each digit, find the character that maps to the current digit, add a character to a collection of characters. Then get the length of the resulting String object. Will run in O(n) for n=#digits.

• for-loop: will perform 2 mathematical operation: dividing the number by 10 and incrementing a counter. Will run in O(n) for n=#digits.

• logarithmic: Will call log10 and floor, and add 1. Looks like O(1) but I’m not really sure how fast the log10 or floor functions are. My knowledge of this sort of things has atrophied with lack of use so there could be hidden complexity in these functions.

So I guess it comes down to: is looking up digit mappings faster than multiple mathematical operations or whatever is happening in log10? The answer will probably vary. There could be platforms where the character mapping is faster, and others where doing the calculations is faster. Also to keep in mind is that the first method will creats a new String object that only exists for the purpose of getting the length. This will probably use more memory than the other two methods, but it may or may not matter.

answered Jul 11, 2011 at 15:17

user240515user240515

3,0061 gold badge27 silver badges34 bronze badges

Brian MintonBrian Minton

3,2863 gold badges35 silver badges41 bronze badges

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

Gary WilloughbyGary Willoughby

50.4k41 gold badges133 silver badges199 bronze badges

user unknownuser unknown

35.3k11 gold badges75 silver badges121 bronze badges

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

Where x is a the base and n is the number.

answered Apr 8, 2017 at 19:00

Ivan SmetaninIvan Smetanin

1,9792 gold badges21 silver badges28 bronze badges

twodayslatetwodayslate

2,7933 gold badges27 silver badges43 bronze badges

GURU ShreyanshGURU Shreyansh

8711 gold badge6 silver badges18 bronze badges

answered Feb 12, 2022 at 19:42

NomenNescioNomenNescio

2,8898 gold badges43 silver badges82 bronze badges

13   голосов , оценка 3.923 из 5