位运算

一、n的二进制表示中第k位是几
第一步：将n右移k位，即 n >> k，把第k位移到最低位。
第二步：通过与运算获取最低位的值，即 n & 1，判断第k位是0还是1。

二、lowbit(x)：返回x的最低位1及其后所有0所组成的数值

例如：
x = 1010（二进制） lowbit(x) = 10
x = 101000（二进制） lowbit(x) = 1000

原理：
lowbit(x) 的计算公式是 x & -x。

解释：

• 首先，-x 等于 ~x + 1，这是二进制表示中取反加一的结果（即补码）。
• 当我们将x与-x进行按位与运算时，结果会保留x中最低位的1，并将其他位清零。

举例说明：
x = 1010010101000
~x = 0101101010111
-x = ~x + 1 = 0101101011000（补码）
x & -x = 0000000001000

这表明lowbit(x) = 1000。

应用：
可以用lowbit(x)来计算x（二进制）中有多少个1。