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

ВНИМАНИЕ, СТАТЬЯ НАХОДИТСЯ В РАЗРАБОТКЕ

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

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

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

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

Побитовое И

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

&
	11001010 11100010
	11000010

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

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

|
	11001010 11100010
	11101010

Побитовое НЕ

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

~
	11001010
	00110101

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

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

^
	11001010 11100010
	00101000

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

Операторы сдвига [math]\ll[/math] и [math]\gg[/math] сдвигают биты в переменной влево или вправо на указанное число. Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.

x = 7     //00000111
x << 1    //00001110
x << 5    //11000000
x >> 2    //00110000

Ограничения

C++ Visual Studio 15

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

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

   short x = 16384    // 01000000 00000000
   short y = x << 1   // 10000000 00000000
                      // 16384 left-shifted by 1 = -32768

Java

В языке программирования Java существует также оператор беззнакового битового сдвига вправо [math]\ggg[/math]. При использовании этого оператора на освободившиеся позиции всегда устанавливаются [math]0[/math], тогда как при использовании [math]\gg[/math] на освободившиеся позиции устанавливается бит знака.

При использовании битовых сдвигов есть некоторое отличие от целочисленного деления на [math]2[/math]: если сдвигать отрицательное число вправо, то сначала это аналогично целочисленному делению на [math]2[/math], но когда останется [math]-1[/math], то при следующих сдвигах результат меняться не будет. То есть происходит округление не к нулю, как при целочисленном делении, а к [math]-1[/math].

Также нельзя сдвинуть число на количество бит большее, чем разрядность операнда. При этом происходит неявное сокращение правого операнда (количество бит).

Примеры:

i = 1      //00000000 00000000 00000000 00000001 (1)
i << 29    //00100000 00000000 00000000 00000000 (536870912)
i << 30    //01000000 00000000 00000000 00000000 (1073741824)
i << 31    //10000000 00000000 00000000 00000000 (-2147483648 / 2147483648)
i << 32    //00000000 00000000 00000000 00000001 (1)

i = -1      //11111111 11111111 11111111 11111111 (-1 / 4294967295)
i >>> 1     //01111111 11111111 11111111 11111111 (2147483647)
i >>> 30    //00000000 00000000 00000000 00000011 (3)
i >>> 31    //00000000 00000000 00000000 00000001 (1)
i >>> 32    //11111111 11111111 11111111 11111111 (-1 / 4294967295)

i = -192    //11111111 11111111 11111111 01000000 (-192 / 4294967104)
i >> 1      //11111111 11111111 11111111 10100000 (-96 / 4294967200)
i >> 30     //11111111 11111111 11111111 11111111 (-1 / 4294967295)
i >> 31     //11111111 11111111 11111111 11111111 (-1 / 4294967295)
i >> 32     //11111111 11111111 11111111 01000000 (-192 / 4294967104)

Арифметическое распространение в Java проводится перед операциями и гарантирует расширение каждого операнда по крайней мере до int (или, если один из операндов имеет больший тип, то до него). Расширение происходит знаково, ввиду чего результат может быть не таким, как ожидалось; при приведении типа к меньшему лишние байты отбрасываются.

Примеры:

byte b = -127   //10000001 (-127 / 129)
(int)b          //11111111 11111111 11111111 10000001 (-127 / 4294967169)

int i = -127    //11111111 11111111 11111111 10000001 (-127 / 4294967169)
(byte)i         //10000001 (-127 / 129)

int i = 128     //00000000 00000000 00000000 10000000 (128)
(byte)i         //10000000 (-128 / 128)

int i = 256     //00000000 00000000 00000001 00000000 (256)
(byte)i         //00000000 (0)

int i = -256    //11111111 11111111 11111111 00000000 (-256 / 4294967040)
(byte)i         //00000000 (0)

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

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

answer = x && !(x & (x - 1)) // если answer == 1, то число x является степенью двойки

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

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

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

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

// в этом и следующих примерах в константе CHAR_BIT хранится количество битов в одном байте
sign = x >> (sizeof(int) * CHAR_BIT - 1)    // если x < 0, результатом будет -1, иначе 0 

sign = (x != 0) | (x >> (sizeof(int) * CHAR_BIT - 1))    // результатом будет -1, 0, или +1 
                                                         // для отрицательного, равного нулю и положительного числа x соответственно

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

bool result = ((x [math]\oplus[/math] y) < 0)    // значение переменной result == true, если знаки переменных x и y различны

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

mask = x >> sizeof(int) * CHAR_BIT - 1

abs = (x + mask) [math]\oplus[/math] mask
// другой способ сделать то же самое:
abs = (x [math]\oplus[/math] mask) - mask

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

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

min = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))
max = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))

Кодирование информации

// функция для шифровки текста с помощью XOR
function encode(secret: string, key: string): byte[]
    btxt = secret.getBytes
    bkey = key.getBytes

    for i = 0 .. btxt.length:
        result[i] = (btxt[i] [math]\oplus[/math] bkey[i % bkey.length]) as byte

    return result

// функция для расшифровки текста
function decode(secret: byte[], key: string): string
    bkey = key.getBytes

    for i = 0 .. secret.length:
        result[i] = (secret[i] [math]\oplus[/math] bkey[i % bkey.length]) as byte

    return result as string

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

Онлайн справочник программиста на С и С++

MSDN: Операторы сдвигов влево и вправо

Битовые сдвиги и приведения в Java: подводные камни

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

Bit Twiddling Hacks by Sean Eron Anderson