276
правок
Изменения
→Применение
Пусть дано число <tex>x</tex>. Тогда, если результатом выражения <tex>(x\ \&\&\ !(x\ \&\ (x - 1)))</tex> является единица, то число <tex>x</tex> {{---}} степень двойки.
Правая часть выражения <tex>(!(x\ \&\ (x - 1)))</tex> будет равна единице только если число <tex>x</tex> равно <tex>0</tex> или является степенью двойки. Если число <tex>x</tex> является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: <tex>1\underbrace{0\dots0}_{n}</tex>, где <tex>n</tex> {{---}} показатель степени. Соответственно, выражение <tex>(x - 1)</tex> будет иметь вид <tex>\underbrace{1\dots1}_{n}</tex>, и выражение <tex>x\ \&\ (x - 1)</tex> равно <tex>0</tex>.
Операция логического И в данном выражении отсекает тот случай, когда <tex>(x = 0)</tex> и не является степенью двойки, но при этом правая часть выражения <tex>(!(x\ \&\ (x - 1)))</tex> равна единице.
====Определение знака числа====
'''Способ 1.'''
Рассмотрим некоторое число, пусть оно представимо представим его как <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> будет число, состоящее только из старшего бита исходного числа.
<code>
x |= x >> 1
'''Способ 2.'''
Способ основан на [[Целочисленный двоичный поиск | бинпоиске]]. Будем искать максимальную степень двойки, меньшую числа <tex>x</tex>.
<code>
'''while''' r < l - 1:
m = (l + r) / 2
'''if''' (1 << m) < tex>\leqslant</tex> x:
r = m
'''else''':
result = r
</code>
====Нахождение младшего единичного бита====
'''Способ 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>
'''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) - 1) & x == 0:
r = m
'''else''':
l = m
result = r
</code>
====Вычисление модуля числа без использования условного оператора====
Пусть дано число <tex>x</tex>. Тогда
