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

Введение в биты и двоичную систему

Бит - минимальная единица информации, которая может принимать одно из двух значений.

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

Например, двоичное число $1011_2$ соответствует десятичному числу $11_{10}$ . Понимание этого позволяет применять операции напрямую к представлениям чисел в памяти.

Определение и основные понятия

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

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

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

Побитовое И (AND)

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

Пример: $1011\ \&\ 1101\ =\ 1001$

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

Побитовое ИЛИ (OR)

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

Пример: $0101\ \|\ 0011\ =\ 0111$

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

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

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

Пример: $1100\ \oplus\ 1010\ =\ 0110$

Интересное свойство XOR: применение одной и той же маски дважды восстанавливает исходное значение, то есть $a\ \oplus\ m\ \oplus\ m\ =\ a$ .

Побитовая инверсия (NOT)

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

Пример: $\mathrm{NOT}\ 00110101\ =\ 11001010$

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

Побитовые сдвиги

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

Логический сдвиг влево на один бит соответствует умножению на два для неотрицательных целых чисел: например, $0110\ 1001_{2}\ \xrightarrow{\ \text{<<1}\ }\ 1101\ 0010_{2}$ .

Логический сдвиг вправо на один бит соответствует целочисленному делению на два с отбрасыванием дробной части: $x\ \mid=\ m\quad\text{(установить биты):}\ x = x\ \,|\, m$ .

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

Практические приёмы и трюки

Маски позволяют быстро установить, сбросить или поменять конкретные биты. Чтобы установить бит по маске, используют операцию ИЛИ. Чтобы сбросить бит — применяют операцию И вместе с инверсией маски. Чтобы переключить бит — применяют XOR.

Установить бит: $x\ \&=\ \mathrm{NOT}(m)\quad\text{(сбросить биты):}\ x = x\ \&\ \sim m$ ; сбросить бит: $x\ \oplus=\ m\quad\text{(переключить биты):}\ x = x\ \oplus\ m$ ; переключить бит: $10110_{2}\ \&\ 00101_{2}$ .

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

Применения в программировании и алгоритмах

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

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

Типичные ошибки и особенности

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

Ещё одна распространённая ошибка — смешение логического и арифметического сдвига при работе с отрицательными числами. Необходимо четко понимать семантику оператора в используемом языке программирования.

Задачи и упражнения

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

Упражнение: вычислите результат выражения $10000_{2}$ и преобразуйте его в десятичную систему: $00000100_{2}$ .

Ещё одно упражнение: используя маску $1101_{2}$ , установите третий по счёту младший бит в числе $1101_{2}\ \mid\ 00000100_{2}\ =\ 1101_{2}$ и покажите результат $1101_{2}\ \&\ \sim 00000100_{2}\ =\ 1001_{2}$ .

Основные

Курсы

Другое