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

Question

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

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

Примеры:

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

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

Допустим,

x% 7 ==?

Answer 1

Прежде всего, на самом деле неверно говорить, что

x % 2 == x & 1

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

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

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

Ссылки

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

Answer 2

Существует только простой способ найти по модулю 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)

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

Answer 3

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

Answer 4

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

(число) _база % база ^x

соответствует последним x цифрам (числа) _base .

Answer 5

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

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

Answer 6

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

int a = x % 7;

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

Answer 7

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

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

Answer 8

В этом конкретном случае (мод 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, и, конечно, менее читабелен.

Answer 9

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

Answer 10

Существует только простой способ найти по модулю 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)

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

@ Murali Любые такие методы для n% [(2 ^ 16) +1] = 65537. Я имею в виду n% (2 ^ k) +1, который является простым.