【与二进制中最低位】相关的位运算小技巧
说明：
- 此文章中的n都为正数
- 假设n的二进制位是 (a10…0)2，其中a表示若干个高位，1 表示最低位的 1，0⋯0 表示后面的若干个 0。
通过位运算技巧可以更快速的求得：
- n的二进制中最低位的1
- n的二进制中1的个数
- n是否是2的幂
总结
| 位运算 | 高位 | 最低位的1以及低位 |
|---|---|---|
| n | a | 10…0 |
| n - 1 | a | 01…1 |
| n & (n-1) | a | 00…0 |
| -n | ~a | 10…0 |
| n & (-n) | 0 | 10…0 |
n&(n-1)
通过n&(n-1)可以将n的二进制中最低位的1变为0，即将最低位的1移除。
n的二进制表示为： (a10…0)2
n-1的二进制表示为：*(a01…1)2*
n&n-1得到的结果为: *(a00…0)2*，即高位 a 不变，在a之后的所有位都会变为 0，这样最低位的1就被移除了。
n&-n
通过n&(-n)可以直接获取 n 的二进制表示的最低位的 1
n的二进制表示为： (a10…0)2
-n是n的相反数，是一个负数，二进制表示为：*(～a 10…0)2*
由于负数是按照补码规则在计算机中存储的，-n 的二进制表示为 n 的二进制表示的每一位取反再加上 1
所以-n的二进制表示为 (～a 01…1)2 + (1)2 = (～a 10…0)2
其中，~a 是 a 的按位取反*(a & ~a)2 = 0*
则n&-n得到的结果为: *(0…1…0)2*，高位全部变为 0，最低位的 1 以及之后的所有 0 不变，这样就获取了 n 的二进制中表示的最低位的 1。
参考：https://leetcode-cn.com/problems/power-of-two/solution/2de-mi-by-leetcode-solution-rny3/
