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

Question

1. Как мод степени 2 работает только с младшими битами двоичного числа (1011000111011010)?
2. Что это за число 2 для степени 0, 2 для степени 4?
3. Какое отношение степени 2 имеет отношение к оператору по модулю?Обладает ли оно специальным свойством?
4. Может ли кто-нибудь дать мне пример?

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

Answer 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 дает вам две последние цифры и т. Д.

Answer 2

Что он имеет в виду, это:

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

Когда у - степень 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

Answer 3

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

  334 % 10 = 4
  12345 % 10 = 5

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

  334 % 100 = 34
  12345 % 100 = 45

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

Answer 4

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

Пример:

      x = 10101010110101110
x mod 4 = 00000000000000010

Answer 5

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

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