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

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

Принцип работы

Логические побитовые операции

Битовые операторы И $(AND,\ \&)$, ИЛИ $(OR,\ \mid)$, НЕ $(NOT,\ \sim)$ и исключающее ИЛИ $(XOR,\ $\textasciicircum$,\ \oplus)$ используют те же таблицы истинности, что и их логические эквиваленты.

Побитовое И

Побитовое И используется для выключения битов. Любой бит, установленный в $0$, вызывает установку соответствующего бита результата также в $0$.

&
	11001010 11100010
	11000010

Побитовое ИЛИ

Побитовое ИЛИ используется для включения битов. Любой бит, установленный в $1$, вызывает установку соответствующего бита результата также в $1$.

|
	11001010 11100010
	11101010

Побитовое НЕ

Побитовое НЕ инвертирует состояние каждого бита исходной переменной.

~
	11001010
	00110101

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

Исключающее ИЛИ устанавливает значение бита результата в $1$, если значения в соответствующих битах исходных переменных различны.

^
	11001010 11100010
	00101000

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

Операторы сдвига $\texttt{\lt \lt }$ и $\texttt{\gt \gt }$ сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в двоичном дополнительном коде и необходимо поддерживать знаковый бит).

Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.

x = 7         // 00000111 (7)
x = x >> 1    // 00000011 (3)
x = x << 1    // 00000110 (6)
x = x << 5    // 11000000 (-64)
x = x >> 2    // 11110000 (-16)

В языке программирования Java существует также оператор беззнакового битового сдвига вправо $\texttt{\gt \gt \gt }$. При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.

x = 7          // 00000111 (7)
x = x << 5     // 11100000 (-32)
x = x >>> 2    // 00111000 (56)

Применение

Сложные операции

Определение знака числа

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

int32 getSign(x: int32):
    if x != 0:
        mask = 1
    else:
        mask = 0

    return mask | (x >> 31)    // результатом будет -1, 0, или +1 
                               // для отрицательного, равного нулю и положительного числа x соответственно

Используя побитовые операции можно также узнать, различны ли знаки двух переменных $x$ и $y$. Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство $(x \oplus y) \lt 0$ будет верно в том случае, если числа $x$ и $y$ разного знака.

Вычисление модуля числа без использования условного оператора

Пусть дано число $x$. Если $x$ положительно, то $mask = 0$, и $(x + mask) \oplus mask = x$. В случае, если $x$ отрицательно, $mask = -1$. Тогда получается, что мы работаем с числом $x$ так, как будто оно представлено в коде со сдвигом с тем отличием, что у нас знаковый бит принимает значение $1$ для отрицательных чисел, а $0$ — для положительных.

int32 abs1(x: int32):
    mask = x >> 31
    return (x + mask) [math]\oplus[/math] mask

int32 abs2(x: int32):
    mask = x >> 31
    return (x [math]\oplus[/math] mask) - mask

Нахождение минимума и максимума из двух чисел без использования условного оператора

Этот способ корректен только если можно утверждать, что величина $(x - y)$ лежит между граничными значениями типа int.

Пусть даны числа $x$ и $y$ разрядности $n$. Тогда, если $x \lt y$, то $((x - y) \texttt{\gt \gt } (n - 1)) = -1$ а если $x \geqslant y$, то $((x - y) \texttt{\gt \gt } (n - 1)) = 0$. Выражение $((x - y) \& ((x - y) \texttt{\gt \gt } (n - 1))$ принимает значение $0$, если $x \geqslant y$ и $(x - y)$, если $x \lt y$.

int32 min(x, y: int32):
    return y + ((x - y) & ((x - y) >> 31))

int32 max(x, y: int32):
    return x - ((x - y) & ((x - y) >> 31))

Проверка на то, является ли число степенью двойки

Пусть дано число $x$. Тогда, если результатом выражения $(x\ \&\&\ !(x\ \&\ (x - 1)))$ является единица, то число $x$ — степень двойки.

Правая часть выражения $(!(x\ \&\ (x - 1)))$ будет равна единице, только если число $x$ равно $0$ или является степенью двойки. Если число $x$ является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: $1\underbrace{0\dots0}_{n}$, где $n$ — показатель степени. Соответственно, выражение $(x - 1)$ будет иметь вид $\underbrace{1\dots1}_{n}$, и $x\ \&\ (x - 1)$ равно $0$.

Операция логического И в данном выражении отсекает тот случай, когда $(x = 0)$ и не является степенью двойки, но при этом правая часть $(!(x\ \&\ (x - 1)))$ равна единице.

Нахождение младшего единичного бита

Пусть дано число $x$ и необходимо узнать его младший единичный бит.

Применим к числу $x$ побитовое отрицание, чтобы инвертировать значения всех его бит, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом $x$, а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа $(x\ \&\ (\sim x + 1))$.

К такому же результату можно прийти, если сначала отнять от числа $x$ единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в $1$, затем инвертировать результат и применить побитовое И с исходным числом $(x\ \&\ \sim (x - 1))$.

Нахождение старшего единичного бита

Пусть дано число $x$ и необходимо узнать его старший единичный бит.

Рассмотрим некоторое число, представим его как $0\dots01b \dots b$, где $b$ — любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на $1$ и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат $0\dots011b \dots b$. Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на $2$, то получим $0\dots01111b \dots b$. При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций (зависит от разрядности числа) мы получим число вида $0\dots01\dots1$. Тогда результатом выполнения действий $x - (x \texttt{ \gt \gt }1)$ будет число, состоящее только из старшего бита исходного числа.

int32 greatestBit(x: int32):
    power = 1
    for i = 1..[math]\log_2{32}[/math]:
        x |= x >> power
        power <<= 1
    return x - (x >> 1)

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

Пусть дано число $x$ и надо совершить циклический сдвиг его битов на величину $d$. Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на $d$ и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.

int32 rotateLeft(x, d: int32):
    return (x << d) | (x >>> (32 - d))

int32 rotateRight(x, d: int32):
    return (x >>> d) | (x << (32 - d))

Подсчет количества единичных битов

Для подсчета количества единичных битов в числе $x$ можно воспользоваться следующим алгоритмом:

// Пример приведен для 16-ти битных чисел. 
// Для чисел большей разрядности необходимо использовать соответствующие константы.
x = x - ((x >>> 1) & 0x5555)
x = (x & 0x3333) + ((x >>> 2) & 0x3333)
x = (x + (x >>> 4)) & 0x0F0F
answer = (x * 0x0101) >>> 8

Поскольку $5555_{16}$ равно $01010101 01010101_{2}$, результатом операции $x\ \&\ 5555_{16}$ является число, в котором все нечетные биты соответствуют нечетным битам числа $x$. Аналогично, результатом операции $(x\ \texttt{\gt \gt \gt }\ 1)\ \&\ 5555_{16}$ является число, в котором все нечетные биты соответствуют четным битам $x$. Четные биты результата в обоих случаях равны нулю.

Мысленно разобьем двоичную запись нашего числа $x$ на группы по $2$ бита. Результатом операции $x\ \&\ 5555_{16} + (x\ \texttt{\gt \gt \gt }\ 1)\ \&\ 5555_{16}$ будет такое число, что если разбить его двоичную запись на группы по два бита, значение каждой группы соответствует количеству единичных битов в соответствующей паре битов числа $x$.

Аналогично, число $3333_{16}$ равно $00110011 00110011_{2}$ и операция $x = (x\ \&\ 3333_{16}) + (x\ \texttt{\gt \gt \gt }\ 2\ \&\ 3333_{16})$, примененная к результату, полученному на первом этапе, выполняет подсчет количества единичных битов в блоках по $4$. В свою очередь, число $\texttt{0F0F}_{16}$ равно $00001111 00001111_{2}$ и операция $x = (x\ \&\ \texttt{0F0F}_{16}) + (x\ \texttt{\gt \gt \gt }\ 4\ \&\ \texttt{0F0F}_{16})$ позволяет подсчитать число единичных бит в блоках по $8$.

Теперь необходимо просуммировать числа, записанные в блоках по $8$ битов, чтобы получить искомую величину. Это можно сделать, домножив результат на $0101_{16}$ $(1 00000001_{2})$. Ответ на задачу будет находиться в первых восьми битах произведения. Выполнив сдвиг вправо на $8$ (для шестнадцатибитных чисел), мы получим долгожданный ответ.

Подведем итог:

x = (x & 0x5555) + ((x >>> 1) & 0x5555)
x = (x & 0x3333) + ((x >>> 2) & 0x3333)
x = (x & 0x0F0F) + ((x >>> 4) & 0x0F0F)
answer = (x * 0x0101) >>> 8

Заметим, что операция $x\ \&\ 55_{16} + (x\ \texttt{\gt \gt \gt }\ 1)\ \&\ 55_{16}$ равносильна операции $x - (x\ \texttt{\gt \gt \gt }\ 1)\ \&\ 55_{16}$, в чем легко убедиться, рассмотрев все числа из двух бит.

В свою очередь, операцию $(x\ \&\ \texttt{0F0F}_{16}) + ((x\ \texttt{\gt \gt \gt }\ 4)\ \&\ \texttt{0F0F}_{16})$ можно заменить на $(x + (x\ \texttt{\gt \gt \gt }\ 4))\ \&\ \texttt{0F0F}_{16}$. Эта замена не повлияет на результат, так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок.

Таким образом, мы получили код, приведенный в начале раздела.

Разворот битов

Чтобы получить биты числа $x$, записанные в обратном порядке, применим следующий алгоритм.

// Пример приведен для 16-ти битных чисел.
// Для чисел других разрядностей нужны соответствующие константы.
x = ((x & 0x5555) << 1) | ((x >>> 1) & 0x5555)  // Четные и нечетные биты поменялись местами.
x = ((x & 0x3333) << 2) | ((x >>> 2) & 0x3333)  // Биты "перетасовываются" группами по два.
x = ((x & 0x0F0F) << 4) | ((x >>> 4) & 0x0F0F)  // Биты "перетасовываются" группами по четыре.
x = ((x & 0x00FF) << 8) | ((x >>> 8) & 0x00FF)  // Биты "перетасовываются" группами по восемь.

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

Применение для решения задач

Работа с битовыми масками

Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение $(\sim mask)$, пересечение $(mask_1\ \&\ mask_2)$, объединение $(mask_1 \mid mask_2)$ множеств, установить бит по номеру $(mask \mid (1\ \texttt{\lt \lt }\ x))$, снять бит по номеру $(mask\ \&\ \sim(1\ \texttt{\lt \lt }\ x))$.

Битовые маски используются, например, при решении некоторых задач динамического программирования.

См. также

• Определение булевой функции
• Сумматор
• Триггеры

Источники информации

• Онлайн справочник программиста на С и С++
• Побитовые операторы
• Bit Twiddling Hacks by Sean Eron Anderson
• Habrahabr — Алгоритмы поиска старшего бита
• STP's blog — Counting the number of set bits in an integer