Самый быстрый способ добавления/суммирования отдельных цифровых компонентов числа

Ответ 1

Там есть крутой трюк для суммирования 1 цифры в двоичном формате и с целым числом с фиксированной шириной. На каждой итерации вы выделяете половину цифр каждый на два значения, бит сдвигаете одно значение вниз, а затем добавляете. Первая итерация, отдельная всегда другая цифра. Вторая итерация, пары цифр и т.д.

Учитывая, что 27 является 00011011 в виде 8-битного двоичного кода, процесс...

00010001 + 00000101 = 00010110  <-  every other digit step
00010010 + 00000001 = 00010011  <-  pairs of digits
00000011 + 00000001 = 00000100  <-  quads, giving final result 4

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

02040608 + 01030507 = 03071115  <-  every other digit
00070015 + 00030011 = 00100026  <-  pairs
00000026 + 00000010 = 00000036  <-  quads, final result

Итак, 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36, что верно, но вы можете сделать это только эффективно, если ваше числовое представление является фиксированным. Всегда требуется lg (n) итераций, где lg означает базовый логарифм, и вы округлите вверх.

Чтобы немного расширить это (основываясь на обсуждениях в комментариях), предположим, что это было разумно, немного...

Если вы подсчитываете однозначные дополнения, на самом деле там больше работы, чем простой цикл. Идея, как и побитовая трюка для подсчета бит, заключается в том, чтобы повторно упорядочить эти дополнения (используя ассоциативность), а затем вычислить как можно больше параллельно, используя одно дополнение полной ширины для реализации двух дополнений с половинной шириной, четыре четверть ширины и т.д. Значительные накладные расходы для операций очистки цифр и смещения цифр и даже больше, если вы реализуете это как цикл (вычисление или поиск значений маскировки и сдвига расстояния для каждого шага). "Петля", вероятно, должна быть полностью развернута, и эти маски и расстояния сдвига будут включены как константы в код, чтобы этого избежать.

Процессор с поддержкой Binary Coded Decimal (BCD) мог бы справиться с этим. Маскировка цифр и смещение цифр будут реализованы с использованием маскировки битов и сдвига битов, поскольку каждая десятичная цифра будет кодироваться в 4 (или более) битах, независимо от кодирования других цифр.

Одна из проблем заключается в том, что поддержка BCD в наши дни довольно редка. Раньше он был довольно распространен в 8-битных и 16-битных днях, но, насколько мне известно, процессоры, которые все еще поддерживают его, теперь делают это в основном для обратной совместимости. Причины включают...

• Очень ранние процессоры не включали аппаратное умножение и деление. Аппаратная поддержка этих операций означает, что теперь проще и эффективнее преобразовать двоичный код в десятичный. Двоичный используется почти для всех сейчас, и BCD в основном забывают.

• В библиотеках есть представления десятичных чисел, но мало, если какие-либо языки высокого уровня когда-либо предоставляли переносную поддержку аппаратного BCD, так как ассемблер переставал быть реальным вариантом для большинства разработчиков. Поддержка BCD просто перестала использоваться.

• По мере увеличения числа даже упакованный BCD довольно неэффективно упакован. Число представлений базы 10 ^ х имеют самые важные свойства базы 10 и легко декодируются как десятичные. Base 1000 требуется только 10 бит на три цифры, а не 12, потому что 2 ^ 10 равно 1024. Этого достаточно, чтобы показать, что вы получаете дополнительную десятичную цифру для 32 бит - 9 цифр вместо 8 - и у вас все еще осталось 2 бита, например для знакового бита.

Дело в том, что для того, чтобы этот алгоритм счисления по цифре был вообще полезен, вам нужно работать с десятичной запятой с фиксированной шириной, вероятно, не менее 32 бит (8 цифр). Это дает 12 операций (6 масок, 3 смены, 3 дополнения), а не 15 дополнений для (полностью развернутого) простого цикла. Тем не менее, приграничное усиление - и другие проблемы в коде могут легко означать, что это на самом деле медленнее.

Коэффициент усиления эффективности более ясен в 64 бит (16 десятичных цифр), так как все еще только 16 операций (8 масок, 4 смены, 4 дополнения), а не 31, но шансы найти процессор, поддерживающий 64-битные операции BCD похоже тонкий. И даже если бы вы это сделали, как часто вам это нужно? Кажется маловероятным, что это может стоить усилий и потери переносимости.

Ответ 2

Здесь что-то в Haskell:

sumDigits n = 
  if n == 0 
     then 0
     else let a = mod n 10
          in a + sumDigits (div n 10)

О, но я просто прочитал, что вы уже это делаете...

(тогда также очевидно:

sumDigits n = sum $ map (read . (:[])) . show $ n

)

Ответ 3

Для короткого кода попробуйте следующее:

int digit_sum(int n){
    if (n<10) return n;
    return n%10 + digit_sum(n/10);
}

Или, на словах,

-Если число меньше десяти, тогда цифра представляет собой номер.

- В противном случае цифра представляет собой текущую последнюю цифру (aka n mod10 или n% 10) плюс цифровую сумму всего слева от этого числа (n делится на 10, используя целочисленное деление).

-Этот алгоритм также может быть обобщен для любой базы, подставляя основание в 10.

Ответ 4

int digit_sum(int n)
Do
    if (n<10) return n;
    Exit do
    else

    n=n%10 + digit_sum(n/10);

Loop