位运算

常用的两种位运算的操作：求 \(n\) 的第 \(k\) 位数字和 \(n\) 的最后一位

1. n的二进制表示中第k位

思路：

1. 先把第 \(k\) 位移到最后一位，即n >> k
2. 看一下最低位是几，x & 1

结合①和②，得到公式：n >> k & 1

位移运算不会改变原数据的值，即n >> k前后n的值不变

2. n的二进制表示中最后一位

lowbit()是树状数组的基本操作，lowbit(x)的作用是返回x的最后一位1。例如：如果二进制数x = 1010，则lowbit(x)返回的是10，即十进制数2；如果二进制数x = 101000，则lowbit(x)返回的是1000，即十进制数8。

实现：lowbit(x) = x & -x。其中，-x是x的补码，即x取反加一

应用：统计x的二进制表示中1的个数。每次把最后一位1减掉，当x的值为0时停止，统计循环次数。

// 求n的第k位数字: 
n >> k & 1
// 返回n的最后一位1：
lowbit(n) = n & -n