C++中 x & -x 表示含义

来源：

当我在刷题，学习（借鉴）大佬的代码的时候，经常看到 “(x & -x) == x”

说明：

-x 的值，其实就是在x的值的基础上进行按位取反(~x)之后在增加1所得， 也就是说

x & -x == x & (~x + 1)。

1.x 为偶数我们都知道， 当一个奇数 + 1时， 表示的二进制数则会发生进位， 这样的话， 会产生一个连锁反应，也就是最低位的那些连续的1都会被清0,

0000 0000 0111 1111 + 1 = 0000 0000 1000 0000

如果一个偶数, 如 0000 0100 1110， 取反后的结果就变成了 1111 1011 0001，而当这个值 + 1之后由于发生了进位， 即
1111 1011 0001 + 1 = 1111 1011 0010

这个结果再与最初的值相与后， 只会有一位保留为1

0000 0100 1110 & 1111 1011 0010 = 0000 0000 0010

很显然， 这个值的与原值的末位0的个数是一致的

也就是说， 如果一个偶数， 在执行 x & -x的操作的时候， 最后结果肯定有如下两个特征

① 这个结果只有一位值是1， 其他位均是0

② 这个值的末位0的个数与原值保持一致

仔细一想， 这个原值肯定是能被结果值整除的， 而这个结果值又是2^ n， 那我们就可以描述成，

“当一个偶数与它的负值相与时， 结果是能整除这个偶数的最大的2的幂,

即： m = n & -n , 则 n % m = 0, 且 m = 2 ^ k”

所以当m=n时，可以用 n&-n == n 来判断n是不是2的整数次幂

2.x为奇数

当一个奇数 + 1时， 表示的二进制数则会发生进位， 这样的话， 会产生一个连锁反应，为奇数取反后的值一定是偶数，而 x与其取反的数相与结果肯定是0 ，但是由于相与的数是取反后再+ 1的值(肯定是个奇数)， 也就是说， 只有最后一位有翻转，所以只有最后一位都是1， 相与结果仍旧是1， 而其他位所有的只都是相反值， 相与必为0 , 所以结论是：

“如果是x是奇数， 那x & -x 的结果一定是1”