NumberofDigitsinanIntegerinJava

编程

We"ll also analyze those different methods and will figure out which algorithm would best fit in our situation.

2. Number of Digits in an Integer

For the methods discussed here, we"re only considering positive integers. If we"re expecting any negative input, then we can first make use of Math.abs(number) before using any of these methods.

2.1. String-Based Solution

Perhaps the easiest way of getting the number of digits in an Integer is by converting it to String, and calling the length() method. This will return the length of the String representation of our number:

1

int

length = String.valueOf(number).length();

But, this may be a sub-optimal approach, as this statement involves memory allocation for a String, for each evaluation. The JVM must first parse our number and copy its digits into a separate String and perform a number of different operations as well (like keeping temporary copies, handle Unicode conversions etc).

If we only have a few numbers to evaluate, then we can clearly go with this solution – because the difference between this and any other approach will be neglectable even for large numbers.

2.2. Logarithmic Approach

For the numbers represented in decimal form, if we take their log in base 10 and round it up then we"ll get the number of digits in that number:

1

int

length = (

int

) (Math.log10(number) +

1

);

Note that log100 of any number is not defined. So if we"re expecting any input with value 0, then we can put a check for that as well.

The logarithmic approach is significantly faster than String based approach as it doesn"t have to go through the process of any data conversion. It just involves a simple, straightforward calculation without any extra object initialization or loops.

2.3. Repeated Multiplication

In this method, we"ll take a temporary variable (initialized to 1) and will continuously multiply it with 10 until it becomes greater to our number. During this process, we"ll also use a length variable which will keep a track of the number"s length:

1

2

3

4

5

6

7

int

length =

0

;

long

temp =

1

;

while

(temp <= number) {

    

length++;

    

temp *=

10

;

}

return

length;

In this code, the line temp *= 10 is same as writing temp = (temp << 3) + (temp << 1). Since multiplication is usually costlier operation on some processors when compared to shift operators, the latter may be a bit more efficient.

2.4. Dividing with Powers of Two

If we know about the range of our number, then we can use a variation that will further reduce our comparisons. This method divides the number by powers of two (e.g. 1, 2, 4, 8 etc.):

This method divides the number by powers of two (e.g. 1, 2, 4, 8 etc.):

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

int

length =

1

;

if

(number >=

100000000

) {

    

length +=

8

;

    

number /=

100000000

;

}

if

(number >=

10000

) {

    

length +=

4

;

    

number /=

10000

;

}

if

(number >=

100

) {

    

length +=

2

;

    

number /=

100

;

}

if

(number >=

10

) {

    

length +=

1

;

}

return

length;

It takes advantage of the fact that any number can be represented by the addition of powers of 2. For example, 15 can be represented as 8+4+2+1, which all are powers of 2.

For a 15 digit number, we would be doing 15 comparisons in our previous approach, which we have reduced to just 4 in this method.

2.5. Divide And Conquer

This is perhaps the bulkiest approach when compared to all other described here, but needless to say, this one is the fastest because we"re not performing any type of conversion, multiplication, addition or object initialization.

We get our answer in just three or four simple if statements:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

if

(number <

100000

) {

    

if

(number <

100

) {

        

if

(number <

10

) {

            

return

1

;

        

}

else

{

            

return

2

;

        

}

    

}

else

{

        

if

(number <

1000

) {

            

return

3

;

        

}

else

{

            

if

(number <

10000

) {

                

return

4

;

            

}

else

{

                

return

5

;

            

}

        

}

    

}

}

else

{

    

if

(number <

10000000

) {

        

if

(number <

1000000

) {

            

return

6

;

        

}

else

{

            

return

7

;

        

}

    

}

else

{

        

if

(number <

100000000

) {

            

return

8

;

        

}

else

{

            

if

(number <

1000000000

) {

                

return

9

;

            

}

else

{

                

return

10

;

            

}

        

}

    

}

}

Similar to the previous approach, we can use this method only if we know about the range of our number.

3. Benchmarking

Now that we have a good understanding of the potential solutions, let"s now do some simple benchmarking of all our methods using the Java Microbenchmark Harness (JMH).

The following table shows the average processing time of each operation (in nanoseconds):

1

2

3

4

5

6

Benchmark                            Mode  Cnt   Score   Error  Units

Benchmarking.stringBasedSolution     avgt  200  32.736 ± 0.589  ns/op

Benchmarking.logarithmicApproach     avgt  200  26.123 ± 0.064  ns/op

Benchmarking.repeatedMultiplication  avgt  200   7.494 ± 0.207  ns/op

Benchmarking.dividingWithPowersOf2   avgt  200   1.264 ± 0.030  ns/op

Benchmarking.divideAndConquer        avgt  200   0.956 ± 0.011  ns/op

The String-based solution, which is the simplest, is also the most costly operation – as this is the only one which requires data conversion and initialization of new objects.

The logarithmic approach is significantly more efficient, compared to the previous solution – as it doesn"t involve any data conversion. And, being a single line solution, it can be a good alternative to String-based approach.

Repeated multiplication involves simple multiplication, proportionally with the number length; for example, if a number is fifteen digits long, then this method will involve fifteen multiplications.

However, the very next method takes advantage of the fact that every number can be represented by powers of two (the approach similar to BCD), and reduces the same to 4 division operations, so it"s even more efficient than the former.

Finally, as we can infer, the most efficient algorithm is the verbose Divide and Conquer implementation – which delivers the answer in just three or four simple if statements. We can use it if we have a large dataset of numbers we need to analyze.

4. Conclusion

In this brief article, we outlined some of the ways to find the number of digits in an Integer and we compared the efficiency of each approach.

And, as always, you can find the complete code over on GitHub.

以上是 NumberofDigitsinanIntegerinJava 的全部内容, 来源链接: utcz.com/z/513067.html

回到顶部