Efficient way to determine number of digits in an integer
Well, the most efficient way, presuming you know the size of the integer, would be a lookup. Should be faster than the much shorter logarithm based approach. If you don't care about counting the '-', remove the + 1.
#include <climits>
// generic solution
template <class T>
int numDigits(T number)
{
int digits = 0;
if (number < 0) digits = 1; // remove this line if '-' counts as a digit
while (number) {
number /= 10;
digits++;
}
return digits;
}
// partial specialization optimization for 64-bit numbers
template <>
int numDigits(int64_t x) {
if (x == INT64_MIN) return 19 + 1;
if (x < 0) return digits(-x) + 1;
if (x >= 10000000000) {
if (x >= 100000000000000) {
if (x >= 10000000000000000) {
if (x >= 100000000000000000) {
if (x >= 1000000000000000000)
return 19;
return 18;
}
return 17;
}
if (x >= 1000000000000000)
return 16;
return 15;
}
if (x >= 1000000000000) {
if (x >= 10000000000000)
return 14;
return 13;
}
if (x >= 100000000000)
return 12;
return 11;
}
if (x >= 100000) {
if (x >= 10000000) {
if (x >= 100000000) {
if (x >= 1000000000)
return 10;
return 9;
}
return 8;
}
if (x >= 1000000)
return 7;
return 6;
}
if (x >= 100) {
if (x >= 1000) {
if (x >= 10000)
return 5;
return 4;
}
return 3;
}
if (x >= 10)
return 2;
return 1;
}
// partial specialization optimization for 32-bit numbers
template<>
int numDigits(int32_t x)
{
if (x == INT32_MIN) return 10 + 1;
if (x < 0) return numDigits(-x) + 1;
if (x >= 10000) {
if (x >= 10000000) {
if (x >= 100000000) {
if (x >= 1000000000)
return 10;
return 9;
}
return 8;
}
if (x >= 100000) {
if (x >= 1000000)
return 7;
return 6;
}
return 5;
}
if (x >= 100) {
if (x >= 1000)
return 4;
return 3;
}
if (x >= 10)
return 2;
return 1;
}
// partial-specialization optimization for 8-bit numbers
template <>
int numDigits(char n)
{
// if you have the time, replace this with a static initialization to avoid
// the initial overhead & unnecessary branch
static char x[256] = {0};
if (x[0] == 0) {
for (char c = 1; c != 0; c++)
x[c] = numDigits((int32_t)c);
x[0] = 1;
}
return x[n];
}
Finding the number of digits of an integer
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; }
Fastest way to find number of digits of an integer?
Here's a benchmark, with a fix for the loop method to return 1 for the input 0:
func lenLoop(i int) int {
if i == 0 {
return 1
}
count := 0
for i != 0 {
i /= 10
count++
}
return count
}
func lenItoa(i int) int {
return len(strconv.Itoa(i))
}
const num = 834589
func BenchmarkLoop(b *testing.B) {
for i := 0; i < b.N; i++ {
lenLoop(num)
}
}
func BenchmarkItoa(b *testing.B) {
for i := 0; i < b.N; i++ {
lenItoa(num)
}
}
[Note that these only work on positive numbers]
Output on my machine:
goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i7-4771 CPU @ 3.50GHz
BenchmarkLoop
BenchmarkLoop-8 213208418 5.535 ns/op
BenchmarkItoa
BenchmarkItoa-8 33039769 33.74 ns/op
Note that you could get different results for a different size of an input number; I picked length 6 as typical, but you could try other options. For shorter numbers, the extra machinery in Itoa
makes it even slower (in relative terms) than the loop. For huge numbers it's "only" 4x slower than the loop.
The log10
method proposed in another answer is 2x slower than the loop (once fixed to handle corner cases correctly)
How do I determine the number of digits of an integer in C?
floor (log10 (abs (x))) + 1
http://en.wikipedia.org/wiki/Logarithm
Get the number of digits in an int
How about division:
int length = 1;
int x = 234567545;
while ( x /= 10 )
length++;
or use the log10
method from <math.h>
.
Note that log10
returns a double
, so you'll have to adjust the result.
Way to get number of digits in an int?
Your String-based solution is perfectly OK, there is nothing "un-neat" about it. You have to realize that mathematically, numbers don't have a length, nor do they have digits. Length and digits are both properties of a physical representation of a number in a specific base, i.e. a String.
A logarithm-based solution does (some of) the same things the String-based one does internally, and probably does so (insignificantly) faster because it only produces the length and ignores the digits. But I wouldn't actually consider it clearer in intent - and that's the most important factor.
Count number of digits - which method is most efficient?
The following is even more efficient:
int findn(int num)
{
if ( num < 10 )
return 1;
if ( num < 100 )
return 2;
//continue until max int
}
You could optimize this even further by doing a binary search, but that would be overkill.
How to find length of digits in an integer?
If you want the length of an integer as in the number of digits in the integer, you can always convert it to string like str(133)
and find its length like len(str(123))
.
Fastest way to get number of digits on a number?
Math.floor(Math.log10(number) + 1)
// or just (int) Math.log10(number) + 1
For example:
int number = 123456;
int length = (int) Math.log10(number) + 1;
System.out.println(length);
OUTPUT:
6
C++ - how to find the length of an integer
The number of digits of an integer n
in any base is trivially obtained by dividing until you're done:
unsigned int number_of_digits = 0;
do {
++number_of_digits;
n /= base;
} while (n);
Related Topics
Floating Point Format for Std::Ostream
Start Windows Service from Application Without Admin Right(C++)
C++ Convert from 1 Char to String
Efficient 128-Bit Addition Using Carry Flag
Why Are My Struct's Members Not Properly Initialised Using '{}'
How to Install the Openssl Libraries on Ubuntu
How Std::Bind Works with Member Functions
Using C++ Filestreams (Fstream), How to Determine the Size of a File
When Are Static and Global Variables Initialized
Convert Windows Filetime to Second in Unix/Linux
Cross-Platform Way to Get Line Number of an Ini File Where Given Option Was Found
Why Is Including "Using Namespace" into a Header File a Bad Idea in C++