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

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

2. 将二进制表示的最右侧的 1 置 0

x & (x-1)。

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

3. 用一条语句判断一个整数是否是 2 的整数次方

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

n&(n-1) == 0

4. 判断整数 m 的二进制需要改变多少位才能变为 n

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