int digits( int n ){ int i=0; if (n<0) n= -n; while (n) { n/=10; i++; } return i;}No biggy of course, everyone should be able to do this. So, now lets see some impressive methods.
Quick Way to Get Number of Digits in an Integer
This forum isn't exactly meant for homework, but its an interesting subject so I want to inject some code, and see if we can get some people to show their interesting ways to do this.
No biggy of course, everyone should be able to do this. So, now lets see some impressive methods.
No biggy of course, everyone should be able to do this. So, now lets see some impressive methods.
Quote:Original post by Inmate2993
This forum isn't exactly meant for homework, but its an interesting subject so I want to inject some code, and see if we can get some people to show their interesting ways to do this.
*** Source Snippet Removed ***
No biggy of course, everyone should be able to do this. So, now lets see some impressive methods.
It would appear that you are the only one who considered the possibility of negative numbers.
Quote:Original post by Dave Hunt
It would appear that you are the only one who considered the possibility of negative numbers.
I thought I covered that in my case. The
if (n<0) n= -n;
Crazy... log[2] right-shifts, one multiplication and log[2] plus one addition. Significantly faster than log[10] divisions and log[10] additions or even log[10] multiplications and log[10] additions most likely.
count = 0while 1: if n < 0: n = -n if n == 0: break n = n >> 1 count = count + 1return floor(count * 0.30103)+1
Fine, I'll compete. Let's do binary search in a look-up table to avoid multiplications.
Develop clever algorithm in Python:
Translate to C++:
Anyone care to unroll the loop manually, or generate the look-up table at compile time via TMP? Perhaps specialize for other sizes of numeric type? Or for that matter, handle negative numbers? :) (When printing, you kinda want the negative sign to be counted as an extra digit, but for other algorithms you'd prefer it weren't... hmm.)
Develop clever algorithm in Python:
>>> def digits(n): (low, high) = (0, 9) lut = [10 ** x for x in range(1, 10)] while low != high: test = (low + high) / 2 if n < lut[test] : high = test else: low = test + 1 return low + 1# Some unit tests:>>> [digits(int('9' * n)) for n in range(1, 10)][1, 2, 3, 4, 5, 6, 7, 8, 9]>>> [digits(int('1' + '0' * n)) for n in range(1, 10)][2, 3, 4, 5, 6, 7, 8, 9, 10]>>> digits(0)1Translate to C++:
// Assuming 32-bit integers.const int lut[9] = { 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };inline int digits(int n) { int low = 0; int high = 10; while (low != high) { int test = (low + high) / 2; if (n < lut[test]) { high = test; } else { low = test + 1; } } return low + 1;}Anyone care to unroll the loop manually, or generate the look-up table at compile time via TMP? Perhaps specialize for other sizes of numeric type? Or for that matter, handle negative numbers? :) (When printing, you kinda want the negative sign to be counted as an extra digit, but for other algorithms you'd prefer it weren't... hmm.)
Quote:Original post by dohoQuote:Original post by Dave Hunt
It would appear that you are the only one who considered the possibility of negative numbers.
I thought I covered that in my case. Thepart isn't needed.if (n<0) n= -n;
By Jove, you're right. I didn't pay close enough attention to your for loop conditional. Sorry.
sleepy right now, but here is something:
It prolly has some dumb bug as usual, but I will try it later tomorrow.
int numDigits(int n){ for(int i=1,int numDigits=0;;i>n?(return numDigits):(numDigits++,i*=10)); //buggy! return -1;}It prolly has some dumb bug as usual, but I will try it later tomorrow.
Quote:Original post by Sagar_Indurkhya
sleepy right now, but here is something:
*** Source Snippet Removed ***
It prolly has some dumb bug as usual, but I will try it later tomorrow.
I like this one. Scoping rules probably wouldn't cause a collision with numDigits identifier, but just to be safe I'd recommend never doing that ever again. =D
Quote:Original post by Inmate2993Quote:Original post by Sagar_Indurkhya
sleepy right now, but here is something:
*** Source Snippet Removed ***
It prolly has some dumb bug as usual, but I will try it later tomorrow.
I like this one. Scoping rules probably wouldn't cause a collision with numDigits identifier, but just to be safe I'd recommend never doing that ever again. =D
Thanks! It's not often that I write code that considered nifty.
I am sure it can be further optimized, and can garuntee you that any self respecting compiler would further optimizer it.
You probably have so many errors having to do with unspecified order of operations in there that I don't even want to think about it.
*EDIT* Never mind, looked closer.
Nice!
*EDIT* Never mind, looked closer.
Nice!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
