位运算

这里主要记录一下学习到的位运算算法

求第k位数字

求n的第k位数字: n >> k & 1

返回n的最后一位1

lowbit(n) = n & -n，，如101000得1000

这个可能咋看一下不好理解，但是可以推理出来:

1. 假设x = 1010...10000
2. -x = ~x+1
3. ~x = 0101...01111
4. ~x + 1 = 0101...10000
5. x & (~x+1) = (1010...10000) & (0101...10000) = 0000...10000
   可以通过上面步骤发现lowbit(n)算法最终取到最后一位1和后面的二进制

题目

位1的个数