Каков самый быстрый способ получить наивысшую десятичную цифру целого числа?

Question

Какой самый быстрый способ реализации

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

(например, который возвращает 3 для 356431, 7 для 71 и 9 для 9)?

Лучшее, что я могу думать:

• constexpr-вычислить «среднего размера» мощность 10, которая вписывается в Т.
• выполнить бинарный поиск (над силами 10, возможно, используя constexpr-built lookup table), чтобы найти p, наивысшая мощность -10 ниже, чем x.
• возвращение х делится на р

... но может быть, есть другой подход.

Примечания:

• Я высказал вопрос, и мой подход в C++ 14ish терминов, и решение в коде было бы хорошо, но абстрактное решение (или даже решение в сборке x86_64) было бы хорошо. Однако я хочу что-то, что будет работать для всех (беззнаковых) целых типов.
• Вы можете игнорировать подписанные интегральные типы.
• Я не указал, что такое «быстрая», но, пожалуйста, будь то аппаратно-зависимым.

Answer 1

Варианты, которые возникают у меня;

Грубая сила: сохраняйте целочисленное деление на 10, пока не получите нуль; что говорит вам, что порядок числа вы смотрите (например, 860 занимает 3 смены (86, 8, 0), так что это 10^3), а затем вернуться п/(10^порядка)

Двоичный поиск: как вы говорите, поиск полномочий 10, но для этого требуются дополнительные переменные и назначения и беспокойство, будет ли эта дополнительная информация отслеживания платить за себя по интересующим вас цифрам? Например, если большая часть ваших чисел мала, грубая сила может быть только быстрее.

Bitshift optimization: подсчитывает, сколько раз вам нужно делать x >> 1, пока не достигнете нуля; это задает диапазон для вашего поиска. Например, 94 занимает 7 смен, чтобы очистить номер. Следовательно, это < 128. Поэтому начните поиск грубой силы на 10^3. Вам понадобится поиск битов => порядок.

Answer 2

Новые чипы x86 поддерживают инструкцию lzcnt, которая сообщает вам количество чистых бит в начале целого числа. Вы можете получить к нему доступ с помощью встроенных функций компилятора, такие как следующие (от 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); 

Вы можете совместить это с поисковой таблицы 640 значений, указывающих на нижнюю и верхнюю границы целых чисел, начиная с каждой цифры от 0-9, которые начинаются с соответствующего количества ясных бит. Фактически, вы могли бы сэкономить место, переместив значение lzcnt на 3 места; соответствие с первыми десятичными цифрами будет по-прежнему уникальным.

Answer 3

С помощью команды lzcnt вы можете построить таблицу делителей для каждого числа ведущих нулевых битов. Например, для знака 64 разрядных чисел:

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 

Тогда вычисление становится:

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

Результат деления будет всегда меньше, чем 20, так что только простая проверка необходима для дробей между 10 и 19. Деление на константу также можно оптимизировать.

Answer 4

Самый лучший вариант, кажется, объединить CLZ подход и разделить на расчетную мощность 10. Таким образом, в псевдокоде:

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() возвращает 64 для long long, 32 для int и 16 для short int.