Мод мощности 2 по побитовым операторам?

  • Как mod of power of 2 работает только с битами младшего разряда двоичного числа (1011000111011010)?
  • Что это за номер mod 2 для питания 0, 2 для питания 4?
  • Какая сила 2 связана с оператором modulo? Имеет ли он особое свойство?
  • Может ли кто-нибудь дать мне пример?

Инструктор говорит: "Когда вы берете что-то модное до 2, вы просто берете бит младшего порядка". Я слишком боялся спросить, что он имел в виду =)

Ответы

Ответ 1

Он имел в виду, что принятие number mod 2^n эквивалентно удалению всех, кроме n бит наименьшего порядка (самый правый) number.

Например, если n == 2,

number      number mod 4
00000001      00000001
00000010      00000010
00000011      00000011
00000100      00000000
00000101      00000001
00000110      00000010
00000111      00000011
00001000      00000000
00001001      00000001
etc.

Иными словами, number mod 4 совпадает с number & 00000011 (где & означает побитовое и)

Обратите внимание, что это работает точно так же в base-10: number mod 10 дает вам последнюю цифру числа в base-10, number mod 100 дает две последние цифры и т.д.

Ответ 2

Он имеет в виду, что:

x modulo y = (x & (y − 1))

Когда y является степенью 2.

Пример:

0110010110 (406) modulo
0001000000 (64)  =
0000010110 (22)
^^^^<- ignore these bits

Используя ваш пример сейчас:

1011000111011010 (45530) modulo
0000000000000001 (2 power 0) =
0000000000000000 (0)
^^^^^^^^^^^^^^^^<- ignore these bits

1011000111011010 (45530) modulo
0000000000010000 (2 power 4) =
0000000000001010 (10)
^^^^^^^^^^^^<- ignore these bits

Ответ 3

Рассмотрим, когда вы берете число по модулю 10. Если вы это сделаете, вы просто получите последнюю цифру числа.

  334 % 10 = 4
  12345 % 10 = 5

Аналогично, если вы принимаете число по модулю 100, вы просто получите последние две цифры.

  334 % 100 = 34
  12345 % 100 = 45

Итак, вы можете получить по модулю силы два, посмотрев на его последние цифры в двоичном формате. Это то же самое, что делать побитовое и.

Ответ 4

Modulo в целом возвращает остаток от значения после деления. Таким образом, x mod 4, например, возвращает 0, 1, 2 или 3 в зависимости от x. Эти возможные значения могут быть представлены с использованием двух битов в двоичном формате (00, 01, 10, 11). Другой способ сделать x mod 4 - просто установить все биты на ноль в x, за исключением последних двух.

Пример:

      x = 10101010110101110
x mod 4 = 00000000000000010

Ответ 5

Отвечая на ваши конкретные вопросы:

  • mod - оператор остатка. Если применить к серии чисел x в 0, 1,..., то x mod n будет 0, 1,..., n-1, 0, 1,..., n-1, ad infinitum. Когда ваш модуль n равен 2, тогда x mod n будет подсчитываться в двоичном формате от 0 до n-1, обратно до 0, до n-1 и т.д.; для модуля n, который выглядит как двоичный 01xxxxx, x mod n будет циклически проходить через каждый из этих младших битов xxxxx.
  • binary 1011000111011010 mod 1 равно 0 (mod 2 ^ 0 дает последние нулевые биты, все mod 1 равно нулю). двоичный код 1011000111011010 mod двоичный 10000 равен 1010 (mod 2 ^ 4 дает последние четыре бита).
  • Разделение и остальная часть двоичного числа по степеням двух особенно эффективны, поскольку он просто сдвигается и маскируется; математически это ничего особенного.
  • Пример: см. ответ на вопрос 2.