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的个数。