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]