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

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

  • автор:

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

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

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 — 2024. Stepik

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

Get it on Google Play

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

ПОРАЗРЯДНАЯ КОНЪЮНКЦИЯ

�� Что означает операция поразрядной конъюнкции? 14 & 5 = 1100 & 0101 = 0100 = 8 — вот и всё.

�� Для выражения (‘x & A = 0’ —> ‘x & 13 = 0’) v ‘x & 23 = 23 0’ найти наименьшее А, чтобы выражение принимало значение 1 для всех х

�� Преобразуем запись.
Пусть ‘x & m = 0’ = Z(m), тогда:
(Z(A) —> Z(13)) v Z(23) = -Z(A) v Z(13) v Z(23)

Z(13) = Либо у числа х не должно быть битов
Z(23) = Либо у числа х не должно быть битов

К примеру для х = 8 выражение будет истинным, потому что, хоть Z(13) = 0, Z(23) = 1
-Z(A) = Либо у числа x есть биты там же, где они есть у A:

�� Какое A надо взять, чтобы оно дополняло условия Z(13) или Z(23)

если А = 1, тогда ЛЮБОЕ нечётное число (у всех у них есть бит 1) будет -Z(A) = 1 — значит и общее выражение будет истинно.

Биты в составе -Z сводят на нет действие битов в Z(13) или Z(23).

�� Какой надо взять наименьший A, чтобы не осталось ‘активных’ битов либо в Z(13) либо в Z(23)? Ответ: А = 13

Логические высказывания

Ранее речь уже шла о том, что под логической переменной может подразумеваться любое высказывание, которое мы можем определить как ложное или истинное. В задании №15 ЕГЭ по информатике, которому посвящен данный раздел теории, логической переменной может быть, например, принадлежность точки некоторому отрезку или справедливость неравенства. Например, переменная x > 10 будет Истинна (т.е. равна 1) для всех чисел, которые строго больше 10, и Ложна (т.е. равна 0) для всех остальных. А переменная B ∈ [2; 4] будет Истинна (т.е. равна 1) только для чисел, расположенных между 2 и 4, и Ложна (т.е. равна 0) для всех прочих.

Для работы с заданием №15 необходимо хорошо разбираться в двух аспектах. Первый – это работа с математической составляющей, которой посвящен урок «Математика в информатике» (см. соответствующий раздел теории). Второй аспект – это преобразование логических выражений, о чем и пойдет речь в тексте ниже.

Формулы де-Моргана. Два главных выражения
Формулами де-Моргана называются две формулы, которые выглядят следующим образом:
¬(A /\ B) = ¬A \/ ¬B и ¬(A \/ B) = ¬A /\ ¬B

Эти выражения справедливы абсолютно всегда и используются, чтобы раскрывать инверсию перед скобкой. Чтобы убедиться, что эти формулы равносильны, достаточно построить для них таблицы истинности. Для первой формулы:

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

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