Изменения

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

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

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

====Проверка на то, является ли число степенью двойкиОпределение знака числа====Пусть дано число <tex>x</tex>. ТогдаПоскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, если результатом выражения знак числа <tex>(x\ \&\&\ !(x\ \&\ (x - 1)))</tex> является единицаможно определить, то число выполнив сдвиг вправо на всю длину переменной:<texcode> '''int32''' getSign(x</tex> {{---}} степень двойки.: '''int32'''): '''if''' x != 0: mask = 1 '''else''': mask = 0

Правая часть выражения <tex>(! '''return''' mask | (x\ \&\ (x - 1))>> 31) <font color = green>//tex> результатом будет равна единице только если число <tex>-1, 0, или +1 // для отрицательного, равного нулю и положительного числа xсоответственно</tex> равно <texfont>0</texcode> или является степенью двойки. Если число Используя побитовые операции можно также узнать, различны ли знаки двух переменных <tex>x</tex> является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: и <tex>1\underbrace{0\dots0}_{n}y</tex>. Если числа имеют различный знак, то результат операции XOR, где <tex>n</tex> {{---}} показатель степенипроизведенной над их знаковыми битами, будет единицей. Соответственно, выражение Поэтому неравенство <tex>(x - 1\oplus y)< 0</tex> будет иметь вид <tex>\underbrace{1\dots1}_{n}</tex>верно в том случае, и выражение если числа <tex>x\ \&\ (x - 1)</tex> равно и <tex>0y</tex>разного знака.

Операция логического И в данном выражении отсекает тот случай====Вычисление модуля числа без использования условного оператора====Пусть дано число <tex>x</tex>. Если <tex>x</tex> положительно, когда то <tex>(x 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> '''int32''' abs1(x: '''int32'''): mask = x >> 31 '''return''' (x + mask)'''XOR''' mask '''int32''' abs2(x: '''int32'''): mask = x >> 31 '''return''' (x + mask)'''XOR''' mask</texcode> равна единице.

====Определение знака числаНахождение минимума и максимума из двух чисел без использования условного оператора====Этот способ корректен только если можно утверждать, что величина <tex>(x - y)</tex> лежит между граничными значениями типа int. Пусть дано число даны числа <tex>x</tex> и <tex>y</tex> разрядности <tex>n</tex>. Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знакаТогда если <tex>x < y</tex>, то <tex>((x - y) >> (n - 1)) = -1</tex>, знак числа а если <tex>x \geqslant y</tex>, то <tex>((x - y) >> (n - 1)) = 0</tex>. Выражение <tex>((x - y) \& ((x - y) >> (n - 1))</tex> принимает значение <tex>0</tex>, если <tex>x \geqslant y</tex>, и <tex>(x- y)</tex> можно определить, выполнив сдвиг вправо на всю длину переменной:если <tex>x < y</tex>.

<font color = green>// в константе '''CHAR_BITint32''' min(x, y: '''int32'''): '''return''' хранится количество битов в одном байте</fonty + ((x - y) & ((x - y) >>31))

'''ifint32''' max(x != 0, y: '''int32'''): mask = 1 '''elsereturn'''x - ((x - y) & ((x - y) >> 31))</code>  mask = 0===Проверка на то, является ли число степенью двойки====Пусть дано число <tex>x</tex>. Тогда, если результатом выражения <tex>(x\ \&\&\ !(x\ \&\ (x - 1)))</tex> является единица, то число <tex>x</tex> {{---}} степень двойки.

sign = mask | Правая часть выражения <tex>(!(x >> \ \&\ (''sizeof''('''int''') * '''CHAR_BIT''' x - 1)) )</tex> будет равна единице, только если число <tex>x</tex> равно <font color = greentex>0</tex> или является степенью двойки. Если число <tex>x</ результатом будет -tex> является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: <tex>1\underbrace{0\dots0}_{n}</tex>, 0где <tex>n</tex> {{---}} показатель степени. Соответственно, или +выражение <tex>(x - 1 )</tex> будет иметь вид <tex>\underbrace{1\dots1}_{n}</ для отрицательногоtex>, равного нулю и положительного числа <tex>x\ \&\ (x соответственно- 1)</fonttex> равно <tex>0</codetex>. Используя побитовые операции можно также узнатьОперация логического И в данном выражении отсекает тот случай, различны ли знаки двух переменных когда <tex>(x= 0)</tex> и не является степенью двойки, но при этом правая часть <tex>(!(x\ \&\ (x - 1)))</tex> равна единице. ====Нахождение младшего единичного бита====Пусть дано число <tex>yx</tex>и необходимо узнать его младший единичный бит. Если числа имеют различный знак Применим к числу <tex>x</tex> побитовое отрицание, то результат операции XORчтобы инвертировать значения всех его бит, произведенной над их знаковыми битамиа затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом <tex>x</tex>, будет единицейа вторая часть совпадает. Поэтому неравенство Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа <tex>(x\ \&\ (\sim x \oplus y+ 1)) < 0</tex> будет верно в том случае. К такому же результату можно прийти, если сначала отнять от числа <tex>x</tex> единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в <tex>1</tex>, затем инвертировать результат и применить побитовое И с исходным числом <tex>y(x\ \&\ \sim (x - 1))</tex> разного знака.

'''Способ 1Пусть дано число <tex>x</tex> и необходимо узнать его старший единичный бит.'''

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

'''int32''' greatestBit(x |: '''int32'''): power = x >> 1 x | '''for''' i = x 1 <tex>\ldots\log_2{32}</tex> 2: x |= x >> 4 power power <<font color = green>// Для восьмибитных чисел будет достаточно такого количества операций // если разрядность больше, надо добавить нужное количество следующих степеней двойки</font>1 result = '''return''' x - (x >> 1)

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

Способ основан на [[Целочисленный двоичный поиск <code> '''int32''' rotateLeft(x, d: '''int32'''): '''return''' (x << d) | бинпоиске]].(x >>> (32 - d)) '''int32''' rotateRight(x, d: '''int32'''): '''return''' (x >>> d) | (x << (32 - d))</code>

'''int''' x, m <font color = green>// x {{---}} исходное числоДля чисел других разрядностей необходимо использовать соответствующие константы.</font> '''intint16''' l = n <font color = green>// n {{---}} разрядность числа</font> setBitsNumber(x: '''intint16''' r ): x = x -((x >>> 1 '''while''' r < l - 1:) & 0x5555) m x = (l x & 0x3333) + r((x >>> 2) & 0x3333) / 2 '''if''' x = (x + (1 << mx >>> 4)) < x: r = m& 0x0F0F '''elsereturn''': l = m result = r(x * 0x0101) >>> 8

====Вычисление модуля Поскольку <tex>5555_{16}</tex> равно <tex>01010101 01010101_{2}</tex>, результатом операции <tex>x\ \&\ 5555_{16}</tex> является число, в котором все нечетные биты соответствуют нечетным битам числа <tex>x</tex>. Аналогично, результатом операции <tex>(x\ \texttt{>>>}\ 1)\ \&\ 5555_{16}</tex> является число, в котором все нечетные биты соответствуют четным битам <tex>x</tex>. Четные биты результата в обоих случаях равны нулю. Мысленно разобьем двоичную запись нашего числа <tex>x</tex> на группы по <tex>2</tex> бита. Результатом операции <tex>x\ \&\ 5555_{16} + (x\ \texttt{>>>}\ 1)\ \&\ 5555_{16}</tex> будет такое число, что если разбить его двоичную запись на группы по два бита, значение каждой группы соответствует количеству единичных битов в соответствующей паре битов числа без использования условного оператора==<tex>x</tex>. Аналогично, число <tex>3333_{16}</tex> равно <tex>00110011 00110011_{2}</tex> и операция <tex>x =(x\ \&\ 3333_{16}) + (x\ \texttt{>>>}\ 2\ \&\ 3333_{16})</tex>, примененная к результату, полученному на первом этапе, выполняет подсчет количества единичных битов в блоках по <tex>4</tex>. В свою очередь, число <tex>\texttt{0F0F}_{16}</tex> равно <tex>00001111 00001111_{2}</tex> и операция <tex>x =(x\ \&\ \texttt{0F0F}_{16}) + (x\ \texttt{>>>}\ 4\ \&\ \texttt{0F0F}_{16})</tex> позволяет подсчитать число единичных бит в блоках по <tex>8</tex>. Пусть дано число Теперь необходимо просуммировать числа, записанные в блоках по <tex>8</tex> битов, чтобы получить искомую величину. Это можно сделать, домножив результат на <tex>0101_{16}</tex> <tex>(1 00000001_{2})</tex>. Ответ на задачу будет находиться в первых восьми битах произведения. Выполнив сдвиг вправо на <tex>x8</tex>(для шестнадцатибитных чисел), мы получим долгожданный ответ. Тогда  Подведем итог:

<font color = green>// в константе '''CHAR_BITint16''' хранится количество битов в одном байте</font> mask = setBitsNumber(x >> : ''sizeof''('''intint16''') * '''CHAR_BIT''' - 1: abs x = (x & 0x5555) + mask) <tex((x >>\oplus</tex> mask1) & 0x5555) <font color x = green(x & 0x3333) + ((x >>// другой способ сделать то же самое:</font>2) & 0x3333) abs x = (x <tex& 0x0F0F) + ((x >\oplus</tex> mask> 4) - mask& 0x0F0F) '''return''' (x * 0x0101) >>> 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 - y)</tex> лежит между граничными значениями типа int, записанные в обратном порядке, применим следующий алгоритм.

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