mohit - 8 months ago 28

C Question

One obvious solution is:

`int n = 2134;`

while(n > 9)

n /= 10;

which takes linear time. Could we do any faster?

Is this any faster than linear time:

`char s[100];`

sprintf(s, "%d", n);

n = s[0]-'0';

Which are the other ways (efficiency is primary concern)?

I've seen this, except that I need to find only the first digit.

(Also, I don't understand the answer).

Answer

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;
}
```