Ответ 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 похоже тонкий. И даже если бы вы это сделали, как часто вам это нужно? Кажется маловероятным, что это может стоить усилий и потери переносимости.