Побитовые логические операции
Кроме обычных логических операций, в Си имеются побитовые логические операции, которые выполняются независимо для каждого отдельного бита операндов. Побитовые операции имеют следующие обозначения:
& побитовое логическое сложение ("и") | побитовое логическое умножение ("или") ~ побитовое логическое отрицание ("не") ^ побитовое сложение по модулю 2 (исключающее "или")
(Необходимо помнить, что логические операции умножения и сложения записываются с помощью двойных знаков && или ||, а побитовые - с помощью одинарных.)
Ни в коем случае не используйте побитовые операции в качестве логических условий, это может приводить к непредсказуемым ошибкам!
В основном побитовые операции применяются для манипуляций с битовыми масками. Например, пусть целое число x описывает набор признаков некоторого объекта, состоящий из четырех признаков. Назовем их условно A, B, C, D. Пусть за признак A отвечает нулевой бит слова x (биты в двоичном представлении числа нумеруются справа налево, начиная с нуля). Если бит равен единице (программисты говорят бит установлен), то считается, что объект обладает признаком A. За признаки B, C, D отвечают биты с номерами 1, 2, 3. Общепринятая практика состоит в том, чтобы определить константы, отвечающие за соответствующие признаки (их обычно называют масками):
const int MASK_A = 1; const int MASK_B = 2; const int MASK_C = 4; const int MASK_D = 8;
Эти константы содержат единицу в соответствующем бите и нули в остальных битах. Для того чтобы проверить, установлен ли в слове x бит, соответствующий, к примеру, признаку D, используется операция побитового логического умножения. Число x умножается на константу MASK_D; если результат отличен от нуля, то бит установлен, т.е. объект обладает признаком D, если нет, то не обладает. Такая проверка реализуется следующим фрагментом:
if ((x & MASK_D) != 0) { // Бит D установлен в слове x, т.е. // объект обладает признаком D . . . } else { // Объект не обладает признаком D . . . }
При побитовом логическом умножении константа MASK_D обнуляет все биты слова x, кроме бита D, т.е. как бы вырезает бит D из x. В двоичном представлении это выглядит примерно так:
x: 0101110110...10*101 MASK_D: 0000000000...001000 x & MASK_D: 0000000000...00*000
Звездочкой здесь обозначено произвольное значение бита D слова x.
Для установки бита D в слове x используется операция побитового логического сложения:
x = (x | MASK_D); // Установить бит D в слове x
Чаще это записывается с использованием операции |= типа "увеличить на" (см. раздел 3.4.4):
x |= MASK_D; // Установить бит D в слове x
В двоичном виде это выглядит так:
x: 0101110110...10*101 MASK_D: 0000000000...001000 x | MASK_D: 0101110110...101101
Операция побитового отрицания "~" инвертирует биты слова:
x: 0101110110...101101 ~x: 1010001001...010010
Для очистки (т.е. установки в ноль) бита D используется комбинация операций побитового отрицания и побитового логического умножения:
x = (x & ~MASK_D); // Очистить бит D в слове x
или, применяя операцию "&=" типа "домножить на":
x &= ~MASK_D; // Очистить бит D в слове x
Здесь сначала инвертируется маска, соответствующая биту D,
MASK_D: 0000000000...001000 ~MASK_D: 1111111111...110111
в результате получаются единицы во всех битах, кроме бита D. Затем слово x побитно домножается на инвертированную маску:
x: 0101110110...10*101 ~MASK_D: 1111111111...110111 x & ~MASK_D: 0101110110...100101
В результате в слове x бит D обнуляется, а остальные биты остаются неизменными.
Приоритеты побитовых операций в Си выбраны достаточно странно (они такие же, как у соответствующих логических операций), это иногда приводит к неожиданным ошибкам. Например, если не заключить в скобки операцию побитового умножения в приведенном выше примере, то получится ошибочный результат: строка
if (x & MASK_D != 0) {
эквивалентна строке
if ((x & 1) != 0) {
т.е. проверяется бит A, а вовсе не D! Дело в том, что приоритет операции сравнения != выше, чем операции побитового умножения &, т.е.
в приведенной строке скобки неявно расставлены так:
if (x & (MASK_D != 0)) {
Выражение (MASK_D != 0) истинно и, таким образом, равно единице, поэтому строка эквивалентна
if (x & 1) {
что, в свою очередь, эквивалентно более канонической записи:
if ((x & 1) != 0) {
Чтобы избежать подобных ошибок, всегда заключайте все побитовые операции в скобки.
Побитовую операцию ^ называют сложением по модулю 2, а также "исключающим или". Часто для нее используется аббревиатура XOR, от eXclusive OR. "Таблица сложения" для этой операции выглядит следующим образом:
0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0.
Пусть x - произвольное целое число, m - маска, т.е. число, в котором интересующие программиста биты установлены в единицу, остальные в ноль. В результате выполнения операции XOR
x = (x ^ m);
или, в более удобной записи,
x ^= m;
биты в слове x, соответствующие установленным в единицу битам маски m, изменяются на противоположные (инвертируются). Биты слова x, соответствующие нулевым битам маски, не меняют своих значений. Пример:
x: 101101...1001011110 m: 000000...0011111100 x ^ m: 101101...1010100010
Операция XOR обладает замечательным свойством: если дважды прибавить к слову x произвольную маску m, то в результате получается исходное значение x:
((x ^ m) ^ m) == x
Прибавление к слову x маски m можно трактовать как шифрование x, ведь в результате биты x, соответсвующие единичным битам маски m, инвертируются. Если маска достаточно случайная, то в результате x тоже принимает случайное значение. Процедура расшифровки в данном случае совпадает с процедурой шифрования и состоит в повторном прибавлении маски m.
