|
Битовые операции И, ИЛИ, НЕ, XOR. Сдвиговые операцииПрактический курс по C/C++: https://stepik.org/course/193691 В языке Си можно выполнять не только арифметические операции над числами, но и с отдельными битами. Что такое биты и как с их помощью кодируются целые числа, мы с вами ранее уже говорили. Так вот для работы с отдельными битами чисел используются следующие общепринятые операции: И, ИЛИ, НЕ, исключающее ИЛИ (XOR) Битовая операция НЕНачнем с самой простой битовой операции НЕ, которая выполняет инверсию бит в соответствии со следующей таблицей истинности:
На языке Си она записывается с помощью символа ~ (тильда). Например: #include <stdio.h> int main(void) { unsigned char var = 153; //двоичная запись 10011001 unsigned char not_v = ~var; //результат: 01100110 (число 102) printf("var = %d, not_v = %d\n", var, not_v); return 0; } Здесь для простоты восприятия информации переменные обозначены как однобайтовые без знака. Первая принимает значение 153, а вторая формируется с помощью битовой операции НЕ, то есть, с помощью инверсии всех бит числа. В результате переменная not_v принимает значение 102. Можно заметить, что 153+102 = 255 – максимальное значение байтовой переменной. И это логично, так как число 102 содержит недостающие единицы числа 153 и в сумме они дают восемь единичных бит, то есть, число 255. Битовая операция ИСледующая операция битовая И в языке Си записывается символом & (амперсанд). Она является бинарной и образует следующую таблицу истинности:
Это очень похоже на умножение, поэтому ее условно воспринимают, как битовое умножение. Величины x и y – соответствующие биты двух операндов. Давайте посмотрим, как она работает на конкретных примерах: #include <stdio.h> int main(void) { unsigned char flags = 5; //двоичная запись 00000101 unsigned char mask = 4; //двоичная запись 00000100 unsigned char res = flags & mask; printf("res = %d\n", res); return 0; } В этой программе происходит побитовое умножение соответствующих бит двух переменных flags и mask в соответствии с таблицей истинности операции И. В результате, переменная res будет содержать следующую информацию:
То есть, мы над каждыми парами бит переменных flags и mask выполняем битовую операцию И, и то что получается на выходе заносится в соответствующие биты переменной res. Получаем ее двоичное представление, которое соответствует десятичному значению 4. И, действительно, после запуска программы видим именно это значение переменной res. Я, думаю, вы поняли, как это работает, но здесь возникает вопрос зачем все это надо? Смотрите, если нам нужно проверить включен ли какой-либо бит числа (то есть установлен ли он в 1), то мы можем относительно просто сделать это с помощью битовой операции И следующим образом: Здесь переменная mask определяет маску с включенным 2-м битом, который мы хотим проверить у переменной flags. Далее, в соответствии с битовой операцией И (flags & mask) все биты обнулятся, кроме 2-го, но только в том случае, если в переменной flags 2-й бит установлен в 1. В итоге, если результат операции (flags & mask) равен маске, то 2-й бит включен и на экране мы видим соответствующее сообщение. Чтобы убедиться, что все действительно работает, давайте поменяем переменную flags на 1: unsigned char flags = 1; //двоичная запись 00000001 и снова запустим программу. На этот разу увидим другое сообщение, что 2-й бит выключен. По аналогии можно проверять другие биты или сразу группы бит. Другим важным назначением операции И является выключение определенных бит переменной. Делается это следующим образом: #include <stdio.h> int main(void) { unsigned char flags = 13; //двоичная запись 00001101 unsigned char mask = 5; //двоичная запись 00000101 flags = flags & ~mask; printf("flags = %d\n", flags); return 0; } Как это работает? Сначала вычисляется инверсия бит переменной mask, так как операция НЕ имеет более высокий приоритет, чем операция И. Затем, идет операция битового И, и там где в маске стоят 1, биты переменной flags не меняются, остаются прежними, а там где в маске стоят 0 – соответствующие биты в переменной flags обнуляются. За счет этого происходит выключение 2-го и 0-го битов переменной flags:
Кстати, строчку битовых операций здесь можно записать в более краткой форме: flags &= ~mask; //двоичная запись 00001000 Битовая операция ИЛИСледующая битовая операция – битовое ИЛИ. Она определяется символом | и ее таблица истинности выглядит следующим образом:
Для чего можно использовать эту операцию? Обычно ее применяют, когда нужно включить отдельные биты переменной. Рассмотрим следующую программу: #include <stdio.h> int main(void) { unsigned char flags = 8; //двоичная запись 00001000 unsigned char mask = 5; //двоичная запись 00000101 flags = flags | mask; //двоичная запись 00001101 (число 13) printf("flags = %d\n", flags); return 0; } Здесь преобразования над переменными flags и mask выполняются следующим образом:
То есть, операция битового ИЛИ как бы собирает все единички из обеих переменных и получается своеобразное битовое сложение. Кстати, в нашем конкретном примере действительно получается результат 8+5=13. Но это не всегда так, например, если: unsigned char flags = 9; //двоичная запись 00001001 то результат тоже будет 13, так как операция ИЛИ включает бит вне зависимости был ли он уже включен или нет, все равно на выходе будет единица. И здесь уже 9+5=13, что математически неверно. Битовая операция исключающее ИЛИ (XOR)И последняя базовая операция работы с битами – исключающее ИЛИ (ее еще называют XOR). Она определяется символом ^ и имеет следующую таблицу истинности:
Из нее видно, что данная операция позволяет переключать биты числа, то есть, если они были равны 0, то станут 1 и, наоборот, если были 1 – станут 0. Продемонстрируем это на примере: #include <stdio.h> int main(void) { unsigned char flags = 9; //двоичная запись 00001001 unsigned char mask = 1; //двоичная запись 00000001 flags = flags ^ mask; //двоичная запись 00001000 (число 8) printf("flags = %d\n", flags); flags ^= mask; //двоичная запись 00001001 (число 9) printf("flags = %d\n", flags); return 0; }
Интересной особенностью операции XOR является отсутствие потерь данных при ее работе. Что это значит? Смотрите, какую бы маску мы не взяли, дважды примененная маска дает исходное значение: Это, как раз, связано с эффектом переключения бит, а значит, двойное переключение даст исходный результат. Где этот эффект можно применить? Самое простое – в шифровании данных. Например, когда у нас есть сообщение в виде набора данных и маска – как шифровальный ключ. Тогда, к каждому блоку данных можно применить маску и, таким образом, зашифровать сообщение. В частности по такому принципу устроена защита по паролю в архиваторе zip. Причем, сам пароль является ключом, который накладывается по XOR на заархивированные данные. Приоритеты базовых битовых операцийИтак, мы с вами рассмотрели основные битовые операции, которые также можно записывать и в краткой форме:
Самый высокий приоритет у унарной операции НЕ, затем, с меньшим приоритетом следует операция И, далее, XOR и самый низкий приоритет у битовой операции ИЛИ. Также обратите внимание, приоритет всех битовых операций ниже, чем у операций сравнения и существенно ниже обычных арифметических операций. Битовые операции сдвигов >> и <<В заключение этого занятия рассмотрим еще два распространенных битовых оператора:
Само название уже говорит, что они сдвигают все биты числа вправо или влево и если переменная объявлена как беззнаковая, то на освободившиеся позиции добавляются нули. Например: #include <stdio.h> int main(void) { unsigned char x = 40; // 00101000 printf("x = %d\n", x); x = x >> 1; // 00010100 (число 20) printf("x = %d\n", x); x = x >> 2; // 00000101 (число 5) printf("x = %d\n", x); x = x >> 1; // 00000010 (число 2) printf("x = %d\n", x); x = x >> 1; // 00000001 (число 1) printf("x = %d\n", x); x = x << 1; // 00000010 (число 2) printf("x = %d\n", x); x = x << 2; // 00001000 (число 8) printf("x = %d\n", x); return 0; } Смотрите, при единичном сдвиге бит числа вправо получаем целочисленное деление числа на 2, а при единичном сдвиге влево – целочисленное умножение числа на 2. Именно поэтому число 5 при сдвиге бит вправо дает число 2. Причем эти операции умножения и деления работают значительно быстрее, чем традиционные арифметические операции умножения и деления. Поэтому, разработчики различных алгоритмов для маломощных процессоров стараются составлять вычисления так, чтобы они базировались на сдвиговых операциях, исключая прямое умножение и деление. Сдвиги бит влево для знаковых чисел работают абсолютно так же, как и для беззнаковых. А вот сдвиг вправо несколько отличается. Здесь старший бит знака дублируется. Например: И последнее. Приоритет сдвиговых битовых операций << и >> одинаковый, но выше, чем у операций сравнений и меньше чем у арифметических операций. Практический курс по C/C++: https://stepik.org/course/193691 Видео по теме |
