==Применение==
===Сложные операции===
====Нахождение старшего единичного битаОпределение знака числа====Пусть дано число <tex>x</tex> . Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа <tex>x</tex> можно определить, выполнив сдвиг вправо на всю длину переменной:<code> <font color = green>// n {{---}} разрядность числа</font> '''if''' x != 0 mask = 1 '''else''' mask = 0 sign = mask | (x >> (n - 1)) <font color = green>// результатом будет -1, 0, или +1 // для отрицательного, равного нулю и необходимо положительного числа x соответственно</font></code>Используя побитовые операции можно также узнать его старший единичный бит, различны ли знаки двух переменных <tex>x</tex> и <tex>y</tex>. Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Рассмотрим два способаПоэтому неравенство <tex>((x \oplus y) < 0</tex> будет верно в том случае, с помощью которых можно решить эту задачуесли числа <tex>x</tex> и <tex>y</tex> разного знака.
'''Способ 1'''====Вычисление модуля числа без использования условного оператора====Рассмотрим некоторое Пусть дано число, представим его как <tex>0\dots01b \dots bx</tex>, где . Если <tex>bx</tex> {{---}} любое значение бита. Тогдаположительно, если совершить битовый сдвиг этого числа вправо на то <tex>1mask = 0</tex> , и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат <tex>0(x + mask) \dots011b \dots boplus mask = x</tex>. Если мы повторим эту последовательность действий над полученным числомВ случае, но устроим сдвиг на если <tex>2x</tex>отрицательно, то получим <tex>0\dots01111b \dots bmask = -1</tex>. При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций (зависит от разрядности числа) Тогда получается, что мы получим число вида работаем с числом <tex>0\dots01\dots1x</tex>. Тогда результатом выполнения действий так, как будто оно представлено в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Код со сдвигом |коде со сдвигом]] с тем отличием, что у нас знаковый бит принимает значение <tex>x - (x \texttt{ 1</tex>для отрицательных чисел, а <tex> }1)0</tex> будет число, состоящее только из старшего бита исходного числа{{---}} для положительных.
<code>
'''int''' power = 1 '''for''' i = 1..<tex>\log_2{n}</tex>: <font color = green>// n {{---}} разрядность числа</font> mask = x |>> n - 1 abs = (x + mask) <tex>\oplus</tex> powermask power <font color = green>// другой способ сделать то же самое:<= 1/font> result abs = x - (x <tex>\oplus</tex> 1mask)- mask
</code>
'''Способ 2'''====Нахождение минимума и максимума из двух чисел без использования условного оператора==== Способ основан на [[Целочисленный двоичный поиск | бинпоиске]]. Будем искать максимальную степень двойкиЭтот способ корректен только если можно утверждать, меньшую числа что величина <tex>(x- y)</tex>лежит между граничными значениями типа int.
Пусть даны числа <tex>x</tex> и <tex>y</tex>. Тогда, если <tex>x < y</tex>, то <tex>((x - y) \texttt{>>} (n - 1)) = -1</tex> а если <tex>x \geqslant y</tex>, то <tex>((x - y) \texttt{>>} (n - 1)) = 0</tex>. Выражение <tex>((x - y) \& ((x - y) \texttt{>>} (n - 1))</tex> принимает значение <tex>0</tex>, если <tex>x \geqslant y</tex> и <tex>(x - y)</tex>, если <tex>x < y</tex>.
<code>
'''int''' x, m <font color = green>// x n {{---}} исходное числоразрядность чисел</font> '''int''' l min = n <font color = green>// n {{y + ((x -y) & ((x --}} разрядность числа</fonty) >> '''int''' r = (n -1))) '''while''' r < l max = x - 1: m = (l + r(x - y) / 2 '''if''' & ((1 << mx - y) <tex>\leqslant</tex> x: r = m '''else''': l = m result = r(n - 1)))
</code>
====Проверка на то, является ли число степенью двойки====
Пусть дано число <tex>x</tex>. Тогда, если результатом выражения <tex>(x\ \&\&\ !(x\ \&\ (x - 1)))</tex> является единица, то число <tex>x</tex> {{---}} степень двойки.
Правая часть выражения <tex>(!(x\ \&\ (x - 1)))</tex> будет равна единице только если число <tex>x</tex> равно <tex>0</tex> или является степенью двойки. Если число <tex>x</tex> является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: <tex>1\underbrace{0\dots0}_{n}</tex>, где <tex>n</tex> {{---}} показатель степени. Соответственно, выражение <tex>(x - 1)</tex> будет иметь вид <tex>\underbrace{1\dots1}_{n}</tex>, и <tex>x\ \&\ (x - 1)</tex> равно <tex>0</tex>.
Операция логического И в данном выражении отсекает тот случай, когда <tex>(x = 0)</tex> и не является степенью двойки, но при этом правая часть <tex>(!(x\ \&\ (x - 1)))</tex> равна единице.
====Нахождение младшего единичного бита====
Пусть дано число <tex>x</tex> и необходимо узнать его младший единичный бит. Задачу можно решить несколькими способами. '''Способ 1'''
Применим к числу <tex>x</tex> побитовое отрицание, чтобы инвертировать значения всех его бит, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом <tex>x</tex>, а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа <tex>(x\ \&\ (\sim x + 1))</tex>.
К такому же результату можно прийти, если сначала отнять от числа <tex>x</tex> единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в <tex>1</tex>, затем инвертировать результат и применить побитовое И с исходным числом <tex>(x\ \&\ \sim (x - 1))</tex>.
'''Способ 2''' Алгоритм аналогичен описанному выше способу нахождения ====Нахождение старшего единичного бита и также основан на [[Целочисленный двоичный поиск | бинпоиске]]. Будем искать максимальное ====Пусть дано число вида <tex>0\dots01\dots1x</tex> такое, что и необходимо узнать его побитовое И с числом <tex>x</tex> дает <tex>0</tex>старший единичный бит.
Рассмотрим некоторое число, представим его как <tex>0\dots01b \dots b</tex>, где <tex>b</tex> {{---}} любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на <tex>1</tex> и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат <tex>0\dots011b \dots b</tex>. Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на <tex>2</tex>, то получим <tex>0\dots01111b \dots b</tex>. При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций (зависит от разрядности числа) мы получим число вида <tex>0\dots01\dots1</tex>. Тогда результатом выполнения действий <tex>x - (x \texttt{ >> }1)</tex> будет число, состоящее только из старшего бита исходного числа.
<code>
'''int''' x, m <font color power = green>// x {{---}} исходное число</font>1 '''intfor''' l i = 1..<tex>\log_2{n }</tex>: <font color = green>// n {{---}} разрядность числа</font> '''int''' r = -1 '''while''' r < l - 1: m x |= (l + r) / 2x >> power '''if''' ((1 power << m) - = 1) & x == 0: r = m '''else''': l = m result = rx - (x >> 1)
</code>
position >>= 1
x >>= 1
</code>
====Проверка на то, является ли число степенью двойки====
Пусть дано число <tex>x</tex>. Тогда, если результатом выражения <tex>(x\ \&\&\ !(x\ \&\ (x - 1)))</tex> является единица, то число <tex>x</tex> {{---}} степень двойки.
Правая часть выражения <tex>(!(x\ \&\ (x - 1)))</tex> будет равна единице только если число <tex>x</tex> равно <tex>0</tex> или является степенью двойки. Если число <tex>x</tex> является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: <tex>1\underbrace{0\dots0}_{n}</tex>, где <tex>n</tex> {{---}} показатель степени. Соответственно, выражение <tex>(x - 1)</tex> будет иметь вид <tex>\underbrace{1\dots1}_{n}</tex>, и <tex>x\ \&\ (x - 1)</tex> равно <tex>0</tex>.
Операция логического И в данном выражении отсекает тот случай, когда <tex>(x = 0)</tex> и не является степенью двойки, но при этом правая часть <tex>(!(x\ \&\ (x - 1)))</tex> равна единице.
====Определение знака числа====
Пусть дано число <tex>x</tex>. Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа <tex>x</tex> можно определить, выполнив сдвиг вправо на всю длину переменной:
<code>
<font color = green>// n {{---}} разрядность числа</font>
'''if''' x != 0
mask = 1
'''else'''
mask = 0
sign = mask | (x >> (n - 1)) <font color = green>// результатом будет -1, 0, или +1
// для отрицательного, равного нулю и положительного числа x соответственно</font>
</code>
Используя побитовые операции можно также узнать, различны ли знаки двух переменных <tex>x</tex> и <tex>y</tex>. Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство <tex>((x \oplus y) < 0</tex> будет верно в том случае, если числа <tex>x</tex> и <tex>y</tex> разного знака.
====Вычисление модуля числа без использования условного оператора====
Пусть дано число <tex>x</tex>. Если <tex>x</tex> положительно, то <tex>mask = 0</tex>, и <tex>(x + mask) \oplus mask = x</tex>. В случае, если <tex>x</tex> отрицательно, <tex>mask = -1</tex>. Тогда получается, что мы работаем с числом <tex>x</tex> так, как будто оно представлено в [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код #Код со сдвигом |
коде со сдвигом]] с тем отличием, что у нас знаковый бит принимает значение <tex>1</tex> для отрицательных чисел, а <tex>0</tex> {{---}} для положительных.
<code>
<font color = green>// n {{---}} разрядность числа</font>
mask = x >> n - 1
abs = (x + mask) <tex>\oplus</tex> mask
<font color = green>// другой способ сделать то же самое:</font>
abs = (x <tex>\oplus</tex> mask) - mask
</code>
====Нахождение минимума и максимума из двух чисел без использования условного оператора====
Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int.
Пусть даны числа <tex>x</tex> и <tex>y</tex>. Тогда, если <tex>x < y</tex>, то <tex>((x - y) \texttt{>>} (n - 1)) = -1</tex> а если <tex>x \geqslant y</tex>, то <tex>((x - y) \texttt{>>} (n - 1)) = 0</tex>. Выражение <tex>((x - y) \& ((x - y) \texttt{>>} (n - 1))</tex> принимает значение <tex>0</tex>, если <tex>x \geqslant y</tex> и <tex>(x - y)</tex>, если <tex>x < y</tex>.
<code>
<font color = green>// n {{---}} разрядность чисел</font>
min = y + ((x - y) & ((x - y) >> (n - 1)))
max = x - ((x - y) & ((x - y) >> (n - 1)))
</code>
