non-function operator based one-liner for magnitude of an int

Question

I was wondering if there is any way to get the magnitude of an integer without using function calls and only using operators (no control structures).

In case I'm using the term magnitude incorrectly here, what I mean is basically how many digits are occupied. eg. 2468 has a magnitude of 4.

Otherwise, what is the most efficient way to do this? The best I could come up with is while ( num /= 10 ) mag++; but I'm just wondering if there's some sort of black magic out there I'm unaware of.

Solutions in a C style language are preferred (C, C++, Java, C#, etc.)

Answer 1

There are constant-time "bit hacks" for computing related values, like the highest bit that is set in a number. This is analogous, because you want to find the highest digit that is non-zero.

However, since you are interested in the base-10 value, and these methods use binary arithmetic, I am not sure that they can be adapted. Looking at how they work might give you some ideas, though.

Answer 2

Mathematically you want ⌊log₁₀(|x|)⌋ + 1. Unless x is 0.

The difference between operator and function that you give is rather arbitrary. One could always create a language with a ⌊log₁₀(|x|)⌋ + 1 operator!

Still for the fun of it, we can start with creating an integeral log₁₀(x) method, which is most easily done with simple comparison:

//assumes 32-bit int in max value. Add cases accordingly
return (x >= 1000000000) ? 9 : (x >= 100000000) ? 8 : (x >= 10000000) ? 7 : 
  (x >= 1000000) ? 6 : (x >= 100000) ? 5 : (x >= 10000) ? 4 : 
  (x >= 1000) ? 3 : (x >= 100) ? 2 : (x >= 10) ? 1 : 0;

We are going to add 1 to whatever result we get, so we don't even need that addition, we just change our result:

return (x >= 1000000000) ? 10 : (x >= 100000000) ? 9 : (x >= 10000000) ? 8 : 
  (x >= 1000000) ? 7 : (x >= 100000) ? 6 : (x >= 10000) ? 5 : 
  (x >= 1000) ? 4 : (x >= 100) ? 3 : (x >= 10) ? 2 : 1;

The bonus is that this also handles the case of x == 0 correctly.

Now we just need to abs it.

x = x > 0 ? x : -x;
return (x >= 1000000000) ? 10 : (x >= 100000000) ? 9 : (x >= 10000000) ? 8 : 
  (x >= 1000000) ? 7 : (x >= 100000) ? 6 : (x >= 10000) ? 5 : 
  (x >= 1000) ? 4 : (x >= 100) ? 3 : (x >= 10) ? 2 : 1;

And to one-liner it:

return ((x > 0 ? x : -x) >= 1000000000) ? 10 : ((x > 0 ? x : -x) >= 100000000) ? 9 : ((x > 0 ? x : -x) >= 10000000) ? 8 :  ((x > 0 ? x : -x) >= 1000000) ? 7 : ((x > 0 ? x : -x) >= 100000) ? 6 : ((x > 0 ? x : -x) >= 10000) ? 5 : ((x > 0 ? x : -x) >= 1000) ? 4 : ((x > 0 ? x : -x) >= 100) ? 3 : ((x > 0 ? x : -x) >= 10) ? 2 : 1;

The problem is whether you consider ?: a control structure or not. It is an operator, but it does branch (and of more real impact than whether a control structure is used, though still a micro-opt to get rid of).

Non-branching should at least be possible in a multi-liner, lets see.

Non-branching abs is easy:

 (x ^ (x >> 31)) - (x >> 31); // assuming 32-bit int, adjust shift accordingly

Now for the logarithm, I cheat and look up some bit-twiddling hacks I can't remember. I'm just going to dry-code port this (since I've done C# so far and may as well stick with it) from what I can read at http://graphics.stanford.edu/~seander/bithacks.html, and leave testing and fixing any bugs I've introduced as an exercise:

We start with finding log₂(x);

int[] MultiplyDeBruijnBitPosition = new int[]
{
  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

int l = x >> 1; // first round down to one less than a power of 2 
l |= l >> 2;
l |= l >> 4;
l |= l >> 8;
l |= l >> 16;

l = MultiplyDeBruijnBitPosition[(uint)(l * 0x07C4ACDDU) >> 27];

Now we can use this to find the base-10 logarithm:

int[] PowersOf10 = new int[]
    {1, 10, 100, 1000, 10000, 100000,
     1000000, 10000000, 100000000, 1000000000};

int t = (l + 1) * 1233 >> 12;
return t - (x < PowersOf10[t]);