最近看算法题，涉及到两个很经典的位运算：
- x&(-x)：保留二进制下最后出现的1的位置，其余位置置0（即一个数中最大的2的n次幂的因数
- x&(x-1)：消除二进制下最后出现1的位置，其余保持不变
具体分析如下：
我们可以从看待字符串的角度去思考这件事。
二进制下的数字都可以写成（A）1（B）的形式，其中A表示一串01字符串，1表示从右向左的出现的第一个数字1，B表示空（奇数）或者是连续的0（偶数），即：
- 偶数：(A)1(00…0)
- 奇数：(A)1
对于x&(-x)
-x的运算是，所有位置取反+1，即变形如下（?表示所有位置取反）：
- 偶数：(?)0(11…1) + 1 = (?)1(00…0)
- 奇数：(?)0 + 1 = (?)1
所以，x&(-x)即：
- 偶数：(?)1(00…0) & (A)1(00…0) = (00…0)1(00…0)
- 奇数：(?)1 & (A)1 = (00…0)1
对于x&(x-1)
x-1变形如下：
- 偶数：(A)1(00…0) - 1 = (A)0(11…1)
- 奇数：(A)1-1 = (A)0
所以，x&(x-1)即：
- 偶数：(A)0(11…1) & (A)1(00…0) = (A)0(00…0)
- 奇数：(A)0 & (A)1 = (A)0