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


Оглавление (нажмите, чтобы открыть):

Как установить, сбросить, проверить нужный бит или битовые операции

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

Независимо от того какие микроконтроллеры Вы собираетесь программировать, первое что придётся освоить — это битовые операции.
Битовых операций в языке Си всего 6.

Начнем с того, что выводы микроконтроллера условно разделены на порты, у Atmega16 порт состоит из 8 выводов, у STM32f103 из 16 выводов.

Установить в 1 нулевой бит порта B можно следующим образом.

Таким образом, мы установили нулевой бит в 1, а все остальные в 0, то есть мы переопределили все биты порта. А что если мы хотим установить в 1 только нулевой бит и не задеть остальные? В таком случае нужно воспользоваться побитовым ИЛИ.

В результате мы изменили только нулевой бит порта.
Надо отметить, что в микроконтроллерах счёт начинается с нуля, то есть первый бит будет иметь нулевой порядковый номер, а порядковый номер восьмого бита будет 7.

Битовая операция НЕ — изменяет значение бита на противоположное.

Эта операция совместно с битовым НЕ может использоваться для сброса конкретного бита в ноль.

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

В итоге мы выставили в 0 только первый бит.

Также эту операцию можно использовать для проверки чему равен бит. Например, нам надо проверить чему равен нулевой бит порта B, это можно сделать с помощью следующей конструкции.

Если бит равен единице, выражение в скобках будет правда, иначе — ложь.

Побитовое исключающее ИЛИ — если сумма соответствующих битов число чётное, результирующий бит 0, иначе 1.

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

Также с помощью этой операции можно определить равенство регистров. Например, мы хотим сравнить в одинаковом ли состоянии находятся порты B и D.

Если результат равен нулю, то содержимое регистров равно.

Логический сдвиг влево — все разряды при этом сдвигаются на одну позицию влево, самый левый бит теряется, а в самый правый бит записывается 0.

Операция логического сдвига влево эквивалентна умножению на 2.
0b0000 1011 = 11
0b0001 0110 = 22

Логический сдвиг вправо — все разряды при этом сдвигаются на одну позицию вправо, самый правый бит теряется, а в самый левый бит записывается 0.

Урок 31 — 35
Арифметические и логические (битовые) операции. Маски. Арифметические и логические (битовые) операции. Маски
§26. Особенности представления чисел в компьютере. §27. Хранение в памяти целых чисел. § 28. Операции с целыми числами. §29. Хранение в памяти вещественных чисел

Содержание урока

§26. Особенности представления чисел в компьютере
§27. Хранение в памяти целых чисел
§28. Операции с целыми числами

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

§29. Хранение в памяти вещественных чисел

§28. Операции с целыми числами

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

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

Рассмотрим электронное устройство для управления гирляндой лампочек. Состояние каждой лампочки будет задаваться отдельным битом в некотором управляющем регистре: если бит равен нулю, лампочка выключена, если единице — включена. Для получения различных световых эффектов (типа «бегущих огней») требуется зажигать или гасить отдельные лампочки, менять их состояние на противоположное и т. д. (рис. 4.11). Точно так же биты регистров используются для управления внешними устройствами.

Будем применять логические операции к каждому биту числа, как обычно, считая, что 1 соответствует значению «истина», а 0 — «ложь». Эти операции часто называют поразрядными или битовыми, поскольку действия совершаются над каждым разрядом в отдельности, независимо друг от друга 1 .

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

Маска — это константа (постоянная), которая определяет область применения логической операции к битам многоразрядного числа. С помощью маски можно скрывать (защищать) или открывать для выполнения операции отдельные биты 2 .


1 Для сравнения, сложение (как и другие арифметические действия) не является поразрядной операцией, поскольку возможен перенос из младшего разряда в старший.

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

Основные логические операции в современных процессорах — это «НЕ» (not), «И» (and), «ИЛИ» (or) и «исключающее ИЛИ» (хог).

Логическое «НЕ» (инвертирование, инверсия, not) — это замена всех битов числа на обратные значения: 0 на 1, а 1 — на 0. Эта операция используется, например, для получения дополнительного кода отрицательных чисел (см. алгоритм А1 в § 27). «НЕ» — это унарная операция, т. е. она действует на все биты одного числа. Маска здесь не используется.

Логическое «И» (and). Обозначим через D содержимое некоторого бита данных, а через М — значение соответствующего ему бита маски. Операция «И» между ними задаётся таблицей, показанной на рис. 4.12.

Из таблицы видно, что при выполнении логического «И» нулевой бит в маске всегда сбрасывает (делает равным нулю) соответствующий бит результата, а единичный бит позволяет сохранить значение D (как бы пропускает его, открывая «окошко»).

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

Например, операция X and 1 сбросит у любого числа X все биты, кроме самого младшего. С помощью этого приёма легко узнать, является ли число чётным: остаток от деления на 2 равен последнему биту!

Логическое «ИЛИ». Вспомнив таблицу истинности логической операции «ИЛИ» (or), можно обнаружить, что в ноль в маске сохраняет бит (X or 0 = X), а единица устанавливает соответствующий бит результата (X or 1 = 1) (рис. 4.13).

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

Например, операция X or 8016 установит старший бит восьмиразрядного числа X, формально сделав тем самым число отрицательным.

Таким образом, используя операции «И» и «ИЛИ», можно сбрасывать и устанавливать любые биты числа, т. е. строить любой нужный двоичный код. Где это может пригодиться? Рассмотрим примеры решения конкретных задач.

Пример 1. На клавиатуре набраны 3 цифры, образующие значение целого числа без знака. Определить, какое число было введено.

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

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

Пусть S1 — код первого введённого символа, S2 — второго, S3 — третьего, а N обозначает искомое число. Тогда алгоритм перевода кодов символов в число выглядит так:

2. W = S1 and 0F16 (выделяем первую цифру).

3. N = 10 • N + W (добавляем её к числу).

4. W = S 2 and 0F16 (выделяем вторую цифру).

5. N = 10 • N + W (добавляем её к числу).

6. W = S3 and 0F16 (выделяем третью цифру).

7. N = 10 • N + W (добавляем её к числу).

Пусть, например, набраны символы ‘1’, ‘2’ и ‘3’. Тогда по таблице находим, что S1 =3116, S2 = 3216 и S3 =3316. Значение W на втором шаге вычисляется так:

Так как W = 1, на третьем шаге получаем N = 1. Следующая пара шагов — четвёртый и пятый — дают результаты W = 2 и N = 12 соответственно. Наконец, результат завершающих шагов: W = 3 и N = 123.

Такая процедура используется в каждом компьютере: именно так коды цифровых символов, набранные на клавиатуре, преобразуются в числа, с которыми компьютер выполняет арифметические действия. Заметим, что фактически здесь использована схема Горнера для представления целого числа (см. § 10).

Пример 2. Создадим структуру данных S, которая отражает, есть или нет в некотором числе каждая из цифр от 0 до 9. В математике такая структура называется множеством.

Для хранения S будем использовать 16-разрядное целое число (рис. 4.14).

Договоримся, что младший бит числа имеет номер 0 и хранит информацию о том, есть во множестве цифра 0 (если этот бит равен 0, такой цифры нет, если равен 1, то есть). Аналогично первый бит (второй по счёту справа) показывает, есть ли во множестве цифра 1, и т. д. Старшие биты 10-15 при этом не используются. Например, во множестве, изображенном на рис. 4.14, есть только цифры 0, 3, 6 и 9.

Для записи элементов во множество и проверки их наличия удобно использовать логические операции. Рассмотрим для примера бит 5. Маска, которая потребуется для обращения к нему, — это единица в пятом разряде и нули во всех остальных, т. е. М = 002020. С её помощью можно добавить элемент к множеству с помощью операции «ИЛИ»: S = S or М. А узнать, есть ли во множестве интересующая нас цифра, можно, выделив соответствующий бит с помощью логического «И» (Р = S and М) и проверив результат на равенство нулю.

Мастер Йода рекомендует:  Разрешение экрана и разметка страниц

Исключающее ИЛИ. Как видно из таблицы истинности, операция «исключающее ИЛИ» (хог) не изменяет биты, когда маска нулевая, и меняет биты на противоположные при единичной маске (рис. 4.15).

Например, команда Y = Y хоr FF16 выполняет инверсию всех битов 8-разрядного целого числа. Напомним, что это один из этапов получения дополнительного кода отрицательных чисел.

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

Пример 3. Пусть X — это результат выполнения некоторого вычислительного теста, а Y — то, что ожидалось получить («правильное» значение). Нужно определить, в каких разрядах различаются эти числа (для инженера это очень полезная подсказка, где искать неисправность).


Предположим, что Х = 7, Y = 3. В результате операции X хоr У устанавливаются (в единицу) только те разряды, которые в этих числах не совпали, а остальные сбрасываются 3 . В данном случае находим, что числа различаются только одним битом:

3 Профессиональные программисты часто используют операцию хоr для обнуления переменной: команда R := R хоr R запишет в переменную R ноль, независимо от её начального значения.

Пример 4. Используя логическую операцию «исключающее ИЛИ», можно шифровать любые данные. Покажем это на примере простого текста ‘2*2=4’.

Выберем любую маску, например 2310 = 0001 01112. Эта маска представляет собой ключ шифра — зная ключ, можно расшифровать сообщение. Возьмём первый символ — цифру ‘2’, которая имеет код 5010 = ООН 00102, и применим операцию «исключающее ИЛИ» с выбранной маской:

Полученное значение 0010 01012 = 3710 — это код символа ‘%’. Для расшифровки применим к этому коду «исключающее ИЛИ» с той же маской:

В результате получили число 50 — код исходной цифры ‘2’.

Повторное применение операции «исключающее ИЛИ» с той же маской восстанавливает исходное значение, т. е. эта логическая операция обратима.

Если применить такую процедуру шифрования ко всем символам текста ‘2*2=4’, то получится зашифрованный текст ‘%=%*#’.

Обратимость операции «исключающее ИЛИ» часто используется в компьютерной графике для временного наложения одного изображения на другое. Это может потребоваться, например, для выделения области с помощью инвертирования её цвета.

Следующая страница Сдвиги

Битовые операции

Введение

Я зык Си иногда называют макроассемблером за его тягу к железу. Если не использовать оптимизацию, можно даже примерно оценить, в какие конструкции на ассемблере преобразуется код программы. Простота и минимализм языка (простоту языка не путать с простотой программирования на языке) привели к тому, что на многих платформах си остаётся единственным высокоуровневым языком программирования. Без обзора побитовых операций, конечно, изучения языка было бы неполным.

Побитовые операции, как понятно из названия, позволяют оперировать непосредственно с битами. Большое количество примеров использования побитовых операций можно найти, например, в книге Генри Уоррена «Алгоритмические трюки для программистов». Здесь мы рассмотрим только сами операции и примитивные алгоритмы.

Побитовые И, ИЛИ, НЕ, исключающее ИЛИ

ЗАМЕЧАНИЕ: здесь и далее в примерах используются 8-битные числа для упрощения записи. Всё это верно и для любых других чисел.

Н апомню для начала, что логические операции И, ИЛИ, исключающее ИЛИ и НЕ могут быть описаны с помощью таблиц истинности

Логический оператор И

X Y X AND Y
1
1
1 1 1
Логический оператор ИЛИ

X Y X OR Y
1 1
1 1
1 1 1
Логический оператор исключающее ИЛИ

X Y X XOR Y
1 1
1 1
1 1
Логический оператор НЕ

X NOT X
1
1

В побитовых (bit-wise) операциях значение бита, равное 1, рассматривается как логическая истина, а 0 как ложь. Побитовое И (оператор &) берёт два числа и логически умножает соответствующие биты. Например, если логически умножить 3 на 8, то получим 0

Так как в двоичном виде 3 в виде однобайтного целого представляет собой

Первый бит переменной c равен логическому произведению первого бита числа a и первого бита числа b. И так для каждого бита.

00000011
00001000 ↓↓↓↓↓↓↓↓
00000000

Соответственно, побитовое произведение чисел 31 и 17 даст 17, так как 31 это 00011111 , а 17 это 00010001

00011111
00010001 ↓↓↓↓↓↓↓↓
00010001

Побитовое произведение чисел 35 и 15 равно 3.

00100011
00001111 ↓↓↓↓↓↓↓↓
00000011

Аналогично работает операция побитового ИЛИ (оператор |), за исключением того, что она логически суммирует соответствующие биты чисел без переноса.

выведет 15, так как 15 это 00001111 , а 11 это 00001011

00001111
00001011 ↓↓↓↓↓↓↓↓
00001111

Побитовое ИЛИ для чисел 33 и 11 вернёт 43, так как 33 это 00100001 , а 11 это 00001011


00100001
00001011 ↓↓↓↓↓↓↓↓
00101011

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

) работает не для отдельного бита, а для всего числа целиком. Оператор инверсии меняет ложь на истину, а истину на ложь, для каждого бита. Например,

Выведет -66, так как 65 это 01000001 , а инверсия даст 10111110

что равно -66. Кстати, вот алгоритм для того, чтобы сделать число отрицательным: для нахождение дополнительного кода числа его надо инвертировать и прибавить к нему единицу.

Исключающее ИЛИ (оператор ^) применяет побитово операцию XOR. Например, для чисел

будет выведено 89, так как a равно 00001100 , а b равно 01010101 . В итоге получим 01011001

Иногда логические операторы && и || путают с операторами & и |. Такие ошибки могут существовать в коде достаточно долго, потому что такой код в ряде случаев будет работать. Например, для чисел 1 и 0. Но так как в си истиной является любое ненулевое значение, то побитовое умножение чисел 3 и 4 вернёт 0, хотя логическое умножение должно вернуть истину.

Операции побитового сдвига

О пераций сдвига две – битовый сдвиг влево (оператор >). Битовый сдвиг вправо сдвигает биты числа вправо, дописывая слева нули. Битовый сдвиг влево делает противоположное: сдвигает биты влево, дописывая справа нули. Вышедшие за пределы числа биты отбрасываются.

Например, сдвиг числа 5 влево на 2 позиции

Сдвиг числа 19 вправо на 3 позиции

00010011 >> 3 == 00000010

Независимо от архитектуры (big-endian, или little-endian, или middle-endian) числа в двоичном виде представляются слева направо, от более значащего бита к менее значащему. Побитовый сдвиг принимает два операнда – число, над которым необходимо произвести сдвиг, и число бит, на которое необходимо произвести сдвиг.

Так как сдвиг вправо (>>) дописывает слева нули, то для целых чисел операция равносильна целочисленному делению пополам, а сдвиг влево умножению на 2. Произвести битовый сдвиг для числа с плавающей точкой без явного приведения типа нельзя. Это вызвано тем, что для си не определено представление числа с плавающей точкой. Однако можно переместить число типа float в int, затем сдвинуть и вернуть обратно

Но мы, конечно же, получим не 5.0f, а совершенно другое число.

Особенностью операторов сдвига является то, что они могут по-разному вести себя с числами со знаком и без знака, в зависимости от компилятора. Действительно, отрицательное число обычно содержит один бит знака. Когда мы будем производить сдвиг влево, он может пропасть, число станет положительным. Однако, компилятор может сделать так, что сдвиг останется знакопостоянным и будет проходить по другим правилам. То же самое и для сдвига вправо.

В данном случае при первом сдвиге всё работает, как и задумано, потому что число без знака. Во втором случае компилятор VSE2013 оставляет знак. Однако если посмотреть на представление этого числа, как беззнакового, сдвиг происходит по другим правилам, с сохранением самого левого бита. В последней строчке, если привести число со знаком к числу без знака, то произойдёт обычный сдвиг, и мы получим в результате положительное число.

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

Примеры

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

Для того, чтобы узнать, какой бит (1 или 0) стоит на позиции n, воспользуемся логическим умножением.

Пусть имеется число 9

Нужно узнать, выставлен ли бит на позиции 3 (начиная с нуля). Для этого умножим его на число, у которого все биты равны нулю, кроме третьего:

00001001 & 00001000 = 00001000

Теперь узнаем значение бита в позиции 6

00001001 & 01000000 = 00000000

Таким образом, если мы получаем ответ, равный нулю, то на искомой позиции находится ноль, иначе единица. Чтобы получить число, состоящее из нулей с одним битом на нужной позиции, сдвинем 1 на нужное число бит влево.

Заметьте, что в функции условие записано так

Потому что без скобок сначала будет вычислено равенство нулю и только потом выполнено умножение.

Функцию можно упростить

Функция, которая выставляет бит на n-й позиции в единицу.

Известно, что логическое сложение любого бита с 1 будет равно 1. Так что для установки n-го бита нужно логически сложить число с таким, у которого все биты, кроме нужного, равны нулю. Как получить такое число, уже рассмотрено.


Функция, которая устанавливает бит на n-й позиции в ноль.

Для этого нужно, чтобы все биты числа, кроме n-го, не изменились. Умножим число на такое, у которого все биты равны единице, кроме бита под номером n. Например

0001011 & 1110111 = 0000011

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

Функция, изменющая значение n-го бита на противоположное.

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

Битовые флаги

Расммотрим синтетический пример. Пусть у нас есть три логические переменные, и нам нужно вывести определённое значение в зависимости от всех этих переменных сразу. Очевидно, что может быть 2 3 возможных вариантов. Запишем это условие в виде ветвления:

Мы получили 8 ветвей. Пусть теперь нам понадобилось добавить ещё одно условие. Тогда число ветвей удвоится, и программа станет ещё сложней для понимания и отладки. Перепишем пример.

Если каждое из наших логичесих значений сдвинуть на своё число бит влево и логически сложить, то мы получим свою уникальную комбинацию бит в зависимоти от значений a, b и c:

Используем этот подход к нашей задаче и заменим ветвеление на switch:

Этот метод очень часто используется для назначения опций функций в разных языках программирования. Каждый флаг принимает своё уникальное название, а их совместное значение как логическая сумма всех используемых флагов. Например, библиотека fcntl:

Здесь флаг O_RDWR рaвен

00000000000000000000001000000000

и O_APPEND

Битовые операции над числами

Выполнить логические побитовые операции «И», «ИЛИ» и др. над числами 5 и 6. Выполнить над числом 5 побитовый сдвиг вправо и влево на два знака. Объяснить полученный результат.

Обычно в языках программирования предусмотрены так называемые логические побитовые операции. Они выполняются не над самими числами, а над их двоичным представлением. Например, число 5 в двоичной системе счисления выражается как 101, а число 6 — как 110. Выполняя логическую побитовую операцию «И» получим число 4, т.к. в младшим разряде числа 5 стоит 1, а числа 6 — 0. Выражение «1 и 0» возвращает 0. Продолжая поразрядно выполнять логическое «И» в среднем разряде получим 0, а в старшем 1. Можно записать так:
101

100
Двоичное число 100 — это десятичное число 4.

Выполним операцию побитового логического «ИЛИ»:
101

111 — это число 7.

«Исключающее ИЛИ»:
101

011 — это число 3.

При сдвиге биты просто сдвигаются на указанное количество ячеек в освободившиеся ячейки дописываются нули или единицы (это зависит от ряда причин):
110 > 2 = 001 (число 1).

Немного о портах и битовых операциях

Многие из вас видели и наверно даже понимают, что такое

Дубликаты не найдены

Просьба разжевать по конструкции if(PINB & B00101011)

Как я ее понял- в условии висит побитовое И между состоянием порта и маска. Что получится после побитового сложения? И каков критерий выполнения «if»? Насколько я помню проверяется истина-ложь относительно выражения в скобках, но истиной оно будет во всем диапазоне от 1 до 255, или я чего-то не понимаю в побитовых операциях.

if(0) — не выполнится
if(1). if(n>0) — выполнятся.

В данной конструкции я проверяю, что хотя бы на один вход по маске пришла единица, если надо проверить все сразу, то лучше воспользоваться
if(PINB == B00101011)

Воооот, теперь понятнее. А то у меня никак не сходилось в голове вот это:

(digitalRead(8) && digitalRead(9) && digitalRead(11) && digitalRead(13)) — тут же операторами && стоит, то есть 8 И 9 И 11 И 13 пины установлены- с этим: (PINB & B00101011)

ЗЫ. Что, кстати за 8, 9, 11, и 13 пины? Контроллер и все порты восьмибитные же. индекс 0. 7, не? Или это в ардуине такой бардак.


Ну я факапнул немного в посте с логикой, признаю.

DigitarRead/Write принимает значения от 0 до 20, это адаптация для упрощенного взаимодействия. Ардуино же создана для начинающих, и за кулисами digitalWrite(7) пройдет кучу проверок на включенный шим например, на что-то там ещё, и в итоге преобразуется в знакомую инструкцию PORTD | = _BV(7), а если впишем 13 порт — то в PORTB | = _BV(5).

а можно с начала?

что делает DDRB, что делает команда DDRB |= (1

Ddrb это регистр(переменная) в зависимости от значения ножки микроконтроллера работают по разному. 1 бит в этой переменной соответствует одной ножке. Например если туда записать в первый бит 1 а в остальные нули то мы получим 1ую ножку работающую в режиме выход(т е светодиод горит) а остальные ножки на вход(например можно читать данные с компа или шлейфа)

Отсюда и задача: оставить все ножки без изменения а третью перевести в режим выход. Если в ddrb мы запишем 255 то все ножки станут выходом. Если 0b00000100 то есть 4 то все кроме третьей станут входами. Но по задаче нужно все остальные оставить без изменений. Была 1 осталась 1. Была ноль осталось ноль. А вот третий бит установить 1. Как? Операцией and. 0b01100000 and 0b00000100 = 0b01100100. Т е как раз то что нужно. То бы это сделать выодим команду ddrb = ddrb and 0b00000100. Сокращенно ddrb |=0b00000100

Мир микроконтроллеров

Популярное

  • Устройство и программирование микроконтроллеров AVR для начинающих — 143
  • Трехканальный термостат, терморегулятор, таймер на ATmega8 — 70
  • Двухканальный термостат, терморегулятор на ATmega8 — 66

Битовые операции

Битовые операции

Логические битовые (побитовые) операции
Битовые операции сдвига

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

Битовые операции играют не последнюю роль в программе, позволяют более проще и практичнее реализовать замыслы программиста. Поэтому, бояться выражения «битовые операции» и их самих не надо, тем более, что страшное и не понятное в них — только в названии. А я постараюсь как можно подробнее рассказать и о битовых операциях, и об их применении в практике программистов.
Ряд источников по языкам низкого уровня называет побитовые логические операции просто логическими , но в терминологии программирования на языках высокого уровня в названиях битовых операций присутствуют прилагательные битовый, побитовый, поразрядный .

В распространённых языках программирования встроенными средствами реализуются только четыре побитовые (битовые) логические операции : И, ИЛИ, НЕ и исключающее ИЛИ. Для задания произвольной побитовой логической операции вполне достаточно перечисленных операций.

Чтобы мы не путались с выражениями «битовая операция» и «побитовая операция», запомним, что выполнение битовой операции — это выполнение побитовых операций с отдельными битами, и в дальнейшем я буду просто писать — «битовая операция» или «логическая операция».

Кроме того, читая техническую литературу вы наверняка столкнетесь с терминами «унарная операция» и «бинарная операция» .
Унарная операция — операция над одним операндом (Битовая операция «НЕ»).
Бинарная операция — операция с двумя операндами (Битовые операции «И», «ИЛИ», «ИСКЛЮЧАЮЩЕЕ ИЛИ»)

И еще, регистр общего назначения (R0…R31) я буду обозначать аббревиатурой РОН.

Битовые (побитовые) логические операции

Битовая операция НЕ:

Если бит равен «1», то после выполнения операции он будет равен «0». И наоборот, если бит равен «0», то после выполнения операции он будет равен «1». (операция выполняется одновременно над всеми битами РОН). В качестве операнда может использоваться только РОН

Обозначается знаком «

Кроме инвертирования состояния битов регистра, битовая операция НЕ, применяется для нахождения дополнительного кода числа (из положительного числа — сделать отрицательное). Для этого необходимо число проинвертировать и к полученному результату прибавить единицу .

Дополнительный код, как и прямой и обратный коды — наиболее распространённые способы представления десятичных чисел в двоичном коде. Это вопрос будет рассмотрен в отдельной статье.

Битовая операция И:

Если оба соответствующих бита операндов равны 1, результирующий двоичный разряд равен 1; если же хотя бы один бит из пары равен 0, результирующий двоичный разряд равен 0. В качестве операндов могут использоваться два РОН или РОН и константа (число, записанное в памяти МК)

Обозначается знаком «&»

Практическое применение:
— для сброса конкретного бита (битов) в ноль:

— для проверки бита на 0 или 1, оно же чтение конкретного бита (если результат равен 0, значит бит равен 0, иначе бит равен 1):


— проверка четности числа (четность — способность числа делиться на два)
У чётных чисел первый бит (самый правый) всегда равен нулю, а в нечётных единице:

Битовая операция ИЛИ

Если оба соответствующих бита операндов равны 0, двоичный разряд результата равен 0; если же хотя бы один бит из пары равен 1, двоичный разряд результата равен 1. В качестве операндов могут использоваться два РОН или РОН и константа

Обозначается знаком «|» (вертикальная палочка)

Битовая операция ИСКЛЮЧАЮЩЕЕ ИЛИ

Результат действия выполнения операции равен 1, если число складываемых единичных битов нечётно и равен 0, если чётно. В качестве операндов могут использоваться только РОН

Обозначается знаком «^»

Практическое применение:
— для инвертирования битов регистра по маске

— определения равенства регистров (если результат равен нулю, значит содержимое регистров равно, иначе — не равно):

Битовые операции сдвига

В системе команд микроконтроллеров AVR есть несколько битовых операций, которые трудно однозначно отнести к разделу только логических операций, они вполне могут найти себе место и в разделе арифметических операций (вернее, они там и находятся). Таких операций три:
— логический сдвиг
— арифметический сдвиг
— циклический сдвиг через бит переноса
Мы рассмотрим только операции, относящиеся к логическому сдвигу , а операции арифметического и циклического сдвига — в статьях по командам микроконтроллера.
Битовые операции сдвига, относящиеся к логическому сдвигу :
— логический сдвиг влево
— логический сдвиг вправо

Логический сдвиг влево

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

Обозначается знаком «

Логический сдвиг влево в основном используется как арифметическая операция для целочисленного умножения на 2.
На рисунке вверху показана выполненная два раза операция «логический сдвиг влево» — произведено два сдвига содержимого байта влево.
При этом:
— старшие биты, (выделены красным цветом) уходят в небытие (теряются)
— освободившиеся места младших битов заполняются «0» (выделены синим цветом)

Давайте посмотрим что получилось:
— первоначальное значение регистра 0000 0101 = 5 (в десятичной системе)
— первый сдвиг влево — получаем 0000 1010 = 10
— второй сдвиг влево — получаем 0001 0100 = 20
— а если произвести третий сдвиг — получим 0010 1000 = 40
Как видите, в результате каждого сдвига регистра, происходит умножение на два. Таким образом если нам надо умножить содержимое регистра на 8 (2 в степени 3), нам надо произвести 3 сдвига влево. А если надо умножить на 16 (2 в степени 4) — то 4 сдвига.
При этом надо учитывать, что число на которое можно умножить содержимое регистра должно быть равно «2 в степени n».

Это был пример сдвига как арифметической операции. Применение сдвига как логической операции — тут огромный простор для фантазии. Для примера — записываем в регистр 0000 0001, выводим содержимое в любой порт к выводам которого подсоединены светодиоды, — загорается первый светодиод, производим сдвиг — первый гаснет, зажигается второй (логическая единица переместилась на один разряд), результат — бегущий огонь на выходе.

Логический сдвиг вправо

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

Обозначается знаком «>>»

Логический сдвиг вправо используется как арифметическая операция для целочисленного деления на 2.

На рисунке вверху показана выполненная два раза операция «логический сдвиг вправо» — произведено два сдвига содержимого байта вправо.
При этом:
— младшие биты, а они выделены красным цветом, уходят в небытие (теряются)
— освободившиеся места старших битов заполняются «0» (выделены синим цветом)

Первоначальное число, записанное в регистр — 00100101 = 37 (десятичное)
— первый сдвиг — получаем 0001 0010 = 18
— второй сдвиг — получаем 0000 1001 = 9
При логическом сдвиге вправо происходит деление целочисленного числа на 2. При этом, как вы видите, если число нечетное (37), то при делении на 2 оно как-бы округляется в меньшую сторону (18). При этом надо учитывать, что число на которое можно разделить содержимое регистра должно быть равно «2 в степени n».

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

1. Побитовые (поразрядные) операции

В следующей таблице представлены побитовые операции применяемые в языке Java:

Побитовые операторы применяются к целочисленными типам long , int , short , char , byte . Побитовые операторы применяются к каждому отдельному биту каждого операнда.

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

A | B

A & B

A ^ B

1.1. Побитовое ИЛИ (OR , |)

1.2. Побитовое И (AND , &)


1.3. Побитовое исключающее ИЛИ (XOR , ^)

1.4. Побитовое НЕ (NOT ,

, называемый также побитовым дополнением, инвертирует все биты операнда.

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

2. Битовые сдвиги в Java

Типы byte и short продвигаются к типу int при вычислении выражения.

Пример битовых сдвигов:

3. Побитовые операции с присваиванием

Также существуют побитовые операции с присваиванием:

4.2. Деление числа на два

  • x – умножение на 2.
  • x>>1 — деление на два с отбрасыванием любого остатка.

4.3. Шифрование числа

Представьте, что необходимо отправить в сообщении число 560 — пинкод от банковской карты. Если злоумышленник перехватит сообщение, то узнает пинкод и сможет воспользоваться им. Только отправитель и получатель могут знать пинкод. Чтобы этого не произошло придумаем какое-то число — маску и сообщим его получателю заранее. Перед отправкой пинкода зашифруем его — применим побитовую операцию XOR: message^XOR . И результат отправим. Если злоумышленник и перехватит сообщение, он не будет знать как его расшифровать. Адресат получает сообщение, расшифровывает пинкод с помощью имеющейся маски: message^maska .

Как проверить, имеет ли значение четность бит или нечетное?

Значение имеет четную четность, если оно равно четному числу 1 бит. Значение имеет нечетную четность, если оно имеет нечетное число из 1 бита. Например, 0110 имеет четную четность, а 1110 имеет нечетную четность.

Мне нужно вернуть 1 , если x имеет четную четность.

Предполагая, что вы знаете, что ints — 32 бита.

Посмотрим, как это работает. Чтобы это было просто, позвольте использовать 8-битное целое число, для которого мы можем пропустить первые два сдвига /XOR. Пусть обозначают биты a через h. Если посмотреть на наш номер, мы увидим:

Первая операция x ^= x >> 4 (помните, что мы пропускаем первые две операции, так как в этом примере мы имеем дело только с 8-разрядным целым числом). Пусть записываются новые значения каждого бита, комбинируя буквы, которые являются XOR’d вместе (например, ab означает, что бит имеет значение a xor b).

В результате появляются следующие биты:

Следующая операция x ^= x >> 2 :

В результате появляются следующие биты:

Обратите внимание, как мы начинаем накапливать все биты с правой стороны.

Следующая операция x ^= x >> 1 :

В результате появляются следующие биты:

Мы накопили все биты в исходном слове, XOR’d вместе, в младшем значении. Таким образом, этот бит теперь равен нулю, если и только если в входном слове было четное число 1 бит (даже четность). Тот же процесс работает с 32-битными целыми числами (но требует этих двух дополнительных сдвигов, которые мы пропустили в этой демонстрации).

Последняя строка кода просто удаляет все, кроме наименее значимого бита ( & 1 ), а затем переворачивает его (

x ). Тогда результатом будет 1, если четность входного слова была четной или в противном случае — 0.

Вычислить четность слова с умножением

Следующий метод вычисляет четность 32-разрядного значения только за 8 операций> с использованием умножения.


Также для 64-битных 8 операций все еще достаточно.

Эндрю Шапира придумал это и отправил мне 2 сентября 2007 года.

В GCC есть встроенная функция для этого:

Встроенная функция: int __builtin_parity (unsigned int x)

Возвращает четность x , то есть число 1 бит в x по модулю 2.

т.е. эта функция ведет себя как has_odd_parity . Инвертировать значение для has_even_parity .

Это гарантировано будет самой быстрой альтернативой GCC. Конечно, его использование не является переносимым как таковое, но вы можете использовать его в своей реализации, например, защищенным макросом.

Основная идея такова. Уберите самый правый бит «1», используя x & ( x — 1 ) . Предположим, что x = 13 (1101), а операция x & ( x — 1 ) равна 1101 & 1100 , что составляет 1100, обратите внимание, что самый правый бит установлен в 0 .

Теперь x — 1100 . Операция x & ( x — 1 ) i.e 1100 & 1011 равна 1000 . Обратите внимание, что оригинал x равен 1101 , а после двух операций x & (x — 1) x — 1000 , то есть два установленных бита удаляются после двух операций. Если после odd количества операций, x становится равным нулю, тогда его нечетная четность, иначе это четная четность.

Обобщение ответа @TypelA для любой архитектуры:

Вот одна строка #define которая делает трюк для char :

Это портативно как черт и легко изменено, чтобы работать с большими словами (16, 32 бита). Также важно отметить, что использование #define ускоряет выполнение кода, каждый вызов функции требует времени, чтобы протолкнуть стек и выделить память. Размер кода не пострадает, особенно если он реализован только несколько раз в вашем коде — вызов функции может занять столько же объектного кода, сколько XOR.

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

Я не буду добавлять пример выполнения этого в c, так как уже есть достаточно хороших ответов.

В случае, если конечный результат должен быть частью кода, который может работать (компилироваться) с помощью программы c, я предлагаю следующее:

Это часть кода, которую я использую для проверки четности вычисленных результатов в 64-битной c-программе, скомпилированной с использованием MSVC. Очевидно, вы можете перенести его на 32-битные или другие компиляторы.

Преимущество этого заключается в том, что он намного быстрее, чем использование c, а также использует функциональность cpus.

Что делает этот пример, следует принимать в качестве входного параметра (переданный в соглашении вызова RCX — __fastcall). Он увеличивает его на 0, таким образом устанавливая флаг четности cpus, а затем устанавливая переменную (RAX) на 0 или 1, если флаг четности включен или нет.

Проверка числа на чётность в C#

Проверка является ли число чётным одна из самых распространённых задач в программировании. Особенно, если учесть, что в C# отсутствует готовая функция для её решения.

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

Рассмотрим их более подробно.

Деление с остатком на 2

Если число нечётное, то остаток от его деления на 2 будет больше нуля. Таким образом, для проверки числа на чётность необходимо проверить, равен ли нулю остаток отделения числа на 2.

Битовая арифметика и операции над битами

В Pascal над целыми типами (byte, shortint, word, integer, longint и их диапазоны) допустимы побитовые операции.

Логические операции над битами

Над битами двух целых операндов можно выполнять ранее рассмотренные логические операции: not, and, or, xor. Отличие между побитовыми и логическими операциями состоит в том, что побитовые (поразрядные) операции выполняются над отдельными битами операндов, а не над их значением в десятичном (обычно) представлении.

Например, число 5 в двоичном представлении (в одном байте) имеет значение 00000101. Операция not инвертирует биты и мы получим 11111010, т.е число 250. Если побитовую операцию or использовать к числам 5 (00000101) и 3 (00000011), то получится число 7 (00000111).

Операции циклического сдвига

В Паскаль определены еще две операции над данными целого типа, имеющие тот же уровень приоритета, что и операции and, *, /, div и mod. Это операции shl и shr, которые сдвигают последовательность битов на заданное число позиций влево или вправо соответственно. При этом биты, которые выходят за разрядную сетку, теряются. При выполнении операции shl освободившиеся справа биты заполняются нулями. При выполнении операции shr освободившиеся слева биты заполняются единицами при сдвиге вправо отрицательных значений и нулями в случае положительных значений.

С помощью операции shl возможна замена операции умножения целых чисел на степени двойки. Следующие пары выражений приводят к одинаковому результату: (a shl 1) = a * 2, (a shl 2) = a * 4, (a shl3) = a * 8.

Пример побитовых операций и циклического сдвига

Практическое значение побитовых операций

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

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

Пусть переменная a имеет тип byte и является байтом с восемью флагами. Необходимо проверить состояние бита с номером 5 (биты нумеруются справа налево от 0 до 7). Единица в бите 5 — это пятая степень числа 2, т.е. 32 (00100000). Поэтому, если в пятом бите переменной a стоит единица, то выполняется условие (a and 32) = 32, которое можно проверить в операторе ветвления if. Если необходимо проверить состояние нескольких одновременно установленных в единицу битов, то нужно вычислить соответствующее число как сумму степеней числа 2, где показатели степени равны номерам битов, установленных в 1. Например, для битов 5, 2 и 0 имеем 32+4+1=37. Если a имеет среди прочих единицы в битах 5, 2, 0, то выполнится условие (a and 37) = 37.

Пусть нужно обнулить какой-либо бит в переменной a типа byte (например, бит 3). Определим сначала число, содержащее единицы во всех битах, кроме третьего. Максимальное число, которое можно записать в тип byte, равняется 255. Чтобы в нем обнулить третий бит, вычтем из этого числа третью степень числа 2 (255-8=247). Если это число логически умножить на a, то его единицы никак не скажутся на состоянии переменной a, а нуль в третьем бите независимо от значения третьего бита переменной a даст в результате 0. Итак, имеем a:= a and (255-8). Аналогично можно обнулить несколько битов.

Операция or применяется при установке в единицу отдельных битов двоичного представления целых чисел. Так, чтобы установить бит 4 переменной a в единицу без изменения остальных битов, следует записать a:= a or 16, где 16 — четвертая степень числа 2. Аналогично устанавливаются в единицу несколько битов.

Операция xor применяется для смены значения бита (или нескольких битов) на противоположное (1 на 0 или 0 на 1). Так, чтобы переключить в противоположное состояние 3-й бит переменной a, следует записать a:= a xor 8, где 8 — третья степень числа 2.

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