二进制位操作

取一个 int 数的二进制表示的第 k 位：

int n = 42;
int k = 2;
// 将 n 右移 k 位，再与 1
n >> k & 1;

把一个 int 数的二进制表示中最右边的一个 1 干掉：

int n = 42; // 101010
int m = n & (n - 1); // 101000

$lowbit(x)$ 返回 x 的最后一位 1。

例如：$12 = (1100)_2$，$lowbit(12) = (100)_2 = 4$；$14 = (1110)_2$，$lowbit(14) = (10)_2 = 2$

x & (~x+1) <==> x & -x

int lowbit(x) {
  return x & (-x);
}