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


Содержание

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

Материал на этой странице устарел, поэтому скрыт из оглавления сайта.

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

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

Формат 32-битного целого числа со знаком

Побитовые операторы в JavaScript работают с 32-битными целыми числами в их двоичном представлении.

Это представление называется «32-битное целое со знаком, старшим битом слева и дополнением до двойки».

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

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

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

Примеры представления чисел в двоичной системе:

Обратите внимание, каждое число состоит ровно из 32-битов.

Дополнение до двойки – это название способа поддержки отрицательных чисел.

Двоичный вид числа, обратного данному (например, 5 и -5 ) получается путём обращения всех битов с прибавлением 1.

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

Например, вот число 314 :

Чтобы получить -314 , первый шаг – обратить биты числа: заменить 0 на 1 , а 1 на 0 :

Второй шаг – к полученному двоичному числу прибавить единицу, обычным двоичным сложением: 11111111111111111111111011000101 + 1 = 11111111111111111111111011000110 .

Итак, мы получили:

Принцип дополнения до двойки делит все двоичные представления на два множества: если крайний-левый бит равен 0 – число положительное, если 1 – число отрицательное. Поэтому этот бит называется знаковым битом.

Список операторов

В следующей таблице перечислены все побитовые операторы. Далее операторы разобраны более подробно.

a

Оператор Использование Описание
Побитовое И (AND) a & b Ставит 1 на бит результата, для которого соответствующие биты операндов равны 1.
Побитовое ИЛИ (OR) a | b Ставит 1 на бит результата, для которого хотя бы один из соответствующих битов операндов равен 1.
Побитовое исключающее ИЛИ (XOR) a ^ b Ставит 1 на бит результата, для которого только один из соответствующих битов операндов равен 1 (но не оба).
Побитовое НЕ (NOT) Заменяет каждый бит операнда на противоположный.
Левый сдвиг a Сдвигает двоичное представление a на b битов влево, добавляя справа нули.
Правый сдвиг, переносящий знак a >> b Сдвигает двоичное представление a на b битов вправо, отбрасывая сдвигаемые биты.
Правый сдвиг с заполнением нулями a >>> b Сдвигает двоичное представление a на b битов вправо, отбрасывая сдвигаемые биты и добавляя нули слева.

Побитовые операторы работают следующим образом:

  1. Операнды преобразуются в 32-битные целые числа, представленные последовательностью битов. Дробная часть, если она есть, отбрасывается.
  2. Для бинарных операторов – каждый бит в первом операнде рассматривается вместе с соответствующим битом второго операнда: первый бит с первым, второй со вторым и т.п. Оператор применяется к каждой паре бит, давая соответствующий бит результата.
  3. Получившаяся в результате последовательность бит интерпретируется как обычное число.

Посмотрим, как работают операторы, на примерах.

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

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

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

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

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

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

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

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

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

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

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

Например. Если в выражении (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;

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

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

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

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

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

В языке программирования C существуют следующие поразрядные операции: & (И), | (ИЛИ), ^ (исключающее ИЛИ), > (сдвиг вправо),

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

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

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

В результате на экране вы увидите:

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

000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

Теперь допустим, что у нас есть восьмеричное число 037. По таблице легко понять, что в двоичном выражении оно будет выглядеть как 011 111.

Задание

  1. Как будут выглядеть восьмеричные числа 04271 и 03566 в двоичном представлении.
  2. Составьте на бумаге таблицу соответствия шестнадцатеричный цифр двоичным числам. Переведите числа 7D, FFFF, 2C9 в двоичную систему счисления.

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

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

Результат ее работы будет выглядеть так:

Этот результат будет проще понять с помощью рисунка:

В последнем случае получилось такое большое число потому, что под форматы вывода целых чисел ( %d, %o, %X ) выделяется по 4 байта.

Задание

  • Используя шестнадцатеричные числа, напишите аналогичную приведенной выше программу. Объясните результат.
  • Попробуйте составлять сложные битовые операции (в несколько действий) и оценивать их результат.

Теперь рассмотрим пример использования битовых операций. Допустим, у нас есть массив, требуется снять с него «маску», которая бы отражала, в какой позиции стоят отрицательные, а в какой положительные элементы. Пусть единица в бите обозначает соответствующий ей положительный элемент массива, а ноль — отрицательный. Другими словами, если у нас есть массив <4, -3, 2, 2, 8, -1>, то его «битовая маска» будет выглядеть как 101110, или в восьмеричном представлении как 056. Составим алгоритм решения этой задачи:

  1. Будем считать, что массив состоит не более чем из 32 элементов. Поэтому для хранения его «маски» достаточно переменной типа int . Назовем ее mask и присвоим значение 0.
  2. Перебрать элементы массива в цикле for . Если встречается положительный элемент, то установить соответствующий ему бит значения mask в 1.
  3. Вывести значение переменной mask на экран в виде восьмеричного числа.


Вроде бы все просто, но как установить в единицу определенный бит числа? Существует закономерность соответствия степеней двойки и двоичного представления числа:
2 0 = 0000 0001
2 1 = 0000 0010
2 2 = 0000 0100
2 3 = 0000 1000
2 4 = 0001 0000
и т.д. Если для вас эта последовательность не очевидна, то пересчитайте. Теперь если применить к mask побитовую операцию | (ИЛИ), а в качестве второго операнда использовать определенную степень двойки, то один бит будет установлен в 1. Например:
(0) 0000 0000 | (2 5 ) 0010 0000 = 0010 0000
(32) 0010 0000 | (2 7 ) 1000 0000 = 1010 0000

При переборе первый элемент массива имеет индекс 0, но соответствующий ему бит в maskдолжен стоять впереди остальных. Если известно общее количество элементов массива (N), то можно определить степень двойки по формуле N — i — 1 . Действительно, имея третий положительный элемент массива из 10 элементов, следует установить в единицу восьмой с конца бит, а это значит надо использовать вторым операндом битового ИЛИ 27, а 7 как раз будет 10(N) — 2(i) — 1.

Другая проблема — как в языке C возвести число в степень. Понятно, что можно написать свой код, но скорее всего в стандартной библиотеке уже есть подобная функция. С помощью заголовочного файла math.h можно подключить библиотеку с математическими функциями. Среди них есть функция pow() , которая принимает два числа и возвращает результат возведения первого числа в степень, выраженную вторым числом. Однако результат возвращается в виде вещественного числа, а нам требуется целое. Как быть? В языке программирования С есть операции приведения типов, которые меняют тип значения с одного на другой. Например, чтобы преобразовать значение вещественной переменной a в целое, следует написать (int) a .
Вот как может выглядеть вышеописанная программа:

Задание
Напишите предыдущую программу. Оцените как она работает 1 . Подумайте над тем, как вывести на экран двоичное представление восьмеричного числа. Попробуйте реализовать это.
1 Если у вас не получается скомпилировать программу, добавьте в конце вызова gcc опцию -lm (например, gcc -o bits bits.c -lm ).

Программируем просто

Поиск по этому блогу

Подписаться на этот блог

Follow by Email

Язык Си. Битовые операторы и операции. Трюки с битами.

  • Получить ссылку
  • Facebook
  • Twitter
  • Pinterest
  • Электронная почта
  • Другие приложения

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

^ — исключающее ИЛИ (XOR)
Лучше никак не называть кроме как XOR :-) чтобы не вносить путаницу. Два одинаковых по значению бита, дают 0, два различных по значению дают 1
0101
^
0011
=
0110

>> — побитовый сдвиг вправо

Теперь перейдем к примерам.

Установить нужный бит в 1

Очистить нужный бит(сбросить, установить в 0)

Инвертировать нужный бит (0 в 1, 1 в 0)

Тест нужного бита (установлен он в 0 или 1)

Подсчет количества единичных битов.
Для того чтобы подсчитать количество единичных битов можно использовать следующую операцию x&(x-1)
Суть этой операции в том что самый младший единичный бит устанавливается в 0, соответственно выполняя в цикле эту операцию над значением, можно подсчитать количество единичных битов, которое будет равно количеству итераций.
0b01001011 — количество единичных битов 4
считаем:
0b01001011 & (0b01001011 — 1) = 0b01001010
0b01001010 & (0b01001010 — 1) = 0b01001000
0b01001000 & (0b01001000 — 1) = 0b01000000
0b01000000 & (0b01000000 — 1) = 0b00000000

Обмен двух значений без использования временной переменной.
Все знают как обменять значения двух переменных с помощью временной переменной.
Но не все знают как это сделать без временной переменной :-), с помощью XOR, код ниже.

Один из алгоритмов генерации случайных чисел, разработанный Джорджом Марсаглием,
xorshift (больше примеров по ссылке)

Использование XOR также применяется в шифровании, ниже пример простого шифрования на основе XOR и ключа шифрования, его недостатком является то что зная часть исходных данных можно вычислить ключ, но такой прием используется как маленькая часть больших и сложных алгоритмов шифрования.
Если зашифрованную строку проксорить оригинальной то мы получим ключ :-)

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

Определить имеют ли два числа, противоположные знаки

Установить или сбросить биты по маске
Много интересных примеров также есть !здесь! (некоторые из которых присутствуют в этом посте.)

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

Выполнить логические побитовые операции «И», «ИЛИ» и др. над числами 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).

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

Битовые операции, иногда также булевы или логические операции [1] — операции над битами, применяемые в программировании и цифровой технике, изучаемые в дискретной математике и математической логике.

Введение

Булевы операции и математическая логика


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

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

Булевы операции как основа цифровой техники

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

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

«(Логическое) И» (and) — аналог конъюнкции в логике. Иногда называется логическим умножением.

В булевой логике: $ \land $ В языке C: &

Выдаёт 1 если оба входа равны 1, в противном случае 0. Если один из аргументов равен 1, то результат «И» равен другому. Если один из аргументов равен 0, то результат «И» равен 0 независимо от значения другого аргумента.

«(Логическое) НЕ» (not), инвертирование — аналог отрицания в логике.

В булевой логике: $ \neg $ В языке C:

Данная унарная операция (с одним входом) заменяет 0 на 1 и наоборот. Реализующий её элемент называется инвертором.

«(Логическое) ИЛИ» (or) — аналог дизъюнкции в логике.

В булевой логике: $ \lor $ В языке C: |

Выдаёт 1 если и только если хотя бы один из входов равен 1. Операция, двойственная AND: при инвертировании выхода и всех входов (т.е. при замене 0 и 1 местами) «И» и «ИЛИ» взаимно превращается друг в друга.

Исключающее ИЛИ

«Исключающее ИЛИ» (xor), «сложение по модулю 2» — аналог исключающего ИЛИ в логике.

В булевой логике: $ \oplus $ В языке C: ^

Если один из аргументов равен 0, то результат равен другому. Если один из аргументов равен 1, то результат равен отрицанию другого аргумента. Первое русское название операции обусловлено тем, что результат данной операции отличается от результата «ИЛИ» только в одном случае из 4 случаев входа — обоих 1 (случай одновременной истинности аргументов «исключается»). Ещё в русской грамматике значение данной логической связки передаётся союзом «либо».

Второе название — тем, что действительно является сложением в кольце вычетов по модулю 2, из чего следуют некоторые интересные свойства. Например, в отличие от вышеописанных «И» и «ИЛИ» данная операция является обратимой, или инволютивной: $ (x\oplus y)\oplus y = x $ .

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

Операции от многих аргументов

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

Прочие бинарные операции

«ИЛИ-НЕ» (nor), она же «стрелка Пирса».

В булевой логике: $ \downarrow $

Стрелка Пирса является результатом инвертирования результата «ИЛИ» своих аргументов, выдаёт значение 1 только когда оба входа 0.

«И-НЕ» (nand), она же «штрих Шеффера».

В булевой логике: $ \mid $

Двойственная стрелке Пирса операция: является результатом инвертирования результата «И» своих аргументов, выдаёт значение 0 только когда оба входа 1. Известна простотой реализации в ТТЛ.

Импликация («если-то») — аналог импликации в логике.

В булевой логике: $ \subset $

Совпадает с «ИЛИ» с инвертированным первым аргументом, выдаёт значение 0 только когда первый вход 1 а второй — 0. Данная операция не является коммутативной, в отличие от всех вышеописанных бинарных операций. Её можно понимать как арифметическое $ \le $ (меньше или равно).

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

Сводная таблица истинности булевых операций

x ( $ \neg $ )

Название И/AND НЕ/NOT ИЛИ/OR искл. ИЛИ/XOR импл. стрелка
Пирса
штрих
Шеффера
x y & ( $ x\land y $ ) | ( $ x\lor y $ ) ^ ( $ x\oplus y $ ) $ x\to y $ ( $ x\subset y $ ) $ x\downarrow y $ $ x\mid y $
1 1 1 1
1 1 1 1 1 1
1 1 1 1
1 1 1 1 1

Операции над битовыми векторами

Обобщение операций на булеву алгебру

Вместо одиночных битов мы можем рассмотреть векторы из фиксированного количества битов (в программировании их называют регистрами), например, байты. В программировании регистры рассматривают как двоичное разложение целого числа: $ b = b_0 + 2 b_1 + 2^2 b_2 + . + 2^ b_ $ , где N — количество битов в регистре.

Тем не менее, ничто не мешает рассматривать эти регистры именно как битовые векторы и проводить булевые операции покомпонентно (бит номер k значения есть результат операция от битов номер k аргументов). Кстати, математически говоря, булевы операции распространяются таким образом на произвольную булеву алгебру. Таким образом мы получаем операции побитового И, ИЛИ, НЕ, искл. ИЛИ и т.д. Как арифметические, данные операции не обладают хорошими свойствами за исключением побитового НЕ, которое для чисел в дополнительном коде совпадает с вычитанием из -1 (

x == -1-x ). Однако, они очень полезны в программировании.

Битовые сдвиги

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

Также различают сдвиг влево (в направлении от младшего бита к старшему) и вправо (в направлении от старшего бита к младшему).

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


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

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

Арифметический сдвиг

Арифметический сдвиг аналогичен логическому, но значение слова считается знаковым числом представленному дополнительным кодом. Так при правом сдвиге старший бит сохраняет свое значение. Левый арифметический сдвиг идентичен логическому.

Циклический сдвиг

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

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

2-адическая интерпретация

Целое число, записанное (в дополнительном коде) в бесконечный (в сторону положительных степеней двойки) двоичный регистр является естественным объектом для теории p-адических чисел при $ p=2 $ . Множество целых 2-адических чисел (т.е. произвольных бесконечных битовых последовательностей) может быть рассмотрено как булева алгебра точно так же как и множество значений битового регистра конечной длины. Все вышеперечисленные битовые операции оказываются непрерывными отображениями. Хотя практическое программирование не располагает регистрами бесконечной длины, это не мешает использовать данный теоретический факт в криптографии для создания быстродействующих алгоритмов шифрования.

Практические применения

Физическая реализация битовых операций

Наиболее распространены электронные реализации битовых операций при помощи транзисторов, например транзисторно-транзисторная логика и КМОП; в первой половине XX века вместо транзисторов применяли электронные лампы. Однако, реализация битовых операций может в принципе быть любой: механической, электромеханической, гидравлической или пневматической, оптической и даже химической.

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

Схемы аппаратной логики

Результат операции ИЛИ-НЕ или ИЛИ ото всех битов двоичного регистра проверяет, равно ли значение регистра нулю; то же самое взятое от выхода искл. ИЛИ двух регистров проверяет равенство их значений между собой.

Битовые операции применяются в знакогенераторах и графических адаптерах; особенно велика была их роль в адаптере EGA в режимах с 16 цветами — хитроумное сочетание аппаратной логики адаптера с логическими командами центрального процессора позволяет рассматривать EGA как первый в истории графический ускоритель.

Использование в программировании

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

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

Операция И также используется для наложения маски — например, в IP-адресации (хотя не только).

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

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

Независимо от того какие микроконтроллеры Вы собираетесь программировать, первое что придётся освоить — это битовые операции.
Битовых операций в языке Си всего 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.

Лекция 7. Битовые поля и побитовые операции¶

Системы счисления¶

Теория¶

Системы счисления¶


В настоящее время применяются позиционные системы счисления, изобретённые в Древней Индии.

Основные используемые системы счисления:

Принцип формирования числа:

\(o\) — основание системы счисления (2,10,16).

\(a\) — значение разряда.

\(m\) — номер разряда.

Перевод из двоичной в десятичную¶

Имеем двоичное число \(n_<2>=00101001\) .

Ему соответствует десятичное \(n_<10>=0*(2)^7+0*(2)^6+1*(2)^5+0*(2)^4+1*(2)^3+0*(2)^2+0*(2)^1+1*(2)^0=32+8+1=41\)

Числа, содержащие по одной единице легко запоминаются:

\(00000001\) \(1\)
\(00000010\) \(2\)
\(00000100\) \(4\)
\(00001000\) \(8\)
\(00010000\) \(16\)
\(00100000\) \(32\)
\(01000000\) \(64\)
\(10000000\) \(128\)

Несложно выполнить перевод, если числа содержат несколько идущих подряд единиц:

\(00000011\) \(4-1=3\)
\(00000111\) \(8-1=7\)
\(00001111\) \(16-1=15\)
\(00011111\) \(32-1=31\)
\(00111111\) \(64-1=63\)
\(01111111\) \(128-1=127\)
\(11111111\) \(256-1=255\)

Перевод из десятичной в двоичную¶

Пусть дано \(n_<10>=57\)

  1. Разделить 57 на 2: 28 — 1 (с остатком)
  2. Разделить 28 на 2: 14 — 0 (без остатка)
  3. Разделить 14 на 2: 7 — 0 (без остатка)
  4. Разделить 7 на 2: 3 — 1 (с остатком)
  5. Разделить 3 на 2: 1 — 1 (с остатком)
  6. Разделить 1 на 2: 0 — 1 (с остатком)

Пишем значения разрядов в обратном порядке.

В результате получаем \(n_2=111001\) .

Перевод из шестнадцатиричной в десятичную¶

Перевод из шестнадцатиричной в двоичную¶

Удобно переводить шестнадцатиричное число в двоичное по тетрадам:

Рассмотрим число \(8a\)

\(8\) \(a\)
\(1000\) \(1010\)

Арифметика¶

Сложение¶

Вычитание¶

Знак числа¶

Порядок байтов¶

Little Endian vs. Big Endian¶

Используется два порядка расположения байтов в многобайтной величине: от старшего к младшему big endian и от младшего к старшему little endian.

BE используют: IBM 360/370/390, Motorola 68000, SPARC

LE используют: Intel x86

Достоинства LE¶

Существенным достоинством little-endian по сравнению с big-endian порядком записи считается возможность ‘’неявной типизации’’ целых чисел при чтении меньшего объёма байт.

Так, если в ячейке памяти содержится число 0x00000022, то прочитав его как int16 (два байта) мы получим число 0x0022, прочитав один байт — число 0x22. Однако, это же может считаться и недостатком, потому что провоцирует ошибки потери данных.

Проверка¶

Следующие функции позволяют проверить, какой порядок байт принят в вашей системе:

Использование полей битов¶

Очень полезное с практической точки зрения представление памяти в 1 байт, которое можно использовать как unsigned char или как набор значений отдельных битов.

Функция, переводящая байт из 10-тичной системы в 2-ичную с использованием поля битов:

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

Обзор¶

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

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


  • & — умножение (конъюнкция)
  • ** \(|\) ** — сложение (дизъюнкция)
  • alert<

< - отрицание

  • ** \(>>\) ** — побитовый сдвиг вправо
  • ** \( ** — побитовый сдвиг влево
  • ** \(\widehat <**\) >— исключающее “или” (xor)
  • Вместе с этими операциями может использоваться присваивание, например a>>=2

    Отрицание¶

    Поразрядное отрицание alert<

    Следующая функция возвращает максимальное значение unsigned int в вашей системе:

    Поразрядное ‘’И’‘¶

    Операция & ‘’И’’ является бинарной и выставляет результирующий бит в 1, если оба бита операндов равны 1.

    Поразрядное И¶

    Преобразование числа в бинарную форму:

    Поразрядное ‘’ИЛИ’‘¶

    Операция | ‘’ИЛИ’’ является бинарной и выставляет результирующий бит в 1, если хотя бы один бит у операндов равен 1.

    Поразрядное ИСКЛЮЧАЮЩЕЕ ИЛИ¶

    Операция ** \(\widehat <**\) >‘’ИСКЛЮЧАЮЩЕЕ ИЛИ’’ является бинарной и выставляет результирующий бит в 1, если первый (или второй) бит операнда равен 1, но не оба одновременно.

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

    Операции в языке Си

    Над объектами в языке Си могут выполняться различные операции:

    • операции присваивания;
    • операции отношения;
    • арифметические;
    • логические;
    • сдвиговые операции.

    Результатом выполнения операции является число.

    Операции могут быть бинарными или унарными.
    Бинарные операции выполняются над двумя объектами, унарные — над одним.

    Операция присваивания

    Операция присваивания обозначается символом = и выполняется в 2 этапа:

    • вычисляется выражение в правой части;
    • результат присваивается операнду, стоящему в левой части:

    объект = выражение;

    В случае если объекты в левой и правой части операции присваивания имеют разные типы используется операция явного приведения типа.
    объект = (тип)выражение;

    Операции отношения

    Основные операции отношения:

    • == эквивалентно — проверка на равенство;
    • != не равно — проверка на неравенство;
    • меньше;
    • > больше;
    • меньше или равно;
    • >= больше или равно.

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

    Арифметические операции

    Основные бинарные операции, расположенные в порядке уменьшения приоритета:

    • * — умножение;
    • / — деление;
    • + — сложение;
    • — вычитание;
    • % — остаток от целочисленного деления.

    Основные унарные операции:

    • ++ — инкрементирование (увеличение на 1);
    • –– — декрементирование (уменьшение на 1);
    • — изменение знака.

    Результат вычисления выражения, содержащего операции инкрементирования или декрементирования, зависит от того, где расположен знак операции (до объекта или после него). Если операция расположена до объекта, то сначала происходит изменение значения переменной на 1, а потом это значение используется для выполнения следующих операций. Если операция ++ или расположена после переменной, то сначала выполняется операция, а потом значение переменной изменяется на 1.


    Бинарные арифметические операции могут быть объединены с операцией присваивания:

    • объект *= выражение; // объект = объект * выражение
    • объект /= выражение; // объект = объект / выражение
    • объект += выражение; // объект = объект + выражение
    • объект -= выражение; // объект = объект — выражение
    • объект %= выражение; // объект = объект % выражение

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

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

    Условные логические операции чаще всего используются в операциях проверки условия if и могут выполняться над любыми объектами. Результат условной логической операции:

    • 1 если выражение истинно;
    • 0 если выражение ложно.

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

    Основные условные логические операции:

    • && — И (бинарная) — требуется одновременное выполнение всех операций отношения;
    • || — ИЛИ (бинарная) — требуется выполнение хотя бы одной операции отношения;
    • ! — НЕ (унарная) — требуется невыполнение операции отношения.

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

    Основные побитовые логические операции в языке Си:

    инверсия (логическое НЕ) — унарная операция, результат которой равен 0 если операнд единичный, и равен 1, если операнд нулевой;

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

    a

    a b a & b a | b a ^ b
    1
    1 1 1 1
    1 1 1
    1 1 1 1

    a; // e = 241 = 1111 0001
    f = a ^ b; // f = 7 = 0000 0111

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

    Бит Маска
    0x01
    1 0x02
    2 0x04
    3 0x08
    4 0x10
    5 0x20
    6 0x40
    7 0x80

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

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

    0x02); // a = 1, бит 1 сброшен

    Бинарные побитовые логические операции могут быть объединены с операцией присваивания:

    • объект &= выражение; // объект = объект & выражение
    • объект |= выражение; // объект = объект | выражение
    • объект ^= выражение; // объект = объект ^ выражение

    Сдвиговые операции

    Операции арифметического сдвига применяются в целочисленной арифметике и обозначаются как:

    • >> — сдвиг вправо;
    • — сдвиг влево.

    Общий синтаксис осуществления операции сдвига:
    объект = выражение сдвиг КоличествоРазрядов;

    Арифметический сдвиг целого числа вправо >> на 1 разряд соответствует делению числа на 2.
    Арифметический сдвиг целого числа влево на 1 разряд соответствует умножению числа на 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.

    Илон Маск рекомендует:  Можно ли изменить вид всплывающей подсказки
    Понравилась статья? Поделиться с друзьями:
    Кодинг, CSS и SQL