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

Ответ 1

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

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

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

Ответ 2

например. для 32 бит без знака:

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

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

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

Шаг 2:

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

Ответ 3

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

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

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

Ответ 4

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

Итак, можно сделать что-то вроде этого:

 while(n > 10000)
   n /= 1000;

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

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

Ответ 5

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

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

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

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

Ответ 6

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

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

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

Ответ 7

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

//Shashank Jain
#include<iostream>
#include<cmath>
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<<fdigit<<endl;
    return 0;
}

Ответ 8

int FirstDigit ( int Number ) {

    // to obtain the <number of digits -1> 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);

Ответ 9

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

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

Ответ 10

    for(int i=0; i<n; i++)
    {  
        e=5; //Specify the number of digits in the number OR Exponential value of 10
        while(e>=0)
        {   
            tenp=pow(10,e); //#include <math.h>
            if(arr[i]/tenp!=0)
            {
                q[i][e]=arr[i]/tenp%10;
            }
            e--;
        }
    }

Ответ 11

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

Es.

Decimal value: 265
BCD format: 0010-0110-0101

Ответ 12

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

Ответ 13

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

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

#include <iostream>

using namespace std;

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