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

Есть классный трюк для суммирования цифр 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 означает логарифм по основанию два, и вы округляете в большую сторону.

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

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

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

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

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

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

3. По мере увеличения чисел даже упакованные BCD упаковываются довольно неэффективно. Представления чисел с основанием 10^x обладают наиболее важными свойствами основания 10 и легко декодируются как десятичные. Базе 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, кажутся незначительными. И даже если бы вы это сделали, как часто вам это нужно в любом случае? Кажется маловероятным, что это может стоить усилий и потери мобильности.

Вот что-то в 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

)

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

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

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

-Если число меньше десяти, то сумма цифр и есть само число.

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

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