Побитово и вместо оператора модуля
Мы знаем, что, например, по модулю степени двух можно выразить так:
x % 2 inpower n == x & (2 inpower n - 1).
Примеры:
x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7
Как насчет общей некомпетентности двух чисел?
Скажем так:
х% 7==?
10 ответов
Во-первых, на самом деле не совсем правильно говорить, что
x % 2 == x & 1
Простой контрпример: x = -1, На многих языках, включая Java, -1 % 2 == -1, То есть, % не обязательно традиционное математическое определение по модулю. Java называет это "оператором остатка", например.
Что касается побитовой оптимизации, то в побитовой арифметике "легко" можно сделать только модульные степени двух. Вообще говоря, только по модулю степеней базы b можно "легко" сделать с помощью представления чисел в базе b.
В базе 10, например, для неотрицательных N, N mod 10^k просто берет наименее значимый k цифры.
Рекомендации
Существует только простой способ найти по модулю 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 цифрам (числа)основания.
Существуют модули, отличные от степеней 2, для которых существуют эффективные алгоритмы.
Например, если x равно 32 битам без знака int, то 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. Теперь рассмотрим x == ki: если в k были какие-либо "0" биты, то есть некоторые i, больше 0, которые ki может быть выражено только с 1 битами в этих позициях. (Например, 1011 (11) должен стать 0111 (7), когда из него вычтено 100 (4), в этом случае бит 000 становится равным 100, когда i = 4.) Если бит из выражения k должен измениться с нуля чтобы один представлял ki, тогда он не может правильно вычислить 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, вы можете изменить любые битовые конфигурации на другие битовые конфигурации (т. Е. Этот набор операторов "функционально завершен"). Однако для таких операций, как модуль, общая формула была бы достаточно сложной, я бы даже не стал пытаться ее воссоздать.
Существует только простой способ найти по модулю 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, который является простым.