Побитовое и вместо оператора модуля

Мы знаем, что, например, по модулю степени двойки можно выразить так:

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

Примеры:

x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7 

А как насчет общей нестепени двух чисел?

Скажем:

x% 7 ==?

Во-первых, сказать, что

x % 2 == x & 1

Простой контрпример: x = -1. Во многих языках, в том числе Java, -1 % 2 == -1. То есть, %это не обязательно традиционное математическое определение по модулю. Java, например, называет это «оператором остатка».

Что касается побитовой оптимизации, в поразрядной арифметике «легко» можно выполнить только степень двойки по модулю. Вообще говоря, только по модулю степеней основания b "легко" можно сделать с представлением чисел с основанием b .

В основании 10, например, для неотрицательного N, N mod 10^kпросто принимая значащие kцифры.

Ссылки

• JLS 15.17.3 Остающийся оператор%
• Википедия / Операция по модулю

Есть только простой способ найти числа по модулю 2 ^ i с помощью побитового вычисления.

Существует изобретательный способ решения случаев Мерсенна по ссылке, например n% 3, n% 7 ... Существуют особые случаи для n% 5, n% 255 и составные случаи, такие как n% 6.

Для случаев 2 ^ i, (2, 4, 8, 16 ...)

n % 2^i = n & (2^i - 1)

Более сложные объяснить сложно. Читайте, только если вам очень любопытно.

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

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

(число) _{основание} % основание ^x

эквивалентно последним x цифрам (числа) _базы .

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

Например, если x - 32-битное целое число без знака, тогда x% 3 = popcnt (x & 0x55555555) - popcnt (x & 0xaaaaaaaa)

По модулю "7" без оператора "%"

int a = x % 7;

int a = (x + x / 7) & 7;

Без использования побитового &оператора и ( ) в двоичном формате нет. Эскиз доказательства:

Предположим, что существует такое значение k , что x & k == x % (k + 1), но k! = 2 ^ n - 1 . Тогда, если x == k , выражение x & kкажется «работает правильно», и результат будет k . Теперь рассмотрим х == ки : если были какие -то «0» биты к , есть некоторые я больше 0 , которые ки могут быть выражены только с 1-бит в этих положениях. (Например, 1011 (11) должно стать 0111 (7), когда из него было вычтено 100 (4), в этом случае бит 000 становится 100, когда i = 4. ) Если бит из выражения k должен измениться с нуля одному, чтобы представить ки, то он не может правильно вычислить x% (k + 1) , которое в этом случае должно быть ki , но нет возможности для побитового логического значения и создания этого значения с учетом маски.

В этом конкретном случае (мод 7) мы все еще можем заменить% 7 поразрядными операторами:

// Return X%7 for X >= 0.
int mod7(int x)
{
  while (x > 7) x = (x&7) + (x>>3);
  return (x == 7)?0:x;
}

Это работает, потому что 8% 7 = 1. Очевидно, этот код, вероятно, менее эффективен, чем простой x% 7, и, безусловно, менее читабелен.

Используя bitwise_and, bitwise_or и bitwise_not, вы можете изменять любые битовые конфигурации на другие битовые конфигурации (т. Е. Этот набор операторов является «функционально полным»). Однако для таких операций, как модуль, общая формула обязательно будет довольно сложной, я бы даже не стал пытаться ее воссоздать.