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

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

analog = number1 & number2;

analog	Аналоговая переменная БД
number1	Числовое выражение
number2	Числовое выражение

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

/* присвоение 00000001, 00000011 */

Val = Num1 & Num2;

/* возвращает 1 (00000001) */

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

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

analog = number1 ^ number2;

analog	Аналоговая переменная БД
number1	Числовое выражение
number2	Числовое выражение

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

/* присвоение 00000001, 00000011 */

Val = Num1 ^ Num2;

/* возвращает 2 (00000010) */

Дизъюнкция

Дизъюнкция — поразрядное логическое ИЛИ. Операция используется для сравнения каждого бита первого операнда с соответствующим битом второго операнда. Если хотя бы один из сравниваемых битов равен единице, результирующий бит устанавливается в единицу.

analog = number1 | number2;

analog	Аналоговая переменная БД
number1	Числовое выражение
number2	Числовое выражение

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

/* присвоение 00000001, 00000011 */

Val = Num1 | Num2;

/* возвращает 3 (00000011) */

Логическое И

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

discrete = number1 && number2;

discrete	Дискретная переменная БД
number1	Числовое выражение
number2	Числовое выражение

Val = Num1 && Num2;

Логическое ИЛИ

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

Побитовые операции

Побитовые операции (англ. bitwise operations) — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: логические операции и побитовые сдвиги.

Содержание

Принцип работы [ править ]

Логические побитовые операции [ править ]

Битовые операторы И [math](AND,\ \&)[/math] , ИЛИ [math](OR,\ \mid)[/math] , НЕ [math](NOT,\ \sim)[/math] и исключающее ИЛИ [math](XOR,\ $\textasciicircum$,\ \oplus)[/math] используют те же таблицы истинности, что и их логические эквиваленты.

Побитовое И [ править ]

Побитовое И используется для выключения битов. Любой бит, установленный в [math]0[/math] , вызывает установку соответствующего бита результата также в [math]0[/math] .

&
&	11001010 11100010
11000010

Побитовое ИЛИ [ править ]

Побитовое ИЛИ используется для включения битов. Любой бит, установленный в [math]1[/math] , вызывает установку соответствующего бита результата также в [math]1[/math] .

\|
\|	11001010 11100010
11101010

Побитовое НЕ [ править ]

Побитовое НЕ инвертирует состояние каждого бита исходной переменной.

Побитовое исключающее ИЛИ [ править ]

Исключающее ИЛИ устанавливает значение бита результата в [math]1[/math] , если значения в соответствующих битах исходных переменных различны.

^
^	11001010 11100010
00101000

Побитовые сдвиги [ править ]

Операторы сдвига [math]\lt \lt [/math] и [math]<\gt \gt >[/math] сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в двоичном дополнительном коде и необходимо поддерживать знаковый бит).

Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.

В языке программирования Java существует также оператор беззнакового битового сдвига вправо [math]\gt \gt \gt [/math] . При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.

Применение [ править ]

Сложные операции [ править ]

Определение знака числа [ править ]

Пусть дано число [math]x[/math] . Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа [math]x[/math] можно определить, выполнив сдвиг вправо на всю длину переменной:

Используя побитовые операции можно также узнать, различны ли знаки двух переменных [math]x[/math] и [math]y[/math] . Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство [math](x \oplus y) \lt 0[/math] будет верно в том случае, если числа [math]x[/math] и [math]y[/math] разного знака.

Вычисление модуля числа без использования условного оператора [ править ]

Пусть дано число [math]x[/math] . Если [math]x[/math] положительно, то [math]mask = 0[/math] , и [math](x + mask) \oplus mask = x[/math] . В случае, если [math]x[/math] отрицательно, [math]mask = -1[/math] . Тогда получается, что мы работаем с числом [math]x[/math] так, как будто оно представлено в коде со сдвигом с тем отличием, что у нас знаковый бит принимает значение [math]1[/math] для отрицательных чисел, а [math]0[/math] — для положительных.

Нахождение минимума и максимума из двух чисел без использования условного оператора [ править ]

Этот способ корректен только если можно утверждать, что величина [math](x — y)[/math] лежит между граничными значениями типа int.

Пусть даны числа [math]x[/math] и [math]y[/math] разрядности [math]n[/math] . Тогда если [math]x \lt y[/math] , то [math]((x — y) \gt \gt (n — 1)) = -1[/math] , а если [math]x \geqslant y[/math] , то [math]((x — y) \gt \gt (n — 1)) = 0[/math] . Выражение [math]((x — y) \& ((x — y) \gt \gt (n — 1))[/math] принимает значение [math]0[/math] , если [math]x \geqslant y[/math] , и [math](x — y)[/math] , если [math]x \lt y[/math] .

Проверка на то, является ли число степенью двойки [ править ]

Пусть дано число [math]x[/math] . Тогда, если результатом выражения [math](x\ \&\&\ !(x\ \&\ (x — 1)))[/math] является единица, то число [math]x[/math] — степень двойки.

Правая часть выражения [math](!(x\ \&\ (x — 1)))[/math] будет равна единице, только если число [math]x[/math] равно [math]0[/math] или является степенью двойки. Если число [math]x[/math] является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: [math]1\underbrace<0\dots0>_[/math] , где [math]n[/math] — показатель степени. Соответственно, выражение [math](x — 1)[/math] будет иметь вид [math]\underbrace<1\dots1>_[/math] , и [math]x\ \&\ (x — 1)[/math] равно [math]0[/math] .

Операция логического И в данном выражении отсекает тот случай, когда [math](x = 0)[/math] и не является степенью двойки, но при этом правая часть [math](!(x\ \&\ (x — 1)))[/math] равна единице.

Нахождение младшего единичного бита [ править ]

Пусть дано число [math]x[/math] и необходимо узнать его младший единичный бит.

Применим к числу [math]x[/math] побитовое отрицание, чтобы инвертировать значения всех его бит, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом [math]x[/math] , а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа [math](x\ \&\ (\sim x + 1))[/math] .

К такому же результату можно прийти, если сначала отнять от числа [math]x[/math] единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в [math]1[/math] , затем инвертировать результат и применить побитовое И с исходным числом [math](x\ \&\ \sim (x — 1))[/math] .

Нахождение старшего единичного бита [ править ]

Пусть дано число [math]x[/math] и необходимо узнать его старший единичный бит.

Рассмотрим некоторое число, представим его как [math]0\dots01b \dots b[/math] , где [math]b[/math] — любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на [math]1[/math] и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат [math]0\dots011b \dots b[/math] . Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на [math]2[/math] , то получим [math]0\dots01111b \dots b[/math] . При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций (зависит от разрядности числа) мы получим число вида [math]0\dots01\dots1[/math] . Тогда результатом выполнения действий [math]x — (x \texttt< \gt \gt >1)[/math] будет число, состоящее только из старшего бита исходного числа.

Циклический сдвиг [ править ]

Пусть дано число [math]x[/math] и надо совершить циклический сдвиг его битов на величину [math]d[/math] . Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на [math]d[/math] и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.

Подсчет количества единичных битов [ править ]

Для подсчета количества единичных битов в числе [math]x[/math] можно воспользоваться следующим алгоритмом:

Поскольку [math]5555_<16>[/math] равно [math]01010101 01010101_<2>[/math] , результатом операции [math]x\ \&\ 5555_<16>[/math] является число, в котором все нечетные биты соответствуют нечетным битам числа [math]x[/math] . Аналогично, результатом операции [math](x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 5555_<16>[/math] является число, в котором все нечетные биты соответствуют четным битам [math]x[/math] . Четные биты результата в обоих случаях равны нулю.

Мысленно разобьем двоичную запись нашего числа [math]x[/math] на группы по [math]2[/math] бита. Результатом операции [math]x\ \&\ 5555_ <16>+ (x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 5555_<16>[/math] будет такое число, что если разбить его двоичную запись на группы по два бита, значение каждой группы соответствует количеству единичных битов в соответствующей паре битов числа [math]x[/math] .

Аналогично, число [math]3333_<16>[/math] равно [math]00110011 00110011_<2>[/math] и операция [math]x = (x\ \&\ 3333_<16>) + (x\ \texttt<\gt \gt \gt >\ 2\ \&\ 3333_<16>)[/math] , примененная к результату, полученному на первом этапе, выполняет подсчет количества единичных битов в блоках по [math]4[/math] . В свою очередь, число [math]\texttt<0F0F>_<16>[/math] равно [math]00001111 00001111_<2>[/math] и операция [math]x = (x\ \&\ \texttt<0F0F>_<16>) + (x\ \texttt<\gt \gt \gt >\ 4\ \&\ \texttt<0F0F>_<16>)[/math] позволяет подсчитать число единичных бит в блоках по [math]8[/math] .

Теперь необходимо просуммировать числа, записанные в блоках по [math]8[/math] битов, чтобы получить искомую величину. Это можно сделать, домножив результат на [math]0101_<16>[/math] [math](1 00000001_<2>)[/math] . Ответ на задачу будет находиться в первых восьми битах произведения. Выполнив сдвиг вправо на [math]8[/math] (для шестнадцатибитных чисел), мы получим долгожданный ответ.

Заметим, что операция [math]x\ \&\ 55_ <16>+ (x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 55_<16>[/math] равносильна операции [math]x — (x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 55_<16>[/math] , в чем легко убедиться, рассмотрев все числа из двух бит.

В свою очередь, операцию [math](x\ \&\ \texttt<0F0F>_<16>) + ((x\ \texttt<\gt \gt \gt >\ 4)\ \&\ \texttt<0F0F>_<16>)[/math] можно заменить на [math](x + (x\ \texttt<\gt \gt \gt >\ 4))\ \&\ \texttt<0F0F>_<16>[/math] . Эта замена не повлияет на результат, так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок.

Таким образом, мы получили код, приведенный в начале раздела.

Разворот битов [ править ]

Чтобы получить биты числа [math]x[/math] , записанные в обратном порядке, применим следующий алгоритм.

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

Применение для решения задач [ править ]

Работа с битовыми масками [ править ]

Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение [math](\sim mask)[/math] , пересечение [math](mask_1\ \&\ mask_2)[/math] , объединение [math](mask_1 \mid mask_2)[/math] множеств, установить бит по номеру [math](mask \mid (1\ \texttt<\lt \lt >\ x))[/math] , снять бит по номеру [math](mask\ \&\ \sim(1\ \texttt<\lt \lt >\ x))[/math] .

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

Алгоритм Флойда [ править ]

Алгоритм Флойда–Уоршелла (англ. the Floyd–Warshall algorithm) — алгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма [math] \Theta(n^3) [/math] , также требует [math] \Theta(n^2) [/math] памяти.

Дерево Фенвика [ править ]

Дерево Фенвика (англ. Binary indexed tree) — структура данных, которая может выполнять следующие операции:

изменять значение любого элемента в массиве,
выполнять некоторую ассоциативную, коммутативную, обратимую операцию [math] \circ [/math] на отрезке [math] [i, j] [/math] .

Данная структура требует [math] O(n) [/math] памяти, а выполнение каждой операции происходит за [math] O(\log n) [/math] .

Функция, позволяющая делать операции вставки и изменения элемента за [math] O(\log n) [/math] , задается следующей формулой [math] F(i) = (i \And (i + 1)) [/math] . Пусть дан массив [math] A = [a_0, a_1, \ldots, a_][/math] . Деревом Фенвика называется массив [math] T [/math] из [math] n [/math] элементов: [math] T_i = \sum\limits_^ a_k[/math] , где [math] i = 0\ldots n — 1 [/math] и [math] F(i) [/math] — функция, которую мы определили ранее.

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

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Курс профессиональной переподготовки

Управление информационной средой на основе инноваций

Курс профессиональной переподготовки

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

Сейчас обучается 168 человек из 46 регионов

Курс повышения квалификации

Авторская разработка онлайн-курса

Сейчас обучается 88 человек из 43 регионов

«Домашнее обучение. Лайфхаки для родителей»

подготовка к ЕГЭ/ОГЭ и ВПР

по всем предметам 1-11 классов

«Такие разные дети: преимущества тьюторской позиции учителя»

Свидетельство и скидка на обучение каждому участнику

Дистанционные курсы для педагогов

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

5 910 242 материала в базе

«Интеграция современного искусства в детское творчество»

Свидетельство и скидка на обучение
каждому участнику

Ищем педагогов в команду «Инфоурок»

ЗП до 91 000 руб.

Гибкий график

Удаленная работа

Другие материалы

Информатика

Конспекты

12.09.2016

2518

3

Информатика

Рабочие программы

12.09.2016

409

0

Информатика

9 класс

Другие методич. материалы

Учебник: «Информатика», Босова Л.Л., Босова А.Ю.

Тема: Глава 1. Моделирование и формализация

12.09.2016

1168

5

Информатика

5 класс

Другие методич. материалы

12.09.2016

11202

130

Информатика

8 класс

9 класс

Другие методич. материалы

Учебник: «Информатика», Босова Л.Л., Босова А.Ю.

Тема: § 3.5. Программирование циклических алгоритмов

12.09.2016

551

0

Информатика

8 класс

9 класс

Другие методич. материалы

Учебник: «Информатика», Босова Л.Л., Босова А.Ю.

Тема: Глава 3. Начала программирования

12.09.2016

1572

0

«Практический подход в работе с утратой смысла жизни: логотерапия»

Свидетельство и скидка на обучение каждому участнику

Вам будут интересны эти курсы:

Курс повышения квалификации «Организация работы по формированию медиаграмотности и повышению уровня информационных компетенций всех участников образовательного процесса»

Курс повышения квалификации «Облачные технологии в образовании»

Курс повышения квалификации «Сетевые и дистанционные (электронные) формы обучения в условиях реализации ФГОС по ТОП-50»

Курс повышения квалификации «Развитие информационно-коммуникационных компетенций учителя в процессе внедрения ФГОС: работа в Московской электронной школе»

Курс повышения квалификации «Использование компьютерных технологий в процессе обучения в условиях реализации ФГОС»

Курс повышения квалификации «Специфика преподавания информатики в начальных классах с учетом ФГОС НОО»

Курс повышения квалификации «Введение в программирование на языке С (СИ)»

Курс повышения квалификации «Современные тенденции цифровизации образования»

Курс повышения квалификации «Применение интерактивных образовательных платформ на примере платформы Moodle»

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

12.09.2016 3468

DOCX 1.4 мбайт

18 скачиваний

Рейтинг: 5 из 5

Оцените материал:

Настоящий материал опубликован пользователем Клокова Ольга Михайловна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

Автор материала

На сайте: 5 лет и 9 месяцев

Подписчики: 0

Всего просмотров: 3984

Всего материалов: 2

40%

Московский институт профессиональной
переподготовки и повышения
квалификации педагогов

Дистанционные курсы
для педагогов

663 курса от 690 рублей

Выбрать курс со скидкой

Выдаём документы
установленного образца!

32 минуты

«Как занять ребенка, если под рукой ничего?! Игры с бумагой для младших школьников.»

48 минут

«Буллинг: вызовы и решения в воспитании и образовании детей»

61 минута

«Обсуждение проблем подготовки учителя к изложению материала на уроке, применения методических приемов и технологий работы с учащимися»

Подарочные сертификаты

Курсы «Инфоурок»

Онлайн-занятия с репетиторами на IU.RU

Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

Похожие публикации:

Как вставить строку в ворде в текст подчеркнутую для заполнения

Что такое алфавитный порядок слов

Что такое браузер спутник

Что такое высота сегмента