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

Вот версия двоичного поиска, которую я протестировал, который работает над 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; }
}

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

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

Я сделал некоторое тестирование, и это, кажется, в 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;
}

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

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

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

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

Я не протестировал это, но в законе о переходе к другому основанию говорится:

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

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

Из 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 и -сдвиг). Для этого потребуется всего 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 операций на в среднем.

static int getDigitCount( int x )
    {
    int digits = ( x < 0 ) ? 2 : 1; // '0' has one digit,negative needs space for sign
    while( x > 9 ) // after '9' need more
        {
        x /= 10; // divide and conquer
        digits++;
        }
    return digits;
    }