Самый быстрый способ вычислить десятичную длину целого числа? (.СЕТЬ)

Два предложения:

1. Профилируйте и поставьте общие случаи на первое место.
2. Выполните двоичный поиск, чтобы минимизировать количество сравнений в худшем случае. Вы можете выбрать из 8 альтернатив, используя ровно три сравнения.

Эта комбинация, вероятно, не принесет вам многого, если только распределение не будет очень перекосным.

Из Bit Twiddling Hacks Шона Андерсона:

Найти целое число по базе 10 в логарифме целого числа

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

static unsigned int const PowersOf10[] = 
    {1, 10, 100, 1000, 10000, 100000,
     1000000, 10000000, 100000000, 1000000000};

t = (IntegerLogBase2(v) + 1) * 1233 >> 12; // (use a lg2 method from above)
r = t - (v < PowersOf10[t]);

Основание 10 целочисленного логарифма вычисляется сначала с использованием одного из описанных выше методов нахождения логарифмического основания 2. По соотношению log10 (v) = log2 (v) / log2 (10) нам нужно умножить его на 1 / log2 ( 10), что составляет примерно 1233/4096, или 1233, за которым следует сдвиг вправо на 12. Добавление единицы необходимо, поскольку IntegerLogBase2 округляется в меньшую сторону. Наконец, поскольку значение t является лишь приближением, которое может отличаться на единицу, точное значение находится путем вычитания результата v ‹PowersOf10 [t].

Этот метод требует на 6 операций больше, чем IntegerLogBase2. Его можно ускорить (на машинах с быстрым доступом к памяти), изменив приведенный выше метод поиска по таблице базы 2 журнала, чтобы записи содержали то, что вычислено для t (то есть pre-add, -mulitply и -shift). Для этого потребуется всего 9 операций, чтобы найти базу журнала 10, при условии, что использовались 4 таблицы (по одной на каждый байт v).

Что касается вычисления IntegerLogBase2, на этой странице представлено несколько альтернатив. Это отличный справочник для всех видов высокооптимизированных целочисленных операций.

Вариант вашей версии также существует, за исключением того, что он предполагает, что значения (а не логическая база 10 значений) равномерно распределены, и, следовательно, выполняет экспоненциально упорядоченный поиск:

Найти целое число по базе 10 целого числа очевидным способом

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 операций.

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

int base10len(uint64_t n) {
  int len = 0;
  /* n < 10^32 */
  if (n >= 10000000000000000ULL) { n /= 10000000000000000ULL; len += 16; }
  /* n < 10^16 */
  if (n >= 100000000) { n /= 100000000; len += 8; }
  /* n < 100000000 = 10^8 */
  if (n >= 10000) { n /= 10000; len += 4; }
  /* n < 10000 */
  if (n >= 100) { n /= 100; len += 2; }
  /* n < 100 */
  if (n >= 10) { return len + 2; }
  else         { return len + 1; }
}

Я сомневаюсь, что это будет быстрее, чем то, что вы уже делаете. Но это предсказуемо.

Я провел небольшое тестирование, и это, кажется, в 2-4 раза быстрее, чем код, который у вас есть сейчас:

static int getLen(long x) {
    int len = 1;
    while (x > 9999) {
        x /= 10000;
        len += 4;
    }
    while (x > 99) {
        x /= 100;
        len += 2;
    }
    if (x > 9) len++;
    return len;
}

Изменить:
Вот версия, которая использует больше операций Int32, которая должна работать лучше, если у вас нет приложения x64:

static int getLen(long x) {
    int len = 1;
    while (x > 99999999) {
        x /= 100000000;
        len += 8;
    }
    int y = (int)x;
    while (y > 999) {
        y /= 1000;
        len += 3;
    }
    while (y > 9) {
        y /= 10;
        len ++;
    }
    return len;
}

Вы отметили в коде, что 10 или более цифр очень редки, поэтому ваше исходное решение неплохое.

Я не тестировал это, но изменение основного закона говорит:

Log10 (x) = Log2 (x) / Log2 (10)

Log2 должен быть немного быстрее, чем Log10, если он реализован правильно.

не уверен, быстрее это или нет .. но всегда можно посчитать ...

static int getLen(long x) {
    int len = 1;
    while (x > 0) {
        x = x/10;
        len++
    };
    return len
}

Что вы имеете в виду под длиной? Количество нулей или все? Это значимые цифры, но вы понимаете общую идею

public static string SpecialFormat(int v, int sf)  
{  
     int k = (int)Math.Pow(10, (int)(Math.Log10(v) + 1 - sf));  
     int v2 = ((v + k/2) / k) * k;  
     return v2.ToString("0,0");  
}

Это простой способ.

private static int GetDigitCount(int number)
{
    int digit = 0;

    number = Math.Abs(number);

    while ((int)Math.Pow(10, digit++) <= number);

    return digit - 1;
}

Если число беззнаковое целое, тогда "Math.Abs ​​(число)" не требуется.

Я сделал метод расширения со всеми числовыми типами.

    private static int GetDigitCount(dynamic number)
    {
        dynamic digit = 0;

        number = Math.Abs(number);

        while ((dynamic)Math.Pow(10, digit++) <= number)
            ;

        return digit - 1;
    }

    public static int GetDigit(this int number)
    {
        return GetDigitCount(number);
    }

    public static int GetDigit(this long number)
    {
        return GetDigitCount(number);
    }

тогда вы используете это.

int x = 100;
int digit = x.GetDigit();  // 3 expected.