关于i&(-i)的含义讨论分析

在树状数组之类的应用场合,时常出现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的位索引。

这里不仅仅是讨论这个问题,同时还提出了一种分析“任意”二进制位运算表达式的一种讨论方法,供大家参考。

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据