Как компьютеры находят модуль?

Question

Есть ли какой-нибудь крутой алгоритм с побитовыми операциями?

Answer 1

Часто операции модуля и деления на процессоре - это одно и то же. Например, обратитесь к http://jsimlo.sk/docs/cpu/index.php/div.html. Это реализация инструкции деления на процессорах Intel.

Answer 2

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

Answer 3

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

Во многих процессорах целочисленное умножение значительно быстрее, чем целочисленное деление; некоторые процессоры даже не имеют кода операции целочисленного деления (умножение на n -битные значения можно оптимизировать в схему глубины O (log n) , тогда как не существует известного способа оптимизировать схему деления ниже глубины O (n) ).

Answer 4

Помимо очевидного метода с использованием DIV и IDIV (для x86), как упомянуто выше, результат любого числа по модулю со степенью двойки можно вычислить, взяв побитовое значение и: x mod y гдеу Pow2 совпадает с x AND (y - 1).Большинство компиляторов выполняют это, когда это возможно, поскольку деление намного дороже, чем побитовые операции

Answer 5

x mod y = x - y * (x / y)

, где (x / y) - целочисленное деление.

Answer 6

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

Цитирование википедии:

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

x% 2n == x & (2n - 1)

Примеры (при условии, что x является положительным целым числом):

x% 2 == x & 1

x% 4 == x & 3

x% 8 == x & 7

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