How to retrieve the first decimal digit of number efficiently

Some processors have instructions that calculate "how big" a number is, very quickly (see http://en.wikipedia.org/wiki/Leading_zero_count). This can be used to quickly choose a power of 10, and divide by it, instead of dividing by 10 repeatedly.

Suppose you are given a function clz that calculates the number of leading zero bits in a number's binary representation (0...32). Then, you can use a lookup table that gives the proper power of 10 for each number of leading zeros.

uint32_t powers_of_10[33] = {
    1000000000, 1000000000,
    100000000, 100000000, 100000000,
    10000000, 10000000, 10000000,
    1000000, 1000000, 1000000, 1000000,
    100000, 100000, 100000,
    10000, 10000, 10000,
    1000, 1000, 1000, 1000,
    100, 100, 100,
    10, 10, 10,
    1, 1, 1, 1, 1
};

int CalcFirstDecimalDigit(uint32_t x)
{
    int leading_zeros = clz(x);
    x /= powers_of_10[leading_zeros];
    if (x >= 10)
        return 1;
    else
        return x;
}

e.g. for in 32 bit unsigned:

Step 1: determine (by binary search) in which of the following intervals the value is:

0 .. 9
10 .. 99
100 .. 999
1000 .. 9999
10000 .. 99999
100000 .. 999999
1000000 .. 9999999
10000000 .. 99999999
100000000 .. 999999999
1000000000 .. 4294967295

takes max 4 compares

Step 2:

Than calculate the leading digit by one division.

I'm pretty sure that sprintf (as I assume it is) will be SIGNIFICANTLY slower. You could do some optimization to reduce the number of divide operations (which is one of the slowest instructions on nearly all processors).

So one could do something like this:

 while(n > 10000)
   n /= 1000;

 while(n >= 9)
   n /= 10;

That is, of course, if speed is really important.