Побитовое И, чтобы вычислить наибольшую степень двух, которая делит 'n' - C ++

Question

Читая двоичное индексированное дерево, я наткнулся на следующее выражение, которое магическим образом вычисляло наибольшую степень двух, которая делит данное число 'n'

n&-n

Я хотел бы получить формальный аргумент, почему это выражение делает то, что делает.Кроме того, есть много подобных трюков с использованием побитового оператора, которые могут сэкономить нам много времени и пригодиться.Пожалуйста, перечислите столько, сколько вы знаете.Например, 1 << n дает два возведенных в степень n.

Answer 1

Отвечая на свой вопрос, я не смог найти очень сложное решение, но это меня удовлетворилоПусть наибольшая степень двух, которая делит n, равна 2 ^k .
Это означает, что после последней 1 есть k нулей (если их нет, это дает n = 0 и n & -nтоже ноль, что правильно).

-n = ~n+1, следовательно, все цифры в n инвертированы, кроме последней и следующих нулей k.

Взятие побитового И приведет к последнему, за которым последуют k нулей, что в точности равно 2 ^k .
Некоторые из найденных мной хаков с использованием побитовых операторов:

x |(1 << k) устанавливает бит kth в единицу </p>

x & ~ (1 << k) устанавливает бит kth в ноль </p>

x ^ (1 << k) инвертирует бит kth </p>

x & (x − 1) устанавливает последний бит x в ноль

x & −x устанавливает все один бит в ноль, кроме последнего одного бита.

положительное число x является степенью двойки именно тогда, когда x & (x − 1) = 0.

Формула x |(x − 1) инвертирует все биты после последнего бита

Это может быть подтверждено аналогичными доказательствами.Я добавлю больше, когда я найду больше.