What is the fastest way to get the highest decimal digit of an integer?

Question

What is the fastest way to implement

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

(which returns, for example, 3 for 356431, 7 for 71, and 9 for 9)?

The best I can think of:

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

... but maybe there is a different approach.

Notes:

• I expressed the question and my approach in terms of C ++ 14ish, and a solution in the code would be nice, but an abstract solution (or even a solution in x86_64 assembly) would be fine. I want something that will work for all (unsigned) integer types.
• You can ignore signed integral types.
• I did not indicate what is “fast”, but to be hardware-conscious.

Answer 1

The best option is to combine the CLZ approach and divide by the previously calculated power of 10. Thus, in the pseudo-code:

 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

The new x86 chips support the lzcnt command, which tells you the number of clear bits at the beginning of an integer. You can access it using the built-in compiler functions, such as the following: 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 can combine this with a lookup table of 640 values ​​indicating the lower and upper bounds of integers, starting with each digit from 0-9, which starts with the corresponding number of clear bits. In fact, you could save space by changing the lzcnt value to 3 places; matching with the first decimal digits will still be unique.

Answer 3

With the lzcnt command lzcnt you can build a divisor table for each number of leading zero bits. For example, for 64-bit unsigned numbers:

 lz | range | div ---+---------+---- 64 | 0 | 1 63 | 1 | 1 62 | 2-3 | 1 61 | 4-7 | 1 60 | 8-15 | 1 59 | 16-31 | 10 58 | 32-63 | 10 57 | 64-127 | 10 56 | 128-255 | 100 ... 0 | 9223372036854775808-18446744073709551615 | 1000000000000000000 

Then the calculation will be:

 leading_zero_bits = lzcnt(x); leading_digit = x / divisor_table[leading_zero_bits]; if (leading_digit >= 10) leading_digit = 1; 

The division result will always be less than 20, therefore, for coefficients between 10 and 19. A simple check is needed. Division by constant can also be optimized.

Answer 4

Parameters that arise for me;

Brute force: keep the integer division by 10 until you get zero; (e.g. 860 takes 3 shifts (86, 8, 0), so it's 10 ^ 3) and then returns n / (order 10 ^)

Binary search: as you say, search by degrees 10, but this requires additional variables and assignments, and the problem will be that the additional tracking information is paid by the type of numbers you care about? For example, if most of your numbers are small, brute force can only be faster.

Bitshift Optimization: Counts how many times you need to do x >> 1 until you reach zero; This sets the range for your search. For example, 94 takes 7 shifts to clear the number. Therefore, 128. Therefore, start the search for brute force at 10 ^ 3. You will need to search for the order of bits =>.