Реализовать по модулю, используя битовые сдвиги?
================================================

Я пишу некоторый код для очень ограниченной системы, где оператор мод очень медленный. В моем коде модуль нужно использовать примерно 180 раз в секунду, и я подумал, что его максимально возможное удаление значительно увеличило бы скорость моего кода, так как сейчас один цикл моего основного цикла не выполняется за 1/60 второй, как и должно быть. Мне было интересно, если бы было возможно повторно реализовать модуль, используя только битовые сдвиги, как это возможно с умножением и делением. Итак, вот мой код на C ++ (если бы я мог выполнить модуль по сборке, это было бы еще лучше). Как я могу удалить по модулю, не используя деление или умножение?

**EDIT:** На самом деле я понял, что мне нужно делать это более 180 раз в секунду. Видя, как значение ввода может быть очень большое число до 40 цифр.

simple побитовые операции принимают степень двойки по модулю (делителю) значения (дивиденд), используя AND с делителем-1. Несколько примеров:

**Why it works?** Рассмотрим битовую комбинацию для значения 123, которое`1111011` а затем делитель 4, который имеет битовую комбинацию`00000100`, Как мы уже знаем, делитель должен быть степенью двойки (как 4), и нам нужно уменьшить его на единицу (от 4 до 3 в десятичном виде), что дает нам битовый шаблон`00000011`, После того, как мы поразрядно-И оба исходных 123 и 3, результирующий битовый шаблон будет`00000011`, Это оказывается 3 в десятичном виде. Причина, по которой нам нужен делитель степени двойки, состоит в том, что, как только мы уменьшаем их на единицу, все менее значимые биты устанавливаются в`1` а остальные`0`, Как только мы выполним побитовое И, он "отменяет" более значимые биты от первоначального значения, и оставляем нам просто остаток от исходного значения, деленный на делитель.

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

Также есть[предыдущий вопрос, связанный с предметом](https://stackoverflow.com/questions/980702/efficient-cycles-wise-algorithm-to-compute-modulo-25) который, вероятно, имеет интересную информацию по этому вопросу с разных точек зрения.



как сумму степеней 16 (то есть разбиваете его на nybbles), то каждый член вносит свой вклад в последнюю цифру таким же образом, за исключением одного.

Отметим, что 6 = 5 + 1, и 5 'будут отменены, если их будет четное число. Так что просто сложите nybbles (кроме последнего) и добавьте 5, если результат нечетный.

Это уменьшает 16-битный 4-кратный модуль по модулю до числа не более`0xF * 4 + 5 = 65`, В двоичном коде это по-прежнему раздражает 3 нюбла, так что вам нужно будет повторить алгоритм (хотя один из них на самом деле не считается).

Но у 286 должно быть достаточно эффективное добавление BCD, которое вы можете использовать для вычисления суммы и получения результата за один проход. (Это требует преобразования каждого nybble в BCD вручную; я недостаточно знаю о платформе, чтобы сказать, как ее оптимизировать или проблематично.)



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

Но есть очевидная сделка в пространстве-времени, которую вы можете совершить здесь: настроить таблицу значений для`out` а также`out % 10` и посмотри. Тогда линия становится

и, если повезет, это будет 16-битное добавление и операция сохранения.



для компиляторов, и фактически, gcc уже делает это.

Этот простой фрагмент кода:

Создает следующий код на моем довольно старом gcc с -O3:

Если вы игнорируете функцию epilogue / prologue, в основном два мулла (действительно, на x86 нам повезло, и мы можем использовать lea для одного) и некоторые сдвиги и добавления / переходы. Я знаю, что где-то уже объяснял теорию, лежащую в основе этой оптимизации, поэтому я посмотрю, смогу ли я найти этот пост, прежде чем объяснять его еще раз.

Теперь о современных процессорах, которые, безусловно, быстрее, чем доступ к памяти (даже если вы попали в кэш), но о том, быстрее ли это для вашего явно более древнего процессора, - это вопрос, на который можно ответить только с помощью сравнительного анализа (и также убедитесь, что Ваш компилятор выполняет эту оптимизацию, в противном случае вы всегда можете просто «украсть» версию gcc здесь;)). Особенно с учетом того, что оно зависит от эффективных мульч (то есть старших битов команды умножения), чтобы быть эффективными.
Обратите внимание, что этот код**not** не зависит от размера - точнее, изменяется магическое число (и, возможно, также части добавления / сдвига), но это можно адаптировать



 может быть, вы можете адаптировать[алгоритм двойного дублирования](https://en.wikipedia.org/wiki/Double_dabble) к вашим потребностям?

Этот алгоритм используется для преобразования двоичных чисел в десятичные без использования модуля или деления.