v&(-v)

以上就是全部运算内容。

原因在于 -v 的补码表示为 ~v + 1 , +1 使得 ~v 的最低位的 0 变为了 1 而从末位开始的 1 都变成了 0。

那么在 &v ,v 中最低位的 1 在取反后变为了 0 ,在 +1 后又变为了 1 ,最低位的 1 不变。

最低位 1 之前(从小端开始,向大端)的 0 自然在与运算后继续保持 0。

而最低位 1 之后的 1 因为取反变为 0 ,与运算之后仍是 0 ,又因为最低位 1 取反后的 0 “吸收” 了进位,不会由进位产生反转。

应用

在树状数组中,判断当前节点对应的区间:

即 $c_i$ 所对应的区间为 [i - ( i & ( -i)) + 1, i]