====Подсчет количества единичных битов====
'''Способ 1''' Самый простой способ посчитать количество Для подсчета количества единичных битов в числе <tex>x</tex> {{---}} сдвигать его на <tex>1</tex> вправо до тех пор, пока оно не станет равно нулю и в процессе смотреть на последний бит.можно воспользоваться следующим алгоритмом:
<code>
'''int''' answer <font color = 0green>// Пример приведен для 16-ти битных чисел. // Для чисел большей разрядности необходимо использовать соответствующие константы.</font> '''while''' x != 0:x - ((x >>> 1) & 0x5555) answer x = (x & 0x3333) +((x >>> 2) & 0x3333) x = (x + (x >>> 4)) & 10x0F0F answer = (x * 0x0101) >>> 18
</code>
'''Способ 2'''
Пусть мы хотим посчитать количество единичных битов Поскольку <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>1x</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>x00110011 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>8</tex> (для шестнадцатибитных чисел), мы получим долгожданный ответ.
Подведем итог:
<code>
'''int''' answer x = 0(x & 0x5555) + ((x >>> 1) & 0x5555) '''while''' x != 0:(x & 0x3333) + ((x >>> 2) & 0x3333) x = (x &= 0x0F0F) + ((x - 1>>> 4) & 0x0F0F) answer++= (x * 0x0101) >>> 8
</code>
Заметим, что операция <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>. Эта замена не повлияет на результат, так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок.
Таким образом, мы получили код, приведенный в начале раздела.
====Циклический сдвиг влево====
