276
правок
Изменения
→Применение
==Применение==
===Сложные операции===
====Нахождение старшего единичного бита====
'''Способ 1'''
Рассмотрим некоторое число, представим его как <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>
result = x - (x >> 1)
</code>
'''Способ 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>.
</code>
====Подсчет количества единичных битбитов====
'''Способ 1'''
Самый простой способ посчитать количество единичных битов в числе <tex>x</tex> {{---}} сдвигать его на <tex>1</tex> вправо до тех пор, пока оно не станет равно нулю и в процессе смотреть на последний бит.
<code>
'''int''' answer = 0
'''Способ 2'''
Пусть мы хотим посчитать количество единичных бит битов в числе <tex>x</tex>. Если вычесть из <tex>x</tex> единицу, то его младший единичный бит обнулится, а все последующие за ним биты примут значение <tex>1</tex>. Если произвести операцию побитового И между <tex>x</tex> и <tex>(x - 1)</tex>, то мы получим число, побитово равное <tex>x</tex> во всех позициях, кроме младшего единичного бита <tex>x</tex> (в результирующем числе он будет нулевым). Таким образом, количество совершенных операций до того момента, как исходное число обратится в ноль, будет равно количеству единичных бит битов в нём.
<code>
answer++
</code>
====Циклический сдвиг влево====
Самый простой способ устроить циклический сдвиг числа, это объединить результаты обычных битовых сдвигов влево на необходимую величину и вправо на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.
head = x << a <font color = green>// x {{---}} изменяемое число
// a {{---}} число позиций, на которое хотим выполнить сдвиг</font>
'''if''' a != 0: tail = x >> (n - a) <font color = green>// n {{---}} разрядность числа x</font> '''else''': tail = 0
result = head | tail
</code>
====Разворот битов====
Чтобы получить биты числа <tex>x</tex>, записанные в обратном порядке, будем снимать значение младшего бита, умножать его на старшую незаписанную степень двойки и сдвигать число вправо на единицу для обработки следующих бит.
<code>
result = 0
position = 1 << (n - 1) <font color = green>// n {{---}} разрядность числа x</font>
'''while''' x != 0:
result += (x & 1) * position
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>. Тогда
<code>
<font color = green>// в константе '''CHAR_BIT''' хранится количество битов в одном байтеn {{---}} разрядность числа</font> mask = x >> ''sizeof''('''int''') * '''CHAR_BIT''' n - 1
abs = (x + mask) <tex>\oplus</tex> mask
Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int.
<code>
<font color = green>// в константе '''CHAR_BIT''' хранится количество битов в одном байтеn {{---}} разрядность чисел</font> min = y + ((x - y) & ((x - y) >> (''sizeof''('''int''') * '''CHAR_BIT''' n - 1))) max = x - ((x - y) & ((x - y) >> (''sizeof''('''int''') * '''CHAR_BIT''' n - 1)))
</code>
