Вычисление количества цифр целого числа еще быстрее

Вычислениеколичествацифрцелогочислаещебыстрее

В моем предыдущем сообщении в блоге я задокументировал, как можно продолжить вычисление числа цифр целого числа быстро. Например, учитывая целое число 999, вы хотите 3, но учитывая целое число 2021, вы хотите 4 .Это фактически целочисленный логарифм по основанию 28.

На компьютерах вы можете быстро вычислить целочисленный логарифм по основанию 2, и, следовательно, вы можете перейти от одно к другому довольно быстро. Вам просто нужна поправка, которую вы можете реализовать с помощью таблицы. Очень хорошее решение, найденное в ссылках, таких как Hacker’s Delight, выглядит следующим образом:

  static  uint 32 _ t таблица  знак равно  {  9  ,   999  ,   1000  ,   9999   ,   99999  ,   999999  ,   99999999  ,   99999999  ,   4294967296  }  ;   int  y  =   (  9    int_log2  ( x )  )  >  >   5  ;  y  +   =  x >  таблица  [y]  ;   return  y  +   1  ;  

За исключением вычисления целочисленного логарифма, он включает умножение на 9 , сдвиг, условный ход, поиск в таблице и приращение. Можете ли вы сделать еще лучше? Ты можешь! Кендалл Виллетс нашел еще более экономичное решение.

  int  fast_digit_count  ( uint 64 _ t x  )   {  static  uint 64 _ t таблица  знак равно  {  4294967296  ,   8589934582  ,   12884901788  ,   12884901788  ,   12884901788  ,   12884901788  ,   17179868184  ,   21474826480  ,   17179868184  ,   17179868184  ,   21474826480  ,   21474826480  ,   21474826480  ,   21474826480  ,   25769703776  ,   25769703776  ,   25769703776  ,   34349738368  ,   30063771072  ,   30063771072  ,   34349738368  ,   34349738368  ,   38554705664  ,   38554705664  ,   38554705664  ,   41949672960  ,   38554705664  ,   41949672960  ,   41949672960  ,   41949672960  ,   42949672960  ,   42949672960  }  ; возвращаться  ( x  +  Таблица[int_log2(x)])  >  >   64  ;  }  

Если я опущу вычисление целочисленного логарифма по основанию 2, для этого потребуется только поиск по таблице, добавление и сдвиг:

  добавить  rax ,   qword   ptr   [8*rcx + table]   shr  rax ,   32  

Таблица содержит числа ceil (log 28 (2 j )) 2 32 + 2 64 – 30 ceil (log 10 (2 j )) для j от 2 до 31, а затем просто ceil (log 28 (2 j )) для j = 31 и j = 32. Первое значение – 2 32 .

Доступна моя реализация решения Кендалла .

Дальнейшее чтение: У Джоша Бличера Снайдера есть сообщение в блоге на эту тему, в котором рассказывается вся история .

Leave a comment

Your email address will not be published. Required fields are marked *