Как эффективно получить первую десятичную цифру числа

Одним из очевидных решений является:

int n = 2134; while(n > 9) n /= 10; 

которая принимает линейное время. Можем ли мы сделать все быстрее?

Является ли это быстрее, чем линейное время:

 char s[100]; sprintf(s, "%d", n); n = s[0]-'0'; 

Какими другими способами (эффективность является первоочередной задачей)?
Я видел это , за исключением того, что мне нужно найти только первую цифру. (Кроме того, я не понимаю ответа).

Некоторые процессоры имеют инструкции, которые очень быстро вычисляют «насколько велика» число (см. http://en.wikipedia.org/wiki/Leading_zero_count ). Это можно использовать для быстрого выбора мощности 10 и деления на нее вместо деления на 10 раз.

Предположим, вам дана функция clz которая вычисляет количество clz нулевых битов в двоичном представлении числа (0 … 32). Затем вы можете использовать таблицу поиска, которая дает правильную мощность 10 для каждого числа ведущих нhive.

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

например, для 32-битного без знака:

Шаг 1: определите (по бинарному поиску), в каком из следующих интервалов значение:

 0 .. 9 10 .. 99 100 .. 999 1000 .. 9999 10000 .. 99999 100000 .. 999999 1000000 .. 9999999 10000000 .. 99999999 100000000 .. 999999999 1000000000 .. 4294967295 

берет максимум 4 сравнения

Шаг 2:

Затем вычислить ведущую цифру на одно деление.

Второй пример должен использовать sprintf . Во всяком случае, он не может быть быстрее, так как все число напечатано, таким образом, выполняется поиск всех цифр.

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

Таким образом, самое простое решение также быстрее.

Я уверен, что sprintf (как я предполагаю) будет ЗНАЧИТЕЛЬНО медленнее. Вы можете сделать некоторую оптимизацию, чтобы уменьшить количество операций деления (что является одной из самых медленных инструкций почти для всех процессоров).

Так можно было сделать что-то вроде этого:

  while(n > 10000) n /= 1000; while(n >= 9) n /= 10; 

Это, конечно, если скорость действительно важна.

вы можете сделать это в O (1) постоянном времени, но за счет очень большого использования памяти. Это то же самое, что и раньше.

Вы можете создать таблицу поиска из 2 ^ 31 записей (подписанный int), 4 бита на запись (с 4 битами вы можете кодировать первую цифру 1-9 числа в десятичном представлении).

то вы можете использовать команду int для доступа к таблице поиска и получить первую цифру в O (1). таблица поиска займет 2 ^ 31 * 4 бит -> 1024 Мбайт

это самый быстрый способ, о котором я могу думать …

Вот несколько вариантов бинарного поиска. Как двоичный поиск, это O (log n). Будет ли это быстрее, будет зависеть от того, насколько быстро вы можете сделать целочисленное деление.

 if (n >= 100000000) n /= 100000000 if (n >= 10000) n /= 10000 if (n >= 100) n /= 100 if (n >= 10) n /= 10 

Метод легко расширяется для целых чисел с большим диапазоном.

Вы можете сделать это просто:

 //Shashank Jain #include #include using namespace std; int main() { int num,fdigit; cin>>num; if(num<0) num*=-1; int l=log10(num); // l = (length of number -1) fdigit=num/pow(10,l); cout< 
 int FirstDigit ( int Number ) { // to obtain the  use this math formula: int DigitsInNumber = (int) lg(Number); long TenExpon = pow(10, DigitsInNumber); return (Number / TenExpon); //first digit } 

также: lg(n) = ln(n) / ln(10);

Ваше первое решение (предполагая, что n известно как> = 0) является почти оптимальным, и я думаю, что его можно было бы существенно улучшить, используя язык ассемблерной сборки. Но это было бы полезно, если бы вы обрабатывали миллионы таких чисел.

Второе решение – как я могу это сделать? – более явный подход: производительность? Ла-ди-да, кто заботится …

  for(int i=0; i=0) { tenp=pow(10,e); //#include  if(arr[i]/tenp!=0) { q[i][e]=arr[i]/tenp%10; } e--; } } в  for(int i=0; i=0) { tenp=pow(10,e); //#include  if(arr[i]/tenp!=0) { q[i][e]=arr[i]/tenp%10; } e--; } } 

если вы номер x9x8x7x6x5x4x3x2x1, тогда вы просто делите на 10 ^ 8, так что вам нужно: лучший способ узнать, сколько цифр число. Вы можете использовать двоичный поиск /

Сначала сделайте двойную переменную, в которой сохраняется число. Затем разделите это число на 10 в цикле, чтобы число непрерывно теряло цифру, пока оно не станет 1-значным числом. переведите двойную переменную в int, чтобы округлить ее. Результатом будет предшествующая первая десятичная цифра.

Код будет работать в O (log (n)).

 #include  using namespace std; int main() { double a; cin >> a; while (true) { a /= 10; if (a < 10) { a = int(a); cout << a; break; } } return 0; }