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

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

Поразрядная конъюнкция. Задача №18 из ЕГЭ по информатике.

Задача №18 является заданием повышенной сложности и проверят знание основных понятий и законов математической логики. Это задание за многолетнюю историю ЕГЭ претерпевало ряд изменений. Сначала это была задача на нахождение минимальной/максимальной длины отрезка, затем мы работали с элементами множеств, далее появились битовые цепочки и делители, наконец, последнее на сегодняшний день – поразрядные конъюнкции.

Рекомендуемое время для 18-го задания – 3 минуты. Поэтому, хотя эта задача, как и все остальные, подробно разобрана на сайте http://kpolyakov. spb. ru/school/ege. htm , многие учителя информатики и все, кто связан с подготовкой к сдаче ЕГЭ, продолжают искать более простые алгоритмы решения этой задачи.

Есть решения, основанные на использовании построения таблиц истинности. Интересная статья опубликована в журнале «Потенциал» №2 2016, также посвящена разбору 18-го задания. На летней школе в МГУ для учителей информатики выступление сотрудника ф-та ВМК , было встречено слушателями аплодисментами. Предложенный им метод основан на анализе логического выражения. Посмотреть презентацию можно по ссылке http://www. vmk-edu. ru/news/343 .

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

Итак, во всех заданиях на поразрядную конъюнкцию ищут либо наименьшее, либо наибольшее десятичное число А, такое, что заданное выражение будет тождественно истинно при любом натуральном значении переменной Х. Рассмотрим оба вида заданий1.

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

(X & 49 ? 0) > ((X & 33 = 0) > (X & A ? 0))

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?

Решение.
Сначала преобразуем выражение, избавившись от импликации по формуле A>B = A+B

Получим выражение: (X & 49 ? 0) + (X & 33 = 0) + (X & A ? 0) = 1

Это, в свою очередь, можно переписать так:
(X & 49 = 0) + (X & 33 ? 0) + (X & A ? 0) = 1

Всё выражение будет истинным, когда хотя бы одна из трёх его составляющих будет истинна.

Перейдём к двоичной записи чисел.

Биты 5 4 3 2 1 0

Теперь будем побитово подбирать такое минимальное А, чтобы наше выражение было верным.

Рассмотрим младшие биты. Для 49: 1=0 – неверно; для 33: 1? 0 – верно. Поскольку X & 33 ? 0 в младшем бите даёт нам истину, то в младший бит А мы вольны поставить что угодно: хоть «0», хоть «1». Поскольку мы ищем минимальное значение, ставим «0».

Читайте также:  Что такое else в паскале

Аналогично рассматриваем следующий бит. Для 49: 0=0 сразу даёт истину, так что соответствующий бит А опять равен «0».

Ещё два бита дают уже рассмотренную ситуацию, получаем:

Рассматриваем 4-ый бит: для 49: 1=0 – неверно; для 33: 0? 0 – неверно. Значит в 4-ый бит А мы должны поставить «1», так как по условию X & A ? 0

Последний бит даёт истину для 33: 1? 0, поэтому 5-ый бит А равен «0»

Итак, получили А=100002=1610

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

(X & A ? 0 ) > ((X & 20 = 0) > (X & 5 ? 0))

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?

Как и в задании на поиск минимального значения сначала преобразуем выражение. Получим:

(X & A = 0 ) + (X & 20 ? 0) + (X & 5 ? 0)=1

Перейдём к двоичной записи чисел.

Так же как и в 1-ом задании, будем побитово рассматривать каждое выражение. Если какое-либо из них даёт истину, то в соответствующий бит А мы можем поставить что угодно, но так как мы ищем максимальное значение, то будем ставить «1». В противном случае, бит А должен быть равен «0», так как истинность всего выражения должна будет обеспечить конъюнкция X & A = 0.

0-ые биты. Для 20: 0 ? 0 – ложь, для 5: 1 ? 0 – истина. Бит А равен «1»

1-ые биты. Для 20: 0 ? 0 – ложь, для 5: 0 ? 0 – ложь. Бит А равен «0»

2-ые биты. Для 20: 1 ? 0 – истина, для 5: 1 ? 0 – истина. Бит А равен «1»

3-и биты. Для 20: 0 ? 0 – ложь, для 5: 0 ? 0 – ложь. Бит А равен «0»

4-ые биты. Для 20: 1 ? 0 – истина, для 5: 0 ? 0 – ложь. Бит А равен «1»

Таким способом задания подобного вида решаются быстро, можно уложиться в рекомендуемые три минуты. Здесь приведено подробное объяснение, но при решении достаточно записать все числа в двоичной записи друг под другом и подбирать биты А в зависимости от удовлетворения равенства или неравенства нулю, и учитывая максимальное или минимальное значение А мы ищем.

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

Сдвигает битовое представление числа, представленного первым операндом, влево на определенное количество разрядов, которое задается вторым операндом.

Читайте также:  Система виртуализации hyper v

Сдвигает битовое представление числа вправо на определенное количество разрядов.

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

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

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

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

& : поразрядная конъюнкция (операция И или поразрядное умножение). Возвращает 1, если оба из соответствующих разрядов обоих чисел равны 1

| : поразрядная дизъюнкция (операция ИЛИ или поразрядное сложение). Возвращает 1, если хотя бы один из соответствующих разрядов обоих чисел равен 1

^ : поразрядное исключающее ИЛИ. Возвращает 1, если только один из соответствующих разрядов обоих чисел равен 1

: поразрядное отрицание. Инвертирует все разряды операнда. Если разряд равен 1, то он становится равен 0, а если он равен 0, то он получает значение 1.

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

1 1
1
1 1 1

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

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

1 1
1
1

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

Логические операции

Эти операции используются при построении сложных логических выражений. В эту группу входят 3 операции:

· !— логическое отрицание (логическое НЕ);

· || — дизъюнкция (логическое ИЛИ).

Первая операция унарная, две остальные – бинарные. Операнды – выражения любого арифметического типа данных, значения которых интерпретируются как значения логического типа (отличное от 0 значение – true; 0 — false) . Результат этих операций — логического типа.

Правила записи и результаты выполнения логических операций приведены в следующей таблице:

a b !a a && b a || b

Пусть, например, имеется математическое неравенство: 0 x) или (х > 0) && (x x > 10должно выглядеть следующим образом: (0 > x) || (10 10).

Особенностью выполнения операций && и || является то, что второй операнд (в правой части операций) вычисляется не всегда. Он вычисляется только в том случае, если значения первого операнда недостаточно для получения результата операций && или ||.

Читайте также:  Как открыть файл indd

Например. Если в выражении (a + 10) && (b – 1) значение первого (левого) операнда a + 10равно (false) (это будет при значении a = -10), то вычисление второго (правого) операнда b – 1не выполняется, так как и без его вычисления, значение результата операции &&уже известно – это false. А в выражении (a + 10) || (b – 1) второй операнд не будет вычисляться в том случае, если первый операнд не равен – в этом случае результат операции ||и так уже известен – он равен true.

Побитовые операции рассматривают операнды как упорядоченные наборы битов,
каждый бит может иметь одно из двух значений — 0 или 1 (наборы двоичных значений). Такие операции позволяют программисту манипулировать значениями отдельных битов. Объект, содержащий набор битов, иногда называют битовым вектором. Он позволяет компактно хранить набор флагов — переменных, принимающих значение "да" "нет".

Операции сдвига> — бинарные операции. Операнды целого типа. Результат также целого типа. Формат записи:

сдвиг влево

>> —сдвиг вправо

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

Значение второго операнда должно быть больше или равно 0 и меньше количества двоичных разрядов первого операнда, иначе результат выполнения операций не гарантирован (зависит от реализации, но обычно равен 0).

unsigned a = 20, n = 3, r;

r = a > n;

cout > n

Значение r: 0 0 … 0 0 0 0 0 0 0 1 0 = 2

Операция сдвига влево осуществляет перемещение битов левого операнда a в сторону больших разрядов на количество разрядов, равное значению правого операнда n. Это эквивалентно умножению значения a на 2 в степени n(20 * 8 = 160).

Операция сдвига вправо осуществляет перемещение битов левого операнда a в сторону меньших разрядов на количество разрядов, равное значению правого операнда n. Это эквивалентно делению значения a на 2 в степени n(целочисленное деление 20 / 8 = 2).

Используя операцию сдвига влево очень просто получить любую целую степень двойки в диапазоне степеней равной количеству двоичных разрядов правого операнда без 1. Например, так:

Поразрядные логические операции

К этой группе операций относятся:

— побитовое отрицание (побитовое НЕ) — унарная операция;

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

· ^ — побитовое исключающее ИЛИ — бинарная операция.

Операндами этих операций целочисленных типов данных. Результат также целочисленный.

Операция побитовое отрицание (

) осуществляет инвертирование всех байтов двоичного представления своего операнда. Например:

int a = 14, r;

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: При сдаче лабораторной работы, студент делает вид, что все знает; преподаватель делает вид, что верит ему. 9822 — | 7504 — или читать все.

Ссылка на основную публикацию
Что делать если отключился звук на компьютере
Мы зарегистрировали подозрительный трафик, исходящий из вашей сети. С помощью этой страницы мы сможем определить, что запросы отправляете именно вы,...
Фотографии купе в поезде
Интересный фотоотчет о поездке на одном из первых рейсов двухэтажных поездов. Смотрим далее, как все устроено внутри таких двухэтажных вагонов...
Фотография с самым большим разрешением в мире
Представляем вашему вниманию нашу подборку самых больших фотографий в мире. Для их просмотра вам будет необходим FlashPlayer. Его можно скачать...
Что делать если полетели драйвера видеокарты
Распространенная ошибка в Windows 7 и реже в Windows 10 и 8 — сообщение «Видеодрайвер перестал отвечать и был успешно...
Adblock detector