Решение задач с поразрядными операциями — КиберПедия 

Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...

История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...

Решение задач с поразрядными операциями

2018-01-29 662
Решение задач с поразрядными операциями 0.00 из 5.00 0 оценок
Заказать работу

Для решения этих задач удобно применять метод, предложенный А.В. Здвижковой (г. Армавир) и обоснованный автором[2]. Введём обозначения

Это означает, что если истинно , то это равносильно тому, что истинно . Для сокращения записи вместо будем писать просто .

Пусть в двоичной записи числа K бит с номером i, обозначаемый как ki, равен 1. Если при этом для некоторого x выполнено условие , то соответствующий i -й бит в двоичной записи числа x равен нулю, так как должно выполняться условие .

Для преобразования выражений полезно следующее свойство:

где «or» означает поразрядную дизъюнкцию между двумя натуральными числами. Для доказательства предположим, что в двоичной записи числа K биты с номерами i 1, i 2, …, iq равны 1, а остальные равны 0; а в двоичной записи числа M биты с номерами j 1, j 2, …, jp равны 1, а остальные равны 0. Истинность выражения в левой части означает, что все биты числа x, входящие во множества BK = { i 1, i 2, …, iq } и BM = { j 1, j 2, …, jp } одновременно равны нулю. Поэтому любая комбинация битов из этих множеств тоже равна нулю. Это справедливо, в том числе, и для множества, которое представляет собой объединение множеств BK и BM, то есть, для множества единичных битов числа K or M.

Самый важный результат можно сформулировать так:

Условие истинно для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.

Доказательство. Пусть в двоичной записи числа K биты с номерами i 1, i 2, …, iq равны 1, а остальные равны 0. Пусть также истинно для некоторого x, это значит, что в числе x биты с теми же номерами – нулевые. Если все единичные биты двоичной записи числа M входят во множество BK = { i 1, i 2, …, iq }, то истинно и высказывание , а следовательно – высказывание (1 ® 1 = 1). Если же хотя бы один бит двоичной записи числа M не входит во множество BK (пусть это будет бит с номером j), то для тех х, у которых все биты из множества BK нулевые, а бит j равен 1, выполняется , но не выполняется , так что высказывание ложно.

Для упрощения выражений полезен следующий результат:

Условие при любых натуральных K, M и N ложно для некоторых натуральных значений x.

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

.

Вторая импликация в правой части ложна хотя бы для некоторых x, поскольку из того, что некоторые биты числа x равны нулю (выполняется ) совершенно не следует, что какие-то другие (или те же самые) биты того же числа ненулевые (выполняется ). Строгое доказательство дано в статье, ссылка на которую приведена в сноске на предыдущей странице.

Метод, предложенный А.В. Здвижковой заключается в следующем:

1) упростить заданное выражение, сведя его к импликации, в которой нет инверсий

2) применить полученные выше результаты для нахождения всех подходящих значений неизвестного числа a, включая минимальное и максимальное значения.

Этот же метод можно применить и в том случае, когда результат поразрядной операции «И» сравнивается не с нулём, а с другими числами. Например, рассмотрим выражение R = (x &125= 5). Переведём числа в двоичную систему:

6 5 4 3 2 1 0

125 = 11111012

5 = 1012.

Истинность R означает, что

1) биты числа x с номерами 3, 4, 5 и 6 равны 0;

2) биты числа x с номерами 0 и 2 равны 1.

С учётом введённых выше обозначений можно записать эквивалентное условие:

R = (x &125= 5) Û .

Применяя операцию «НЕ» к этому выражению, получаем

= (x &125¹ 5) Û Û .

В общем виде для чисел b и c, таких, что множество единичных битов числа c входит во множество единичных битов числа b, имеем

R = (x & b = c) Û

= (x & b ¹ c) Û .

где 1, 2, …, q – степени числа 2, которые соответствуют единичным битам числа c. Например, для
c = 5 = 1012 имеем 1 = 22 = 4, 2 = 20 = 1.

Пример задания:

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

(x &125¹ 1) Ú ((x & 34 = 2) ® (x & a = 0))


Поделиться с друзьями:

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...

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

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



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.007 с.