Что такое поразрядная конъюнкция
Перейти к содержимому

Что такое поразрядная конъюнкция

  • автор:

Что такое поразрядная конъюнкция

Каждое целое число в памяти представлено в виде определенного количества разрядов. И операции сдвига позволяют сдвинуть битовое представление числа на несколько разрядов вправо или влево. Операции сдвига применяются только к целочисленным операндам. Есть две операции:

int a = 2 > 3; // 10000 на три разряда вправо = 10 - 2

Число 2 в двоичном представлении 10. Если сдвинуть число 10 на два разряда влево, то получится 1000, что в десятичной системе равно число 8.

Число 16 в двоичном представлении 10000. Если сдвинуть число 10 на три разряда вправо (три последних разряда отбрасываются), то получится 10, что в десятичной системе представляет число 2.

Поразрядные операции

Поразрядные операции также проводятся только над разрядами целочисленных операндов:

  • & : поразрядная конъюнкция (операция И или поразрядное умножение). Возвращает 1, если оба из соответствующих разрядов обоих чисел равны 1
  • | : поразрядная дизъюнкция (операция ИЛИ или поразрядное сложение). Возвращает 1, если хотя бы один из соответствующих разрядов обоих чисел равен 1
  • ^ : поразрядное исключающее ИЛИ. Возвращает 1, если только один из соответствующих разрядов обоих чисел равен 1
  • ~ : поразрядное отрицание. Инвертирует все разряды операнда. Если разряд равен 1, то он становится равен 0, а если он равен 0, то он получает значение 1.
int a = 5 | 2; // 101 | 010 = 111 - 7 int b = 6 & 2; // 110 & 010 = 10 - 2 int c = 5 ^ 2; // 101 ^ 010 = 111 - 7 int f = 12; // 00001100 int d = ~f; // 11110011 или -13 printf("a = %d \n", a); printf("b = %d \n", b); printf("c = %d \n", c); printf("d = %d \n", d);

Например, выражение 5 | 2 равно 7. Число 5 в двоичной записи равно 101, а число 2 — 10 или 010. Сложим соответствующие разряды обоих чисел. При сложении если хотя бы один разряд равен 1, то сумма обоих разрядов равна 1. Поэтому получаем:

1 0 1
0 1 0
1 1 1

В итоге получаем число 111, что в десятичной записи представляет число 7.

Возьмем другое выражение 6 & 2 . Число 6 в двоичной записи равно 110, а число 2 — 10 или 010. Умножим соответствующие разряды обоих чисел. Произведение обоих разрядов равно 1, если оба этих разряда равны 1. Иначе произведение равно 0. Поэтому получаем:

1 1 0
0 1 0
0 1 0

Получаем число 010, что в десятичной системе равно 2.

Теперь рассмотрим последний пример — инверсию числа.

Представление отрицательных чисел

Для записи чисел со знаком в Си применяется дополнительный код (two’s complement), при котором старший разряд является знаковым. Если его значение равно 0, то число положительное, и его двоичное представление не отличается от представления беззнакового числа. Например, 0000 0001 в десятичной системе 1.

Если старший разряд равен 1, то мы имеем дело с отрицательным числом. Например, 1111 1111 в десятичной системе представляет -1. Соответственно, 1111 0011 представляет -13.

Чтобы получить из положительного числа отрицательное, его нужно инвертировать и прибавить единицу:

int x = 12; int y = ~x; y += 1; printf("y = %d \n", y); // y=-12

Что такое поразрядная конъюнкция

Скачай курс
в приложении

Перейти в приложение
Открыть мобильную версию сайта

© 2013 — 2023. Stepik

Наши условия использования и конфиденциальности

Get it on Google Play

Public user contributions licensed under cc-wiki license with attribution required

Поразрядная конъюнкция задачи 3

Давайте разберем поразрядную конъюнкцию. Это задача, которая несколько лет была на ЕГЭ и на всех СтатГрадах, и она как-то исторически вызывает неприятные эмоции у учеников. На самом деле, ничего сложного.

Что такое поразрядная конъюнкция? Это перевод чисел в двоичную систему, а потом разряд с разрядом умножаем. Например, 7 х 4. 7 перевожу в двоичную систему – 1 1 1. 4 перевожу в двоичную систему – 1 0 0. И умножаю разряд с разрядом – 111 х 100=100.

Давайте порешаем задачи.

«Введем выражение М & К, обозначающие поразрядную конъюнкцию М и К (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число А, такое, что выражение

Начнем с короткого обозначения. Выражение Х х 56 =0 обозначим как Х56, в коротком виде. Первое уравнение принимает вид . Нам нужно найти наименьшее натуральное А.

Избавляемся от импликации. Формулу напоминать не буду, наверное, ее уже все знают наизусть.

Теперь мой любимый прием – известная часть пусть будет нулем (0), тогда искомая часть обязана быть единицей (1)

На какой-то момент я забываю про предметную область, я занимаюсь преобразованием до системы.

С нулем работать не очень приятно, поэтому сделаю отрицание и будет единица.

На что мне надо умножить 48, чтобы получились одни нули?

У X должны быть в первом разряде нули, чтобы обнулить единицы у 48, а остальное не важно

И те же самые X я должна умножить на 56 и не получить ноль. Чтобы не получить ноль, мне нужно здесь поставить единицу, чтобы она зацепила единицу от 56

Дальше может стоять что угодно. Все такие X являются решением этого уравнения.

Второе уравнение говорит, что все такие X (001…) нужно умножить на А и не получить ноль.

На первой и второй позиции у А может стоять что угодно. Три последние позиции тоже без разницы. Нужно поймать единственную единицу.

Если у А будет здесь единица, я умножу А и Х и ноль не получу. Вот такое А должно быть.
Нужно найти наименьшее. Тогда остальные пусть будут нули.

А это значит 8 в десятичной системе.

Благодарим за то, что пользуйтесь нашими материалами. Информация на странице «Поразрядная конъюнкция задачи 3» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ. Чтобы успешно сдать нужные и поступить в ВУЗ или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими статьями из разделов нашего сайта.

Публикация обновлена: 05.10.2023

ПОБИТОВЫЕ ОПЕРАТОРЫ В PYTHON (поразрядная конъюнкция и другие)

Побитовые операторы работают с данными в битовом (двоичном) формате и действуют бит за битом.

Всего этих операторов шесть:

& побитовое И (побитовое умножение, поразрядная конъюнкция)
| побитовое ИЛИ (побитовое сложение, поразрядная дизъюнкция)
^ побитовое исключающее ИЛИ (побитовая сумма по модулю два, XOR)
~ побитовое НЕ (побитовая инверсия, поразрядная инверсия)
> побитовый сдвиг вправо

Битовые операции используются в криптографических алгоритмах, сетевых технологиях и др.

Побитовое И (поразрядная конъюнкция)

Пример с поразрядной конъюнкцией:

>>> 10 & 6 2 >>> 

Число 10 в двоичной системе — 1010, а число 6 — 110.
После поразрядного перемножения получим 0010. В десятичной системе это 2.

10 1 0 1 0
6 0 1 1 0
2 0 0 1 0

Побитовое ИЛИ (поразрядная дизъюнкция)

Пример с поразрядной дизъюнкцией:

>>> 10 & 6 14 >>> 

Число 10 в двоичной системе — 1010, а число 6 — 110.
После поразрядного сложения получим 1110. В десятичной системе это 14.

10 1 0 1 0
6 0 1 1 0
14 1 1 1 0

Побитовое исключающее ИЛИ (XOR)

Принцип поразрядного исключающего ИЛИ

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0

Пример с поразрядным исключающим ИЛИ:

>>> 10 ^ 6 12 >>> 

Число 10 в двоичной системе — 1010, а число 6 — 110.
После поразрядного сложения по модулю два получим 1100. В десятичной системе это 12.

10 1 0 1 0
6 0 1 1 0
12 1 1 0 0

Побитовое НЕ

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

~x = -(x + 1)

Пример с поразрядным НЕ:

>>> ~10 -11 >>> 

Еще пример с поразрядным НЕ:

>>> ~-10 9 >>> 

Побитовый сдвиг влево

Позволяет сдвинуть битовое представление числа на несколько разрядов влево. Операции сдвига применяются только к целым числам.

Пример сдвига влево на 2 разряда:

>>> 10 40 >>> 

Число 10 в двоичной системе — 1010.
После поразрядного сдвига влево на два разряда получим 101000 (справа добавится два разряда с нулями). В десятичной системе это 40.

Побитовый сдвиг вправо

Позволяет сдвинуть битовое представление числа на несколько разрядов вправо. Операции сдвига применяются только к целым числам.

Пример сдвига вправо на 2 разряда:

>>> 10 >> 2 2 >>> 

Число 10 в двоичной системе — 1010.
После поразрядного сдвига вправо на два разряда получим 10 (два правых разряда просто исчезнут). В десятичной системе это 2.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *