算法 位运算

算法 - 位运算

10进制数字和2进制数字

数字只有两种:

奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。

举例：

0 = 0 1 = 1 2 = 10 3 = 11

偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。

举例：

2 = 10 4 = 100 8 = 1000 3 = 11 6 = 110 12 = 1100

如果我们想求一个数字里面1的个数那么, 有这样的状态转移方程

P(x)=P(x / 2)+(x mod 2)

或者

P(x) = P(x-1) + 1 如果x是奇数

P(x) = P(x / 2) 如果x是偶数

高级位操作

get 最后一位(op=3)

y = x & (-x); // 1010 -> 0010

pop 最后一位(op=2)

x = x & (x - 1); // 1010 -> 1000