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

2016-03-08T08:48:40Z

109.205.249.5: /* Побитовые сдвиги */

'''Побитовые операции''' (англ. ''bitwise operations'') — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: [[Определение булевой функции | логические операции]] и побитовые сдвиги.
==Принцип работы==
===Логические побитовые операции===
Битовые операторы И <tex>(AND,\ \&)</tex>, ИЛИ <tex>(OR,\ \mid)</tex>, НЕ <tex>(NOT,\ \sim)</tex> и исключающее ИЛИ <tex>(XOR,\ $\textasciicircum$,\ \oplus)</tex> используют те же таблицы истинности, что и их логические эквиваленты.
====Побитовое И====
Побитовое И используется для выключения битов. Любой бит, установленный в <tex>0</tex>, вызывает установку соответствующего бита результата также в <tex>0</tex>.
{|class="wikitable"
!rowspan=2|&
|-
|11001010 11100010
|-
|||11000010
|}
====Побитовое ИЛИ====
Побитовое ИЛИ используется для включения битов. Любой бит, установленный в <tex>1</tex>, вызывает установку соответствующего бита результата также в <tex>1</tex>.
{|class="wikitable"
!rowspan=2| |
|-
|11001010 11100010
|-
|||11101010
|}
====Побитовое НЕ====
Побитовое НЕ инвертирует состояние каждого бита исходной переменной.
{|class="wikitable"
!rowspan=2| ~
|-
|11001010
|-
|||00110101
|}
====Побитовое исключающее ИЛИ====
Исключающее ИЛИ устанавливает значение бита результата в <tex>1</tex>, если значения в соответствующих битах исходных переменных различны.
{|class="wikitable"
!rowspan=2| ^
|-
|11001010 11100010
|-
|||00101000
|}

===Побитовые сдвиги===
Операторы сдвига <tex>\texttt{<<}</tex> и <tex>\texttt{>>}</tex> сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Дополнительный код (дополнение до двух) | двоичном дополнительном коде]] и необходимо поддерживать знаковый бит).

Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.
<code>
x = 7 // 00000111 (7)
x = x >> 1 // 00000011 (3)
x = x << 1 // 00000110 (6)
x = x << 5 // 11000000 (-64)
x = x >> 2 // 11110000 (-16)
</code>

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

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

==Применение==
===Сложные операции===
====Проверка на то, является ли число степенью двойки====
Пусть дано число <tex>x</tex>. Тогда, если результатом выражения <tex>(x\ \&\&\ !(x\ \&\ (x - 1)))</tex> является единица, то число <tex>x</tex> {{---}} степень двойки.

====Определение знака числа====
Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа можно определить следующим образом:
<code>
// в этом и следующих примерах в константе '''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 соответственно
</code>
Используя побитовые операции можно также узнать, различны ли знаки двух переменных:
<code>
'''bool''' result = ((x <tex>\oplus</tex> y) < 0) // значение переменной result == ''true'', если знаки переменных x и y различны
</code>

====Вычисление модуля числа без использования условного оператора====
<code>
mask = x >> ''sizeof''('''int''') * '''CHAR_BIT''' - 1

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

====Нахождение минимума и максимума из двух чисел без использования условного оператора====
Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int.
<code>
min = y + ((x - y) & ((x - y) >> (''sizeof''('''int''') * '''CHAR_BIT''' - 1)))
max = x - ((x - y) & ((x - y) >> (''sizeof''('''int''') * '''CHAR_BIT''' - 1)))
</code>

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

Битовые маски используются, например, при решении некоторых задач<ref>[[Гамильтоновы графы #Задача о коммивояжере| Динамическое программирование по подмножествам (по маскам)]]</ref> [[Динамическое программирование | динамического программирования]].

====Алгоритм Флойда====
{{main|Алгоритм Флойда}}

====Дерево Фенвика====
{{main|Дерево Фенвика}}

==Примечания==
<references/>

==Источники информации==
* [http://www.c-cpp.ru/books/bitovye-operatory Онлайн справочник программиста на С и С++]
* [http://developer.alexanderklimov.ru/android/java/bitwise.php Побитовые операторы]
* [https://graphics.stanford.edu/~seander/bithacks.html Bit Twiddling Hacks by Sean Eron Anderson]

Викиконспекты - Вклад участника [ru]

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