276
правок
Изменения
Нет описания правки
x = 7 <font color = green>// 00000111 (7)</font>
x = x << 5 <font color = green>// 11100000 (-32)</font>
x = x >> 2 <font color = green>// 00111000 (56)</font>
</code>
Пусть дано число <tex>x</tex>. Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа <tex>x</tex> можно определить, выполнив сдвиг вправо на всю длину переменной:
<code>
<font color = green>// в этом и следующих примерах в константе '''CHAR_BIT''' хранится количество битов в одном байте</font>
'''if''' x != 0
Используя побитовые операции можно также узнать, различны ли знаки двух переменных <tex>x</tex> и <tex>y</tex>. Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство <tex>((x \oplus y) < 0</tex> будет верно в том случае, если числа <tex>x</tex> и <tex>y</tex> разного знака.
====Нахождение старшего единичного бита====
'''Способ 1.'''
Рассмотрим некоторое число, пусть оно представимо как <tex>001bbbbb</tex>, где <tex>b</tex> {{---}} любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на 1 и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим число <tex>0011bbbb</tex>. Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на 2, то получим результат <tex>001111bb</tex>. Уже на следующем шаге число будет состоять только из нулей и единиц. Результатом выполнения действий <tex>x - (x \texttt{ >> }1)</tex> будет число, состоящее только из старшего бита исходного числа.
<code>
x |= x >> 1
x |= x >> 2
x |= x >> 4 <font color = green>// Для восьмибитных чисел будет достаточно такого количества операций
// если разрядность больше, надо добавить нужное количество следующих степеней двойки</font>
result = x - (x >> 1)
</code>
'''Способ 2.'''
Способ основан на [[Целочисленный двоичный поиск | бинпоиске]].
<code>
'''int''' x, m <font color = green>// x {{---}} исходное число</font>
'''int''' l = n <font color = green>// n {{---}} разрядность числа</font>
'''int''' r = -1
'''while''' r < l - 1:
m = (l + r) / 2
'''if''' (1 << m) < x:
r = m
'''else''':
l = m
result = r
</code>
====Вычисление модуля числа без использования условного оператора====
Пусть дано число <tex>x</tex>. Тогда
<code>
<font color = green>// в константе '''CHAR_BIT''' хранится количество битов в одном байте</font>
mask = x >> ''sizeof''('''int''') * '''CHAR_BIT''' - 1
Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int.
<code>
<font color = green>// в константе '''CHAR_BIT''' хранится количество битов в одном байте</font>
min = y + ((x - y) & ((x - y) >> (''sizeof''('''int''') * '''CHAR_BIT''' - 1)))
max = x - ((x - y) & ((x - y) >> (''sizeof''('''int''') * '''CHAR_BIT''' - 1)))
