📈【深入理解计算机系统】位运算的奇技淫巧

这是自己总结的一些位运算的奇技淫巧。

1. 不用 for 循环，找到二进制最右侧的 1

(x & (-x))

-x 相当于 ~x+1。~x 将所有位取反，则最右侧连续的 0 变成 1。再加 1，会使得 ~x 最右侧的 0 进 1 变成 1，最右侧连续的 1 变成 0。这样 x 与 -x 只有最右侧的 1 相同，其他位都相反：

x:  1 1 0 0 0 ... 1 0 0 0
~x: 0 0 1 1 1 ... 0 1 1 1
-x: 0 0 1 1 1 ... 1 0 0 0

x & (x-1)。

或者根据上文，先找到最右侧的 1，然后将其取反：(x & (-x)) ^ x。

相当于这个数的二进制表示中有且仅有一位是 1。将其最右侧的 1 置 0，此时这个数变成 0。

n&(n-1) == 0

计算 m 与 n 的异或的二进制中 1 的个数。