Это работает только для степеней 2.
В целом:
x MOD 2^n
эквивалентно:
x AND (2^n - 1)
Обратите внимание, что это может быть только правдойдля x >= 0, в зависимости от вашего определения MOD для x < 0.
Чтобы понять , почему это работает, подумайте, что такое MOD на самом деле - это просто остаток после выполнения целочисленного деления.В случае деления на 2 ^ n мы фактически просто сдвигаем двоичное значение вправо на n битов и отбрасываем любые биты младшего разряда, которые сдвинуты, например, для 8-битного двоичного числа
a b c d e f g h
если мы разделим на 4 = 2 ^ 2, то мы сдвинемся вправо на 2 бита:
0 0 a b c d e f
Остаток (g h) был отброшен в результате целочисленного деления.
Если бы мы хотели знать остаток, то мы могли бы просто извлечь биты g h, применив маску 0 0 0 0 0 0 1 1:
a b c d e f g h
AND 0 0 0 0 0 0 1 1
= 0 0 0 0 0 0 g h
Обратите внимание, что имеет значение 3, которое в общем случае равнопросто 2 ^ n - 1.
Давайте попробуем это с некоторыми действительными числами.Предположим, мы хотим вычислить 42/4 и получить как частное, так и остаток:
42 = 0 0 1 0 1 0 1 0
Чтобы получить частное, мы сдвигаемся вправо на 2 бита:
42 / 4 (decimal)
= 0 0 1 0 1 0 1 0 >> 2
= 0 0 0 0 1 0 1 0
= 10 (decimal)
42 MOD 4 (decimal)
= 0 0 1 0 1 0 1 0 AND 0 0 0 0 0 0 1 1
= 0 0 0 0 0 0 1 0
= 2 (decimal)
Итак, 42/4= 10 остаток 2.