Почему бит-операция i & (-i) равна самому правому биту?

Question

Я узнал алгоритм Fenwick Tree и был написан «i & (-i) равен самому правому биту».
Например, 3 & (-3) = 1, 48 & (-48) = 16..

Я проверил результат для i <= 64, и все значения удовлетворяли условию.
Но я не знаю, почему условие удовлетворяет (доказательство) для всего положительного целого i.

Пожалуйста, скажите мне, как это доказать.

EDIT: Вы можете предположить, что i - 32-разрядное целое (но 16-разрядное - это нормально). Если это так, диапазон значений i равен 1 <= i <= 2^31-1.

Answer 1

Допустим, у вас есть двоичное дополнение двоичное число i:

0b1101001010000000 

и вы хотите найти -i. Ну, -i - это число, такое как i + (-i) == 0. Итак, какое количество имеет это свойство? Ну, если вы строите другой номер:

i: 0b1101001010000000 
-i: 0b0010110110000000 

таким образом, что крайний правый набор бит такой же, как и в i, все биты после этого являются 0, и все биты до того, что являются обратными тех, кто в i:

i: 0b11010010 1 0000000 
-i: 0b00101101 1 0000000 

Затем, когда вы добавляете эти числа вместе, переносы распространяются с левой стороны номера и оставляют все 0 бит, поэтому это -i.

Теперь, что мы получим, если мы получим & эти цифры? Ну, конечные нули & вместе для создания нулей. Биты слева являются противоположностями в i и -i, поэтому они & вместе для создания нулей. Но самый правый бит бит равен 1 как в i, так и в -i, так что это единственный бит в i & -i.

 i: 0b11010010 1 0000000 
    -i: 0b00101101 1 0000000 
i & -i: 0b00000000 1 0000000 

Answer 2

Он даже работает для отрицательных целых чисел, это не имеет большого значения, мы можем доказать это для битстрон в целом.

Сначала i != 0 случай:

Использование строки обозначения,

- (а10 ^к) = (~ а) 10 ^к (либо по определению, или при разработке -x = ~x + 1)

Обратите внимание, что число, которое не равно 0, всегда имеет вид a10 ^k, то есть оно начинается с «ничего», затем имеет самый правый 1, за которым следует любое количество нулей (возможно, нулевые нули).

Затем

а10 ^к & (~ а) 10 ^к = 10 ^к ('а' отменяет со своим обратным)

Для 0 случае, хорошо, есть ни один правый крайний 1, так что это тоже не результат.

Answer 3

Когда вы уменьшаете двоичное дополнение целого, вы:

1. Найдите самый правые 1 бит и установите его в 0; и
2. Установите все биты нижнего порядка 1

i-1, следовательно, имеет все 1 бит, что i имеет, кроме самого правого одной.

комплемента, ~(i-1), поэтому не разделяет не 1 бит с i, за исключением того, что он крайний правый, так i & ~(i-1) содержит только крайний правый 1 бит в i.

Это можно немного упростить, если учесть, что ~x = -x-1, поэтому ~(i-1) = -(i-1)-1 = -i. Таким образом, самый правый 1 бит в i равен i&-i