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

Ответ 1

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

x % 2 == x & 1

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

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

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

Ссылки

• JLS 15.17.3 Оператор останова%
• Википедия/Работа в режиме Modulo

Ответ 2

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

Ответ 3

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

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

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

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

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

Ответ 4

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

(число) _base% base ^x

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

Ответ 5

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

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

Ответ 6

for x % 7 = ?

x % 7 == (x+x/7) & 7

отлично работает в java.

int a = x % 7 ;

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

оба утверждения одинаковы.

Ответ 7

Не использовать побитовый и (&) оператор в двоичном формате, нет. Эскиз доказательства:

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

Ответ 8

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

Ответ 9

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

Ответ 10

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

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

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

n% 2 ^ я = n и (2 ^ я - 1)

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

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