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>
'''Способ 2.'''
Способ основан на [[Целочисленный двоичный поиск | бинпоиске]]. Будем искать максимальную степень двойки, меньшую числа <tex>x</tex>.
====Нахождение младшего единичного бита====
'''Способ 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>.
'''Способ 2.'''
Алгоритм аналогичен описанному выше способу нахождения старшего единичного бита и также основан на [[Целочисленный двоичный поиск | бинпоиске]]. Будем искать максимальное число вида <tex>0\dots01\dots1</tex> такое, что его побитовое И с числом <tex>x</tex> дает <tex>0</tex>.
</code>
====Подсчет количества единичных битовбит===='''Способ 1.'''
Самый простой способ посчитать количество единичных битов в числе <tex>x</tex> {{---}} сдвигать его на <tex>1</tex> вправо до тех пор, пока оно не станет равно нулю и смотреть на последний бит.
x >> 1
</code>
'''Способ 2.'''
Пусть мы хотим посчитать количество единичных бит в числе <tex>x</tex>. Если вычесть из <tex>x</tex> единицу, то его младший единичный бит обнулится, а все последующие за ним биты примут значение <tex>1</tex>. Если произвести операцию побитового И между <tex>x</tex> и <tex>(x - 1)</tex>, то мы получим число, побитово равное <tex>x</tex> во всех позициях, кроме младшего единичного бита <tex>x</tex> (в результирующем числе он будет нулевым). Таким образом, количество совершенных операций до того момента, как исходное число обратится в ноль, будет равно количеству единичных бит в нём.
x &= x - 1
answer++
</code>
====Циклический сдвиг====
Самый простой способ устроить циклический сдвиг числа, это объединить результаты обычных битовых сдвигов влево и вправо на соответствующие величины. Таким образом, мы сможем поменять местами начальную и конечную части числа.
'''Сдвиг влево'''
<code>
'''int''' head, tail
head = x << a <font color = green>// x {{---}} изменяемое число
// a {{---}} число позиций, на которое хотим выполнить сдвиг</font>
tail = x >> (n - a) <font color = green>// n {{---}} разрядность числа x</font>
result = head | tail
</code>
'''Сдвиг вправо'''
<code>
'''int''' head, tail
head = x << (n - a) <font color = green>// x {{---}} изменяемое число
// a {{---}} число позиций, на которое хотим выполнить сдвиг</font>
tail = x >> a <font color = green>// n {{---}} разрядность числа x</font>
result = head | tail
</code>
====Вычисление модуля числа без использования условного оператора====
