Что такое поразрядная конъюнкция
Каждое целое число в памяти представлено в виде определенного количества разрядов. И операции сдвига позволяют сдвинуть битовое представление числа на несколько разрядов вправо или влево. Операции сдвига применяются только к целочисленным операндам. Есть две операции:
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
Наши условия использования и конфиденциальности
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.