发布日期:2020-04-08 21:50:05

lowbit = m & -m = 2的k次方 k为x从最右到左连续0的个数。(0除外)

这里利用的负数的存储特性,负数是以补码存储的,对于整数运算 x&(-x)有

● 当x为0时,即 0 & 0,结果为0;

●当x为奇数时,最后一个比特位为1,取反加1没有进位,故x和-x除最后一位外前面的位正好相反,按位与结果为0。结果为1。

●当x为偶数,且为2的m次方时,x的二进制表示中只有一位是1(从右往左的第m+1位),其右边有m位0,故x取反加1后,从右到左第有m个0,第m+1位及其左边全是1。这样,x& (-x) 得到的就是x。

●当x为偶数,却不为2的m次方的形式时,可以写作x= y * (2^k)。其中,y的最低位为1。实际上就是把x用一个奇数左移k位来表示。这时,x的二进制表示最右边有k个0,从右往左第k+1位为1。当对x取反时,最右边的k位0变成1,第k+1位变为0;再加1,最右边的k位就又变成了0,第k+1位因为进位的关系变成了1。左边的位因为没有进位,正好和x原来对应的位上的值相反。二者按位与,得到:第k+1位上为1,左边右边都为0。结果为2^k。

总结一下:x&(-x),

当x为0时结果为0;

x为奇数时,结果为1;

x为偶数时,结果为x中2的k次方。k为x从最右到左连续0的个数。

 

参考文档:https://www.cnblogs.com/xenny/p/9739600.html

发表评论