Подсчет числа цифр в числе в O (1)

Question

Мне нужно подсчитать количество десятичных цифр в числе (например: 4 для 1002). Я хочу сделать это в O (1) сложности времени, так как код должен быть повторен по огромному набору чисел, что значительно экономит время процессора.

я пришел с двумя решениями:

1. Деление на 10 в цикле, пока число становится равным нулю. Количество циклов - . Но, очевидно, O (n) время.
2. log_base_10(num) + 1

Вопрос: Является ли log10 O (1) решение? Я запускаю код с glibc на машине x86. Как это осуществляется под капотом? и, есть ли лучшие решения для этого?

Answer 1

Все, что вам нужно сделать, это:

1 + floor(log(N)/log(10)) 

(Это не будет работать на 0. Если вход поплавки, он возвращает количество цифр слева от десятичной точки, и работать только на floats> 0.1.)

Практически наверняка есть инструкция FPU, а не исходная x86, но, конечно же, в расширении, поддерживаемом вашим процессором. Вы можете проверить это, оценивая log(N) много раз в цикле.

Предполагается, что у вас есть номер, сохраненный как int или float. Если у вас есть номер, хранящийся в виде массива переменной длины, используя некоторую библиотеку, это время O (1), если библиотека предварительно вычисляет длину массива (правильная вещь) и O (N) в противном случае (плохие библиотеки).

Как и во всех поплавковых операциях, точность может быть проблемой, если вы действительно близки к переходу 99-100, 999-1000 и т. Д. Как отмечает Стив Джессоп в комментариях этого ответа, вы можете определить, недооценка в соответствии с желаемой семантикой. Я мог бы даже сказать, что у вас немного свободы: вы можете добавить/вычесть что-то вроде 0,1 из N, если каким-то образом это не удалось для этих номеров перехода (их не так много: вы можете вручную протестировать их все самостоятельно, чтобы убедиться, что это необходимо).

Answer 2

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

int num_digits[10000]; 
for (int i = 0; i < 10000; ++i) { 
    if (i < 10) { 
    num_digits[i] = 1; 
    } else if (i < 100) { 
    num_digits[i] = 2; 
    } else if (i < 1000) { 
    num_digits[i] = 3; 
    } 
} 

А теперь вот как вы получите количество цифр числа примерно 4 целочисленных операций:

int get(int n) { 
    int result = 0; 
    while (n > 10000) { 
    result += 4; 
    n /= 10000; 
    } 
    return result + num_digits[n]; 
} 

Этих конечно, жертвует памятью за скорость, но, как мы знаем, there is no free lunch.

Answer 3

Предполагая, что целое число без знака и платформа Intel (инструкция BSR), вы можете получить самый старший бит набора. Тогда вы знаете:

2^i <= num < 2^(i+1) 

где i это самый высокий набор бит num. Таким образом, простая таблица поиска (с индексом i) ограничивает вас двумя возможными десятичными цифрами и может быть разрешена только одним, если.

Но действительно ли вы используете такие большие номера, которые вам нужны для такой неуправляемой оптимизации?

Answer 4

Это выглядит как случай для Bit Twiddling Hacks

unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of 
int r;   // result goes here 

r = (v >= 1000000000) ? 9 : (v >= 100000000) ? 8 : (v >= 10000000) ? 7 : 
    (v >= 1000000) ? 6 : (v >= 100000) ? 5 : (v >= 10000) ? 4 : 
    (v >= 1000) ? 3 : (v >= 100) ? 2 : (v >= 10) ? 1 : 0; 

«Этот метод хорошо работает, когда входной равномерно распределена по 32-битовых значений, потому что 76% из входов улавливаются первым сравнения, 21% 2% пойманы третьим и т. д. (сокращая оставшиеся вниз на 90% при каждом сравнении). В результате в среднем требуется меньше 2.6 операций ».