位运算

求某个整数 $n$ 的二进制表示中，第 $k$ 位数是 0 还是 1，注意：个位是第 0 位

算法：

• 先把第 $k$ 位移到最后一位：n >> k
• 看个位是几：x & 1，按位与操作

综上就是：(n >> k) & 1。

这样可以求出某个数的二进制表示，例如：

{
    int n = 10;
    for (int k = 3; k >= 0; k --) {
        cout << (n >> k) & 1;
    }
    return 0;
}

另一个操作 lowbit，它是树状数组的一个基本操作：返回 x 的最后一位 1 以及后面的 0，例如 lowbit(101000) = 1000。

直接给出结论：lowbit(x) = x & -x;

考虑 -x 的补码表示，就是 x 的取反加一，因此 101000 的取反加一就是 011000，注意到最后一位 1 以及后面的 0 经过取反加一没有变化，而前面的则互相相反，因此该算法是正确的。

二进制中的 1 的个数

AC801. 二进制中的 1 的个数