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

91

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

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

Примеры:

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

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

Скажем:

x% 7 ==?

Дато Датуашвили
источник
8
@Neil - Modulo и Binary И это довольно фундаментальные операции, я предполагаю, что они примерно одинаковы на любом компьютерном языке.
Джеймс Колпак,
1
Я действительно немного устал от того, что не вижу опубликованного языка :) Хотя обычно я предполагаю, что если они не указывают, я предполагаю, что это означает C ++ или C. Интересно, насколько это правда ...
Гарет Клаборн
1
Просто для тех, кто изо всех сил пытается понять это, взгляните на stackoverflow.com/a/13784820/1414639 . Да, и в JS с V8 я получаю очень небольшой прирост производительности за счет использования побитовых операторов.
Барди Харбороу,
1
@JamesKolpack Поразрядная операция может выполняться на ЦП НАМНОГО быстрее, чем по модулю. Фактически, распространенный трюк сборки для обнуления регистра заключается в выполнении XOR с самим собой (из-за этого факта). В настоящее время компилятор может оптимизировать по модулю степени двойки, но я не знаю,
Кайзер Кейстер

Ответы:

70

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

x % 2 == x & 1

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

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

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

Ссылки

полигенные смазочные материалы
источник
1
-1 = -1 (mod 2), не уверен, к чему вы клоните - вы имеете в виду, что это не то же самое, что остаток IEEE 754?
BlueRaja - Дэнни Пфлугофт
2
@BlueRaja: общий остаток для -1 в модуле 2 равен 1. en.wikipedia.org/wiki/Modular_arithmetic#Remainders
polygenelubricants
@BlueRaja: если вы разрешаете отрицательные числа, то, в основном, вы можете быть уверены (особенно потому, что язык не упоминается), так это то (a / b) / b + a % b == a, что для операторов C-типа целые числа a и b, b ненулевые, а также abs(a % b) < abs(b)с теми же условиями.
Дэвид Торнли
1
@DavidThornley - предположим, вы имеете в виду (a / b)* b + a % b == a.
sfjac
40

Есть только простой способ найти числа по модулю 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
голос ++; Отличная ссылка, спасибо за ссылку. Советую другим взглянуть, это стоит прочитать, даже если это немного сложно.
varzeak
ссылка - лучшая часть ответа.
Амит Кумар
n% 2 ^ i = n & (1 << i - 1)
Картик Сингх
18

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

VeeArr
источник
2
Если вы работаете на тернарной архитектуре, это немного меняет ситуацию ... однако шансы равны нулю.
Noldorin
Мне нравится, как вы это формулируете: « это немного меняет ситуацию »
j3141592653589793238
12

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

(число) основание % основание x

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

Jdmichal
источник
5

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

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

Дэвид Харрис
источник
4

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

int a = x % 7;

int a = (x + x / 7) & 7;
ashuwp
источник
3
Не работает для 10% 2 = 0. (10 + 10/2) & 2 = 15 & 2 = 2, аналогично 10% 6 = 4. (10 + 10/6) & 6 = 11 & 6 = 2
Шрирам Мурали
10
Кроме того, зачем вам делить, если вы не хотите использовать по модулю? AFAIK, инструкция по делению такая же, как и для получения остатка.
Horse SMith
2
@SriramMurali Это потому, что вы использовали четный мод, конечно, он не сработает, это обходной путь для нечетного, как сказал OP.
ylun.ca
3

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

Предположим, что существует такое значение 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 , но нет возможности для побитового логического значения и создания этого значения с учетом маски.

Хит Ханникатт
источник
2

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

Эрик Бейнвилл
источник
1

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

Ли Райан
источник