bulgakov

17. Побитовые операции, сдвиги и маски

В уроке о двоичной записи число было суммой разрядов: 6 = 4 + 2, поэтому его младшие четыре бита — 0110. Теперь научимся проверять и менять отдельные биты. Это нужно, например, когда одно число хранит несколько независимых признаков: разрешено чтение, запись или выполнение.

Логические операторы проверяют истинность целых выражений. Побитовые операторы работают с соответствующими битами целых чисел. Поэтому 6 && 3 даёт 1, а 6 & 3 даёт 2.

И, или и исключающее или для одного бита

Сначала рассмотрим одну пару битов:

Бит a Бит b a & b a | b a ^ b
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0

& оставляет 1, только если оба бита равны 1. | даёт 1, если хотя бы один бит равен 1. ^ даёт 1, если биты различаются; это исключающее «или», или XOR. В C знак ^ не означает возведение в степень.

Для многобитного числа это правило применяется к каждому разряду отдельно. Для 6 и 3:

  0110  (6)       0110  (6)       0110  (6)
& 0011  (3)     | 0011  (3)     ^ 0011  (3)
  ----           ----           ----
  0010  (2)       0111  (7)       0101  (5)

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

Полная программа:

C
#include <stdio.h>

int main(void)
{
    unsigned int a = 6u;
    unsigned int b = 3u;

    printf("AND: %u\n", a & b);
    printf("OR: %u\n", a | b);
    printf("XOR: %u\n", a ^ b);
    printf("Logical AND: %d\n", a && b);
    return 0;
}

Вывод:

AND: 2
OR: 7
XOR: 5
Logical AND: 1

Для работы с битами здесь используем unsigned int — целый тип без отрицательных значений. Суффикс u в небольших константах 6u и 3u задаёт тип unsigned int. Результаты побитовых операций над этими переменными тоже имеют этот тип, поэтому выводятся через %u. Результат && имеет тип int и равен 0 или 1, поэтому для него нужен %d.

Другие примеры из той же таблицы правил: 5u & 1u даёт 1, 5u | 2u — 7, 5u ^ 1u — 4. В каждом случае можно записать числа двоично и проверить каждый столбец.

У & и | нет короткого вычисления, которое было у && и ||. Нельзя заменить ими логические операторы в проверке, защищающей от деления на ноль. Побитовые операции требуют целочисленных операндов; float и double для них не подходят.

Инверсия: поменять каждый бит

Оператор ~ применяется к одному числу: каждый 0 превращается в 1, каждый 1 — в 0. Он меняет все биты значения, а не только те четыре разряда, которые мы нарисовали.

Поэтому из схемы 0001 → 1110 ещё нельзя заключить, что ~1u равно 14. Для unsigned int результат — UINT_MAX - 1u, где UINT_MAX из <limits.h> обозначает наибольшее значение этого типа.

Чтобы оставить только младшие четыре бита, применим & 15u. Число 15 имеет младшие биты 1111; старшие разряды такого ограничения равны нулю.

C
#include <stdio.h>
#include <limits.h>

int main(void)
{
    unsigned int value = 1u;
    unsigned int inverted = ~value;

    printf("Expected unsigned value: %d\n", inverted == UINT_MAX - 1u);
    printf("Low four bits: %u\n", inverted & 15u);
    return 0;
}

Вывод:

Expected unsigned value: 1
Low four bits: 14

Первая строка печатает результат сравнения, а не само большое число. Это позволяет проверить правило независимо от того, сколько битов использует конкретный unsigned int.

В примере лекции ~1 для знакового int даёт -2 в среде с дополнительным кодом: биты ...0001 превращаются в ...1110. Это нужно отличать от ~1u. В C17 представление знаковых отрицательных чисел зависит от реализации; для переносимых операций с наборами битов удобнее выбрать unsigned int.

Сдвиги: передвинуть разряды

В записи value << n биты сдвигаются влево на n позиций. В записи value >> n — вправо. Для unsigned int освободившиеся позиции заполняются нулями, а биты, вышедшие за границу значения, теряются.

Схема
0001 >> 1 = 0000     1 → 0
0001 << 2 = 0100     1 → 4
0101 >> 1 = 0010     5 → 2
00000101 << 3 = 00101000     5 → 40

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

C
#include <stdio.h>

int main(void)
{
    unsigned int a = 1u;
    unsigned int b = 5u;

    printf("a >> 1: %u\n", a >> 1);
    printf("a << 2: %u\n", a << 2);
    printf("b >> 1: %u\n", b >> 1);
    printf("b << 3: %u\n", b << 3);
    return 0;
}

Вывод:

a >> 1: 0
a << 2: 4
b >> 1: 2
b << 3: 40

Для беззнакового числа сдвиг вправо на одну позицию соответствует целочисленному делению на 2: из 5 / 2 получается 2, дробная часть отбрасывается. Сдвиг влево на одну позицию соответствует умножению на 2, пока результат помещается. Если старшие единицы теряются, обычного математического результата уже не будет: беззнаковое значение сокращается по модулю UINT_MAX + 1. Это математическая запись модуля; вычислять UINT_MAX + 1u для его хранения в том же типе не нужно.

Число позиций должно быть неотрицательным и меньше разрядности левого операнда после целочисленных продвижений. Так называют преобразование небольших целочисленных типов, например char, к int или unsigned int перед операцией. В наших примерах левый операнд уже имеет тип unsigned int, поэтому это преобразование не меняет его тип. Например, если unsigned int в выбранной среде имеет 32 разряда, допустимы количества 0…31; сдвиг на 32 недопустим. Сам по себе суффикс u эту ошибку не исправляет.

Для отрицательного знакового числа сдвиг вправо в C17 зависит от реализации. В показанной в лекции среде старшие позиции заполняются единицами: -3 >> 1 даёт -2. Но -3 / 2 даёт -1. Поэтому правило «сдвиг вправо — это деление» нельзя без оговорки переносить на отрицательные числа. Сдвиг отрицательного знакового числа влево в C17 имеет неопределённое поведение; не используйте его как способ умножения. Для неотрицательного знакового значения результат левого сдвига должен помещаться в тип; переполнение здесь тоже нельзя считать обычным беззнаковым оборачиванием.

Маска: выбрать нужный бит

Битовая маска — число, единицы которого отмечают нужные разряды. Номер самого правого бита — 0. Маски для битов 0, 1, 2, 3 равны 1, 2, 4, 8. Например, 1u << 2 даёт маску 4, то есть младшие биты 0100.

Пусть отдельные биты означают разрешения: 4 — читать, 2 — записывать, 1 — выполнять. Полная программа проверяет, включает, выключает и переключает отдельные признаки:

C
#include <stdio.h>

enum Permission { EXECUTE = 1, WRITE = 2, READ = 4 };

int main(void)
{
    unsigned int flags = READ | EXECUTE;
    unsigned int write_mask = WRITE;
    unsigned int execute_mask = EXECUTE;

    printf("Start: %u\n", flags);
    printf("Can read: %d\n", (flags & READ) != 0u);
    flags = flags | write_mask;
    printf("After set: %u\n", flags);
    flags = flags & ~execute_mask;
    printf("After clear: %u\n", flags);
    flags = flags ^ write_mask;
    printf("After toggle: %u\n", flags);
    return 0;
}

Вывод:

Start: 5
Can read: 1
After set: 7
After clear: 6
After toggle: 4

Начальные флаги — 101: чтение и выполнение. | 010 включает запись и даёт 111. & ~001 выключает выполнение и оставляет 110. ^ 010 переключает запись: здесь она была включена, поэтому выключается, и остаётся 100.

Для инверсии маска сохранена в unsigned int, чтобы ~ работал именно с беззнаковым значением. Для проверки отдельного бита применяют (flags & mask) != 0u. Для проверки, что установлены все биты составной маски, — (flags & mask) == mask.

У беззнакового числа младший бит показывает чётность: (value & 1u) == 0u истинно для чётного значения. Например, у 6 младшие биты 0110, у 7 — 0111.

Похожая идея есть в записи прав 755 в Unix: цифры задаются в восьмеричной системе. Первая относится к владельцу, вторая — к группе, третья — к остальным. 7 означает 111, а 5 — 101. Это девять обычных битов rwx; у реальных прав доступа существуют и другие механизмы, поэтому вся система доступа ими не исчерпывается. Здесь мы только читаем запись, команды изменения прав выполнять не требуется.

Скобки предотвращают другую проверку

У сравнения == приоритет выше, чем у побитового &. Поэтому 6 & 3 == 3 разбирается как 6 & (3 == 3): сначала получается 1, затем 6 & 1, то есть 0.

Если нужно сначала вычислить побитовое «и», пишите (6 & 3) == 3. Здесь результат тоже 0, но по другой причине: 6 & 3 равно 2, а 2 не равно 3. Скобки меняют смысл, даже когда ответ случайно совпал.

Чтобы увидеть разницу в ответе, возьмём value = 2u. Правильная проверка (value & 4u) == 0u даст 1: бит 4 выключен. Запись без скобок value & 4u == 0u даст 0, потому что сначала вычислит 4u == 0u, а затем 2u & 0.

Сравнения == и != связываются сильнее также, чем побитовые ^ и |. Явно отделяйте побитовую часть скобками: сначала выберите биты, затем сравните результат.

Далее научимся повторять действия с помощью while.

ПрактикаЗагружаем тест…