- 取余 和 与
- 1. 与（&）的真面目
- 2. << 左移
- 3. >> 右移
- 4. % 取余
| A | B | A&B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
可以看出，在二进制的位运算中：
- 不管是 0 还是 1 ，& 1 的结果都是 本身
- 不管是 0 还是 1 ，& 0 的结果都是 0
1 & x = x x ∈ ( 0 , 1 ) ⇒ p e r s i s t 0 & x = 0 x ∈ ( 0 , 1 ) ⇒ r e s e t begin{aligned} &1 & x=xquad xin(0,1)Rightarrow persist\ &0 & x=0quad xin(0,1)Rightarrow reset end{aligned} 1 & x=xx∈(0,1)⇒persist0 & x=0x∈(0,1)⇒reset
2. << 左移假设，有 4 4 4 位二进制数 x 4 x 3 x 2 x 1 x_4x_3x_2x_1 x4x3x2x1 ，乘以 2 3 2^3 23
x
4
x
3
x
2
x
1
×
2
3
=
(
x
4
⋅
2
3
+
x
3
⋅
2
2
+
x
2
⋅
2
1
+
x
1
⋅
2
0
)
×
2
3
=
x
4
⋅
2
6
+
x
3
⋅
2
5
+
x
2
⋅
2
4
+
x
1
⋅
2
3
=
x
4
x
3
x
2
x
1
000
begin{aligned} &x_4x_3x_2x_1times2^3\ =& (x_4cdot2^3 + x_3cdot2^2 + x_2cdot2^1 + x_1cdot2^0)times2^3\ =& x_4cdot2^6 + x_3cdot2^5 + x_2cdot2^4 + x_1cdot2^3\ =& x_4x_3x_2x_1000 end{aligned}
===x4x3x2x1×23 (x4⋅23+x3⋅22+x2⋅21+x1⋅20)×23 x4⋅26+x3⋅25+x2⋅24+x1⋅23 x4x3x2x1000
可以看出，任何一个二进制数，乘以
2
N
2^N
2N ，就是将原来的数字，左移
N
N
N 位，后面补
0
0
0 。
假设，有 4 4 4 位二进制数 x 4 x 3 x 2 x 1 x_4x_3x_2x_1 x4x3x2x1 ，除以 2 2 2^2 22
x 4 x 3 x 2 x 1 ÷ 2 2 = ( x 4 ⋅ 2 3 + x 3 ⋅ 2 2 + x 2 ⋅ 2 1 + x 1 ⋅ 2 0 ) ÷ 2 2 = x 4 ⋅ 2 1 + x 3 ⋅ 2 0 + x 2 ⋅ 2 − 1 + x 1 ⋅ 2 − 2 = x 4 x 3 ⋯ x 2 x 1 begin{aligned} &x_4x_3x_2x_1div2^2\ =& (x_4cdot2^3 + x_3cdot2^2 + x_2cdot2^1 + x_1cdot2^0)div2^2\ =& x_4cdot2^1+x_3cdot2^0+x_2cdot2^{-1}+x_1cdot2^{-2}\ =& x_4x_3 cdots x_2x_1 end{aligned} ===x4x3x2x1÷22 (x4⋅23+x3⋅22+x2⋅21+x1⋅20)÷22 x4⋅21+x3⋅20+x2⋅2−1+x1⋅2−2 x4x3 ⋯ x2x1
可以看出，任何一个二进制数，除以 2 N 2^N 2N ，就是将原来的数字，右移 N N N 位。移出去的，是 余数
x 4 x 3 x 2 x 1 % 2 2 = x 2 x 1 x_4x_3x_2x_1 % 2^2 = x_2x_1 x4x3x2x1 % 22=x2x1
4. % 取余既然，当除数是 2 N 2^N 2N ，余数是挪出去的那 N N N 位，对于取余运算来说，提取出最后的 N N N 位就可以了。怎么做呢？清零 & 保留
假设，有 4 4 4 位二进制数 x 4 x 3 x 2 x 1 x_4x_3x_2x_1 x4x3x2x1 ，取余 2 2 2^2 22
x 4 x 3 x 2 x 1 % 2 2 = x 4 x 3 x 2 x 1 & ( 2 2 − 1 ) = x 4 x 3 x 2 x 1 & 0011 = x 2 x 1 begin{aligned} &x_4x_3x_2x_1 % 2^2\ =& x_4x_3x_2x_1 & (2^2-1)\ =& x_4x_3x_2x_1 & 0011\ =& x_2x_1 end{aligned} ===x4x3x2x1 % 22 x4x3x2x1 & (22−1) x4x3x2x1 & 0011 x2x1
可以看出，任何一个二进制数，取余 2 N 2^N 2N ，就可以 & ( 2 N − 1 ) (2^N-1) (2N−1) 。得到需要右移的 N N N 位。
