x & (x-1) 与 x & (-x)的含义及应用

x & (x-1) 与 x & (-x)的含义

x& (x-1)得到的结果是x的二进制去掉最低位

• 例如 10的二进制为 1010
• 9 = 10 -1 ,9的二进制为1001
• 1010 & 1001 结果为1000，这样就去掉了10二进制的最低位
  通常x& (x-1)应用在计算某个数的二进制中1的个数上，或者判断一个数是否为2的幂次，可以查看其二进制中是否只有一个1

而 m = x & (-x) ，得到的结果是x的二进制中最低位的位置

• 例如10的二进制为1010
• -10的二进制为11111111 11111111 11111111 0110
• 两者相&的结果是，2
  通常x & (-x) 应用在分组上，例如，两两成对的数组中，存在两个单数，如何将两个数找出来？
  可以先将整个数组进行异或，这样两个相同的数异或，则会为0，0与任何数异或都是那个数，所以最终的结果就是两个不相同数异或的结果。
  通过 m =x & (-x) 找到结果二进制的最低位数，在这个位置上，必然是两个不相同的数的二进制中有一个为1，有一个为0才会造成异或为1的结果。
  所以，将数组分成两组，m位为0的为一组进行异或，m位为1的进行异或，这样就能得到两个不相同的数。