基础算法——位运算

位运算

1. n的二进制表示中第k位是1/0？

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

思想：

1. 先把第k位移到最后一位n >> k

2. 看各位是几x&1

---

2. lowbit()操作——返回x的最后一位1是多少

• 树状数组的基本操作

• lowbit(x) —— x & (-x)作用：返回x的最后一位1（除了原x的最低为1的比特位为1，其余比特位均为0）

• 原理——x & (-x)
  在C/C++中，x的负数即为x取反加一，即**(-x) = ~x + 1**
  故x & (-x)等价于x & ~x + 1

• 模拟lowbit()作用：
  x = 1011100101000，则 (-x) = 0100011010111，则 (-x+1) = 0100011011000，则 x & (-x+1) = 0000000001000；