What's the fastest way to obtain the highest decimal digit of an integer? [duplicate]

Question

What's the fastest way to implement

template <typename T>
unsigned highest_decimal_digit(T x);

(which returns e.g. 3 for 356431, 7 for 71 and 9 for 9)?

The best I can think of is:

• constexpr-calculate the "middle-size" power of 10 which fits into T.
• perform a binary search (over the powers of 10, possibly using a constexpr-constructed lookup table) to find p, the highest power-of-10 lower than x.
• return x divided by p

... but maybe there's another approach.

Notes:

• I expressed the question and my approach in C++14ish terms, and a solution in code would be nice, but an abstract solution (or even a solution in x86_64 assembly) would be fine. I do want something that will work for all (unsigned) integer types, though.
• You may ignore signed integral types.
• I didn't specify what "fast" is, but be hardware-conscious please.

Answer 1

The best option seems to be to combine CLZ approach and divide by precalculated power of 10. So, in pseudocode:

powers10=[1,1,1,1,10,10,10,10,100,100...]; // contains powers of 10 map to CLZ values
int firstDigit(unsigned INT_TYPE a) {
    if (a<10) return a; // one digit, screw it
    int j=typesize(a)-clz(a);
    if (j==3) return 1; // 10-16 hit this, return 1
    int k=a/powers10[j];
    if (k>9) return 1; else return k;
}

typesize() returns 64 for long long, 32 for int and 16 for short int.

Answer 2

Newer x86 chips support an lzcnt instruction that tells you the number of clear bits at the start of an integer. You can access it using built-in compiler functions such as the following (from GCC):

 unsigned short __builtin_ia32_lzcnt_16(unsigned short);
 unsigned int __builtin_ia32_lzcnt_u32(unsigned int);
 unsigned long long __builtin_ia32_lzcnt_u64 (unsigned long long);

You could combine this with a lookup table of 640 values indicating the lower and upper bounds of integers starting with each digit from 0-9 that start with the corresponding number of clear bits. In fact, you could save space by right-shifting the lzcnt value 3 places; the correspondence with first decimal digits will still be unique.