在树状数组之类的应用场合,时常出现i & (-i)这样的表达式,那么这个表达式到底是什么意思呢?
显然,i可以表示为以下三种形式: x...10...0 (即0个或多个任意0或1以及一个1,紧接着一个或多个0) x...1 以及 0... 。
我们先讨论第一种形式: i=x...10...0
显然由补码定义可知: -i=\bar{x}...01...1+1=\bar{x}...10...0
那么此时 i\&(-i)=0...10...0 ,此时值也就是2^k,其中k表示从低位到高位的第一个1的位索引。
然后我们讨论第二种形式,类似讨论,显然等于1,也就是2^0
最后我们讨论第三种形式,类似地,显然为0。
总结一下i & (-i)表示的2^k,其中k表示i中从低位到高位的第一个1的位索引。
这里不仅仅是讨论这个问题,同时还提出了一种分析“任意”二进制位运算表达式的一种讨论方法,供大家参考。