通过位移实现很多风骚的操作， 参考这个视频。

检查一个数是否是偶数, 本质上就是取最后一位来判断, 如果是1那么就一定是奇数, 反之则为偶数:

(x & 1) == 0

Check if power of two:

(x & x - 1) == 0

因为如果数x是以2底的真数, 那么其二进制一定只有一个位置是1, 如0b1000, 那么x-1就会变成只有该位置是0其右边所有位变为1, 即0b0111, 也就是说这种情况下x和x-1所有位置都互异. 那么它们的位与运算就是x & x - 1 = 0b0000.

x & x - 1的广义用途是求x二进制中1的个数, Counting bits set:

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Brian Kernighan’s algorithm takes O(log N) to count set bits (1s) in an integer: each iteration sets the least significance bit that isn’t zero to zero - and only it. Since each iteration converts exactly bit from 1 to 0, it’ll take as many iterations as there are non-0 bits to convert all the bits to 0(and thus v == 0 and the loop finishes). An integer n has log(n) bits, hence the worst case is O(log(n))

如果一个整数不为0, 那么其二进制就至少有一个1. 假设最右边一位是1, 那么减1就会把最后一位变为0, 前面所有位保持不变. 假如最后一位是0, 那么最靠右的1假设在m位置, 那么减去1, 该位置会变为0, 而其右边的所有0都会变为1, 其左边的所有位不变. v &= v - 1把最右的1变为0.

获取二进制的最后一个1:

def last_set_bit(x):
    y = ~(x - 1) # = - (x - 1) - 1 = -x
    return x & y

假设最右边的1位于n, -1操作会把n右边所有0变为1, 而n位变为0. 接着~操作会把n左边所有位翻转, 而n及其右边的数会变为原来的样子, 也就是n为1, 右边全为0(或者没有右边). 最后&操作就只剩下n位的1和右边的0(如果有的话).