Изменения

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

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

x = x >>> 2 <font color = green>// 00111000 (56)</font>

<font color '''int32''' getSign(x: '''int32'''): '''if''' x != green>// в константе 0: mask = 1 '''CHAR_BITelse''' хранится количество битов в одном байте</font>: mask = 0

'''ifreturn''' mask | (x !>> 31) <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> '''elseint32'''abs1(x: '''int32'''): mask = 0x >> 31 '''return''' (x + mask) '''XOR''' mask

sign = mask | '''int32''' abs2(x >> (: '''int32'sizeof''(): mask = x >> 31 '''intreturn'''(x + mask) * '''CHAR_BITXOR''' - 1)) <font color = green>// результатом будет -1, 0, или +1 // для отрицательного, равного нулю и положительного числа x соответственно</font>mask

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

Рассмотрим некоторое число, представим его как Пусть даны числа <tex>x</tex> и <tex>0\dots01b \dots by</tex>, где разрядности <tex>bn</tex> {{---}} любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на <tex>1x < y</tex> и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат то <tex>0\dots011b \dots b((x - y) >> (n - 1)) = -1</tex>. Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на а если <tex>2x \geqslant y</tex>, то получим <tex>((x - y) >> (n - 1)) = 0\dots01111b \dots b</tex>. При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций Выражение <tex>((x - y) \& ((x - y) >> (зависит от разрядности числаn - 1)) мы получим число вида </tex> принимает значение <tex>0\dots01\dots1</tex>. Тогда результатом выполнения действий , если <tex>x - (x \texttt{ geqslant y</tex>, и <tex> }1(x - y)</tex> будет число, состоящее только из старшего бита исходного числаесли <tex>x < y</tex>.

'''int32''' min(x |= , y: '''int32'''): '''return''' y + ((x - y) & ((x - y) >> 131)) x |= x >> 2 '''int32''' max(x |= x >> 4 <font color = green>// Для восьмибитных чисел будет достаточно такого количества операций // если разрядность больше, надо добавить нужное количество следующих степеней двойки</font>y: '''int32'''): result = '''return''' x - ((x - y) & ((x - y) >> 131))

Способ основан на [[Целочисленный двоичный поиск | бинпоиске]]. Будем искать максимальную степень двойкиОперация логического И в данном выражении отсекает тот случай, меньшую числа когда <tex>(x= 0)</tex>. и не является степенью двойки, но при этом правая часть <codetex> '''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) <tex>\leqslant)</tex> x: r = m '''else''': l = m result = r</code>равна единице.

Применим к числу <tex>x</tex> побитовое отрицание, чтобы инвертировать значения всех его битовбит, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом <tex>x</tex>, а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа <tex>(x\ \&\ (\sim x + 1))</tex>.

'''Способ 2''' Алгоритм аналогичен описанному выше способу нахождения ====Нахождение старшего единичного бита и также основан на [[Целочисленный двоичный поиск | бинпоиске]]. Будем искать максимальное ====Пусть дано число вида <tex>0\dots01\dots1x</tex> такое, что и необходимо узнать его побитовое И с числом <tex>x</tex> дает <tex>0</tex>старший единичный бит.

'''intint32''' greatestBit(x, m <font color = green>// x {{---}} исходное число</font> : '''intint32''' l = n <font color = green>// n {{---}} разрядность числа</font> '''int''' r = -1 '''while''' r < l - 1): m power = (l + r) / 21 '''iffor''' ((i = 1 <tex> \ldots\log_2{32}< m) - 1) & /tex>: x |== 0:x >> power r power <<= m1 '''elsereturn''': l = m result = rx - (x >> 1)

====Подсчет количества единичных битЦиклический сдвиг===='''Способ 1'''Пусть дано число <tex>x</tex> и надо совершить циклический сдвиг его битов на величину <tex>d</tex>.Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на <tex>d</tex> и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.

'''intint32''' answer = 0rotateLeft(x, d: '''int32'''): '''return''' (x << d) | (x >>> (32 - d)) '''whileint32''' rotateRight(x != 0, d: '''int32'''): answer += x & 1 '''return''' (x >> 1> d) | (x << (32 - d))

<font color = green>// Для чисел других разрядностей необходимо использовать соответствующие константы.</font> '''intint16''' answer = 0 setBitsNumber(x: '''whileint16''' x != 0): x &= x - ((x >>> 1) & 0x5555) answerx = (x & 0x3333) +((x >>> 2) & 0x3333) x = (x +(x >>> 4)) & 0x0F0F '''return''' (x * 0x0101) >>> 8

'''intint16''' head, tailsetBitsNumber(x: '''int16'''): head x = (x & 0x5555) + ((x >>> 1) & 0x5555) x << a <font color = green(x & 0x3333) + ((x >>// x {{---}} изменяемое число // a {{---}} число позиций, на которое хотим выполнить сдвиг</font>2) & 0x3333) tail x = (x & 0x0F0F) + ((x >> > 4) & 0x0F0F) '''return''' (n - ax * 0x0101) <font color = green>// n {{---}} разрядность числа x</font> result = head | tail> 8

Заметим, что операция <tex>x\ \&\ 55_{16} + (x\ \texttt{>>>}\ 1)\ \&\ 55_{16}</tex> равносильна операции <tex>x - (x\ \texttt{>>>}\ 1)\ \&\ 55_{16}</tex>, в чем легко убедиться, рассмотрев все числа из двух бит. В свою очередь, операцию <tex>(x\ \&\ \texttt{0F0F}_{16}) + ((x\ \texttt{>>>}\ 4)\ \&\ \texttt{0F0F}_{16})</tex> можно заменить на <tex>(x + (x\ \texttt{>>>}\ 4))\ \&\ \texttt{0F0F}_{16}</tex>. Эта замена не повлияет на результат, так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок. Таким образом, мы получили код, приведенный в начале раздела. ====Вычисление модуля числа без использования условного оператораРазворот битов====Пусть дано число Чтобы получить биты числа <tex>x</tex>, записанные в обратном порядке, применим следующий алгоритм. Тогда

<font color = green>// в константе '''CHAR_BIT''' хранится количество битов в одном байтеДля чисел других разрядностей нужны соответствующие константы.</font> mask = x >> ''sizeof'int16'''reverseBits(x: '''intint16''') * '''CHAR_BIT''' - : x = ((x & 0x5555) << 1) | ((x >>> 1) & 0x5555) <font color = green>// Четные и нечетные биты поменялись местами.</font> abs x = ((x + mask& 0x3333) <tex< 2) | ((x >\oplus>> 2) & 0x3333) <font color = green>// Биты "перетасовываются" группами по два.</texfont> mask x = ((x & 0x0F0F) << 4) | ((x >>> 4) & 0x0F0F) <font color = green>// другой способ сделать то же самое:Биты "перетасовываются" группами по четыре.</font> abs x = ((x & 0x00FF) <<tex8) | ((x >>>\oplus8) & 0x00FF) <font color = green>// Биты "перетасовываются" группами по восемь.</texfont> mask) - mask '''return''' x

====Нахождение минимума и максимума из двух чисел без использования условного оператора====Этот способ корректен только если можно утверждатьБолее подробно про то, что величина <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)))</code>]].