位运算

• 位运算

• 与运算

  • 或运算

• 兼或
  * 异或

  • 非运算
  • 位移运算

• 位运算的用途

• 计算2的N次幂

  • 合并位
  • 提取位
  • 大小写转换
  • BitMask

• 设置状态
  * 清楚状态
  * 判断状态

• 开始干活

• 使用宏

  • 开始测试

• 接下来要做什么

在上一篇文章中我们实现了两个基础的宏print和println在本节中我们需要开始编写常用的函数,在编写之前我们需要掌握一些位的运算知识

位运算

我们知道计算机中采用二进制数表示,其中每个二进制数字称为位(bit)取值范围为0或1

我们主要提及一些常用的位运算,如果想看二进制的资料请参阅我们的前一篇文章

与运算

我们现在有一个命题天空是蓝色的这个命题是真命题,接着我们还有一个命题晴朗的天空中云是白色的显然这个命题也是一个真命题,接下来我们将两个命题连接在一起,天空是蓝色的并且晴朗的天空中云是白色的这两个命题使用并且连接在一起依旧是真命题,我们使用True和False表示一个命题的增加,True表示真命题,False表示假命题

现在我们切换一下思维,在计算机中,二进制可以由1和0表示,那么我们可以使用1表示True,False表示0,上述命题可以转换为以下形式我们设天空是蓝色的命题为命题A天空是蓝色的并且晴朗的天空中云是白色的为命题B,下面我们可以以下形式表示两个命题的组合

$A$ $and$ $B$ $= 1$

A和B都是真命题,因此我们可以简化为

$1$ $and$ $1$ = $1$

好了,我们的命题A发生了一些变化天空是绿色的这命题显然不是真命题,可以使用False表示,我们重新连接两个命题

天空是绿色的并且天空是蓝色的并且晴朗的天空中云是白色的我们的命题本身已经不是真命题了,因此我们可以得到

$A$ $and$ $B$ $=0$

简化后

$0$ $and$ $1$ $=0$

我们在将命题B改为天空的云是彩色的这样两个命题都是假命题了根据以上的逻辑我们可以得到

$A$ $and$ $B$ $=0$

简化后

$0$ $and$ $0$ = 0

虽然A为真命题B为假命题我们没有谈论,但是我们也能猜到结果

这样我们得到了一张表

1
1
1
1
0
0
0
1
0
0
0
0

现在我们知道了单个位与运算的结果,那么多位怎么运算呢

现在我们有这样的二进制数 110(称为A)和101(称为B),在$and$运算时是按位运算,意思是,第一位跟第一位进行$and$运算,第二位跟第二位进行$and$运算,依次类推

1
2
3
4
5
6
1      1 1 1

2and   1 0 1

3--------------

4      1 0 1

5

6

A的第一位是1B的第一位也是1,因此我们可以的得到$1$ $and$ $1$ $=1$

A的第二位是1,B的第二位是0,因此我们可以得到$1$ $and$ $0 = 0$

A的第三位是1B的第三位是1,因此我们可以的得到 $1$ $and$ $1$ $=1$

因此最终的结果是101

或运算

或在平时的自然语言中有两层含义,一个是兼或另一个是异或,首先我们看一下兼或

兼或

在学校中我们选课时是按照自己的专业来选的,比如,选修过微积分的同学或计算机科学的同学选可以选修线性代数课程这个命题,这里是指选修过微积分的同学和计算机科学的学生,或者是两者只修了一门的学生,这样命题使用或的含义是兼或

我们使用A表示命题选修过微积分的同学使用B表示命题计算机科学的同学我们就可以使用以下形式表示

$A$ $or$ $B$ $ = 1$

假设一个A的值为1B的值也为1那么结果也是1,如果A和B其中有一个的值为0那么它们的结果依旧是0,只有两个都是0时它们的结果才为0,我们可以得出一张表

1
1
1
1
0
1
0
1
1
0
0
0

因此我们的多位$OR$运算方式可以参考$AND$运算

1
2
3
4
5
6
1     1 1 1

2or   1 0 1

3--------------

4    1 1 1

5

6

详细分析就不再啰嗦了

异或

或的另一意思是异或,例如李雷生于1991年或1995年,这里的或是异或是具有排他性的,意味着在1991和1995中只能2选一

跟往常一样我们设A为命题李雷生于1991年设B为命题李雷生于1995年我们使用$\oplus$表示异或

我们假设A和B都是真命题那么结论会变成这样李雷生于1991,1995年显然这个一个很荒唐的结论,因此A和B都为1是异或的结果为0

$A \oplus B = 0$ 其中A=B=1

如果A和B都是假命题呢?那我们就无法判断出李雷出生的年份,因此

$A\oplus B = 0$ 其中A=B=0

我们可以得出以下关系

1
1
0
1
0
1
0
1
0
0
0
0

非运算

非运算在自然语言中就是否定语句,例如,太阳会发光这个命题的否定语句是太阳不会发光,如果使用A表示命题太阳会发光那么我们可以用以下形式表示

$not$ $A$

如果你看见$not$ $not$ $A$就是在自然语言中双重否定,双重否定就是肯定,因此如果A=1 $not$ $not$ $A$ 就是1

位移运算

位移就是对二进制数的每一位向左或向右移动指定的个数例如,1101向左移动2位结果是0100移动后的位的位置不变,没有的值用0代替

|表示分割线

1
2
3
4
5
1  |1101

2 1|1010  向左移动1位后

311|0100  向左移动2位后

4

5

现在我们尝试将1111向右移动3位

1
2
3
4
5
6
11111|

20111|1         向右移动1位后

30011|11        向右移动2位后

40001|111   向右移动3位后

5

6

位运算的用途

以下操作数均为无符号

计算2的N次幂

现在这样的二进制数0001现在左移1位结果为0010现在转为十进制为2,其他结果如下

0000 0001
1
0
0000 0010
2
1
0000 0100
4
2
0000 1000
8
3
0001 0000
16
4
0010 0000
32
5
0100 0000
64
6
1000 0000
128
7

例如我们可以计算存储容量的大小,我们知道1MB=1024KB,1024用二进制表示为0100 0000 0000,你会发现是0000 0000 0001向左移动了10位,因此我们可以得以下内容

1KB << 10 = 1MB

虽然有些不太严谨,知道他的含义就好,那么计算1GB等于多少KB呢,1KB << 10 =1MB, 1MB << 10 = 1GB那么1KB<<20 = 1GB

我们可以使用计算器来计算最终结果是0001 0000 0000 0000 0000转为十进制为1048576我们算出来了,1GB=1048567KB

合并位

现在我们有这样的一个需求,我们需要将0010和1111合并成0010 1111,那么该怎么计算呢

首先0010是在高位,因此我们需要通过位移运算来将0010移动到高4位,

0010 << 4 = 0010 0000

紧接着我们要把1111放在第四位

我们可以使用或运算来做到这一点(注意不能使用and运算,如果遇到一个1另一个是0这样会变成0的)

1
2
3
4
5
6
1    0010 0000

2or       1111

3--------------

4    0010 1111

5

6

这样我们就做到了合并操作(写操作系统时经常会用到)

提取位

我们需要将0011 1011(8位)中的第2-5位(不包括第5位)的值(1101)提取出来,那么怎么提取呢

1
2
3
4
5
1 0 0 1 1  1 0 1 1

2 ----------------

3 7 6 5 4  3 2 1 0

4

5

我们可以先左移3位把多余的高位清除掉,结果是这样的

1
2
3
4
5
1 1 1 0 1  1 0 0 0

2 ----------------

3 7 6 5 4  3 2 1 0

4

5

然后在右移3位回到原来的位置

1
2
3
4
5
1 0 0 0 1  1 0 1 1

2 ----------------

3 7 6 5 4  3 2 1 0

4

5

紧接着我们右移1位

1
2
3
4
5
1 0 0 0 0  1 1 0 1 

2 ----------------

3 7 6 5 4  3 2 1 0

4

5

这样就获取到了2-5位的值

如果我们要取的bit位长度为N,提取的范围为$[n,m)$那么消除最高位的位移长度为$L=N-m$ 例如我们上文中的2-5,我们消除高位的位移长度为8-5=3位因此我们需要左移3位在右移3位,然后我们需要消除最低位即$O>>n$O表示被提取的数据最后整理一下

$$L=N-m$$

$$Result = O<<L>>L>>n$$

大小写转换

我们现在要实现这样的一个功能,将大字母转为小写字母

在转换之前我们需要了解一下ASCII表

例如我们要将A转为a,A的十进制为65,二进制为0100 0001,a的十进制为97,二进制为0101 0001,你会发现小写字母的第5位被值1了,因此我们只需要使用一个数将A的第5位置1即可,

1
2
3
4
5
6
1    0100 0001

2or  ???? ????

3----------------

4       0101 0001

5

6

我们只需要根据位运算的特性反推一下,将某一位置1可以使用or运算,我们可以使用0001 0000就可以达到效果,

1
2
3
4
5
6
1    0100 0001

2or  0001 0000

3----------------

4   0101 0001

5

6

我们也可以OR 0101 0001来实现,你会发现其实or的就是小写字母本身

1
2
3
4
5
6
1    0100 0001

2or  0101 0001

3----------------

4   0101 0001

5

6

大写Z转为小写z也是可以的

1
2
3
4
5
6
1    0101 1010

2or  0111 1010

3----------------

4   0111 1010

5

6

BitMask

BitMask翻译过来就是位掩码,可以使用一个数值,数值的每一位表示一种,你可以使用很少的资源来表达很丰富的内容

例如有一个复读机,复读机通常有4个按键,快进,后退,暂停,播放,按键有2种状态按下和弹起我们使用1表示按键被按下,使用0表示按键谈起这样我们可以使用如下形式表示复读机状态

1
2
3
4
5
6
7
8
9
10
11
1第一位表示前进

2第二位表示播放

3第三位表示暂停

4第四位表示后退

5例如:

6   0001 表示前进

7   1000 表示后退

8   0100 表示播放

9   0010 表示暂停

10

11

设置状态

我们需要将那一位置1就在被或运算的那一位置1其他位置0被运算的称为mask

例如 需要将复读机状态转为后退状态我们可以把第4位置1

1
2
3
4
5
6
1   0000

2or 1000

3--------

4   1000

5

6

或者将复读机状态转为播放状态

1
2
3
4
5
6
1    0000

2or  0010

3-----------

4    0010

5

6

清楚状态

要将那一位置0需要在被与运算的mask的位置0其他位置1

现在我们的复读机快进到我们需要的地方了我们要把快进状态给清除掉

1
2
3
4
5
6
1    0001

2and 1110

3----------

4   0000

5

6

判断状态

要确定那一位状态需要与mask进行与运算

我们暂时不知道当前的状态使用x表示未知,我们要判断复读机是否处于播放状态

1
2
3
4
5
6
1    xxxx

2and 0010

3----------

4    00x0

5

6

如果结果大于0表示复读机处于播放状态,如果结果小于0表示不再播放状态

开始干活

好了我们的位运算的知识就学习到这里,接下来我们要对Rust的整形编写位操作

我们紧接着使用上次创建的system项目,项目结构是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
1system

2|

3|__ src

4|      |

5|      |__ lib.rs

6|      |

7|      |__ mutex.rs

8|

9|__ Cargo.toml

10|

11|__ .gitignore

12

13

我们创建一个新的包bits现在项目结构如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1system

2|

3|__ src

4|      |

5|      |__ lib.rs

6|      |

7|      |__ mutex.rs

8|      |

9|      |__ bits.rs

10|

11|__ Cargo.toml

12|

13|__ .gitignore

14

15

lib.rs内容如下

1
2
3
4
5
6
7
8
9
10
11
1pub mod bits;

2

3#[cfg(test)]

4mod tests {

5    #[test]

6    fn it_works() {

7        assert_eq!(2 + 2, 4);

8    }

9}

10

11

现在我们在bits.rs文件中实现我们的位操作

我们可以使用函数形式实现,类似于

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1use core::ops::Range;

2

3fn get_bits_u8(data:u8,range:Range<i32>) -> u8{

4  ....

5}

6

7fn get_bits_u16(data:u8,range:Range<i32>) -> u16{

8  ....

9}

10....

11// 使用时

12let result = get_bits_u16(5,2..3);

13

14

这样写也没什么问题,但是有大量的重复代码,所以我们利用范型改进一下

1
2
3
4
5
6
7
8
1fn get_bits<T>(data: T, r: Range<i32>) -> T {

2   ....

3}

4

5//使用时

6let result = git_byts::<i32>(5,2..3);

7

8

其实更好的做法是使用trait来实现我们为常用的类型添加位运算功能

1
2
3
4
5
6
7
8
9
10
11
1use core::ops::Range;

2

3trait BitOpt {

4    fn length() -> usize;

5    fn get_bit(&self, size: usize) -> bool;

6    fn get_bits(&self, range: Range<usize>) -> Self;

7    fn set_bit(&mut self, bit: usize, value: bool) -> &mut Self;

8    fn set_bits(&mut self, range: Range<usize>, value: Self) -> &mut Self;

9}

10

11

length() 方法是一个静态方法,用于返回bit的长度

get_bit() 方法用于获取size位的值,我们可以使用bool类型表示1和0

get_bits() 方法用于获取指定范围的位,使用Range我们就可以使用..表示一个范围,例如2..5表示2(含2)到5(不包括5)的范围

set_bit() 方法用于设置指定的位,因为我们要对原值进行修改因此使用写指针 &mut self

set_bits 方法用于设置指定范围的位

我们开始为u8类型实现BitOpt trait

1
2
3
4
5
6
7
1impl BitOpt for u8 {

2    fn length() -> usize {

3        ::core::mem::size_of::<Self>() as usize * 8

4    }

5}

6

7

首先是length,我们通过core包中的sizeof来获取对应的字节大小,因为最终提取的单位是字节,所以我们要乘以8,以bit为单位(1byte=8bit)刚好比特的大小跟个数一致,因此我们就可以获取到了当前的位长度

接下来我们要实现set_bit和get_bit方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
1impl BitOpt for u8 {

2    fn length() -> usize {

3        ::core::mem::size_of::<Self>() as usize * 8

4    }

5    fn get_bit(&self, size: usize) -> bool {

6      assert!(size < Self::length());

7      (*self & (1 << size)) != 0

8    }

9    fn set_bit(&mut self, bit: usize, value: bool) -> &mut Self {

10      assert!(bit < Self::length());

11      let mask = 1 << bit;

12      // 如果要把某一位置1使用或运算

13      if value {

14        *self |= mask;

15      } else { // 要把某一位置0进行和运算(需要取反)

16        *self &= !(mask);

17      }

18      self

19    }

20}

21

22

git_bit和set_bit中我们都加了两个assert宏进行断言防止给定的位超过最大位长度

然后我们利用BitMask来获取和设置位(如果还是有疑问可以看一下前面的章节)

接下来我们实现一下get_bits,通过之前的学习我们很容易写出这样的代码(如果看不懂可以看一下提取位章节)

1
2
3
4
5
6
7
8
9
1fn get_bits(&self, range: Range<usize>) -> Self {

2  let shift_bits = Self::length() - range.end;

3

4  let bits = *self << shift_bits >> high_bits;

5

6  bits >> range.start

7}

8

9

在这里我们没有对range的范围做判断,range的范围必须要小于当前位长度而且必须大于0,提取的范围必须是从低到高

因此我们在添加一下内容

1
2
3
4
5
6
7
8
9
10
11
12
1fn get_bits(&self, range: Range<usize>) -> Self {

2  assert!(range.start < Self::length());

3  assert!(range.end <= Self::length());

4  assert!(range.end > range.start);

5

6  let shift_bits = Self::length() - range.end;

7  let bits = *self << high_bits >> high_bits;

8

9  bits >> range.start

10}

11

12

最后我们可以实现set_bits了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1fn set_bits(&mut self, range: Range<usize>, value: Self) -> &mut Self {

2  let length = Self::length();

3    assert!(range.start < length);

4    assert!(range.end <= length);

5    assert!(range.start < range.end);

6    assert!(value << (length - (range.end - range.start)) >>

7            (length - (range.end - range.start)) == value,

8            "value does not fit into bit range");

9

10    let mask: Self = !(!0 << (length - range.end) >>

11                        (length - range.end) >>

12                        range.start << range.start);

13

14    *self = (*self & mask) | (value << range.start);

15

16    self

17}

18

19

根get_bits一样我们需要对range的范围做判断,然后计算移动的长度shift_bits,在做在设置位的时候我们计算出mask

我们利用!0来获取一个全1的二进制数然后通过位移去掉高位和低位,然后将整个值全取反,最后利用mask清除所有的值,然后利用or与之合并

例如我们的对8位数的2…5范围设置位,mask的计算为

1
2
3
4
5
6
7
8
9
10
1shift_bits = 8 - 5 = 3

2!0 = 1111 1111

3

4!0 << shift_bits >> shift_bits = 0001 1111

5

6!0 << shift_bits >> shift_bits >> range.start << range.start = 0001 1100

7

8!(!0 << shift_bits >> shift_bits >> range.start << range.start) = 1110 0011

9

10

这样我们就计算出了mask的值,然后利用mask清除状态,合并即可

使用宏

对u8类型实现了BitOpt操作了以后我们需要对 u16 u32 u64 usize i8 i16 i32 i64 isize类型实现同样操作,如果我们复制粘贴也要好久,不如我们使用Rust提供的宏来解决这个问题

1
2
3
4
5
6
7
1macro_rules! bit_opt_impl {

2    ( $($t:ty)* ) => ($(

3    

4    )*)

5}

6

7

然后我们将我们实现的内容拷贝进去,别忘了把impl BitOpt for u8改成impl BitOpt for $t

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
1macro_rules! bit_opt_impl {

2    ( $($t:ty)* ) => ($(

3        impl BitOpt for $t {

4            fn length() -> usize {

5                ::core::mem::size_of::<Self>() as usize * 8

6            }

7

8            fn get_bit(&self, size: usize) -> bool {

9                assert!(size < Self::length());

10                (*self & (1 << size)) != 0

11            }

12

13            fn get_bits(&self, range: Range<usize>) -> Self {

14                assert!(range.start < Self::length());

15                assert!(range.end <= Self::length());

16                assert!(range.end > range.start);

17

18                let shift_bits = Self::length() - range.end;

19                let bits = *self << shift_bits >> shift_bits;

20

21                bits >> range.start

22            }

23

24            fn set_bit(&mut self, bit: usize, value: bool) -> &mut Self {

25                assert!(bit < Self::length());

26                let mask = 1 << bit;

27                if value {

28                    *self |= mask;

29                } else {

30                    *self &= !(mask);

31                }

32                self

33            }

34

35            fn set_bits(&mut self, range: Range<usize>, value: Self) -> &mut Self {

36                assert!(range.start < Self::length());

37                assert!(range.end <= Self::length());

38                assert!(range.end > range.start);

39

40                let shift_bits = Self::length() - range.end;

41                let mask = !0 << shift_bits >> shift_bits >> range.start << range.start;

42

43                *self = (*self & mask) | (value << range.start);

44

45                self

46            }

47        }

48    )*)

49}

50

51

最后我们可以使用bit_opt_impl宏来实现整数类型

1
2
3
1bit_opt_impl! { u8 u16 u32 u64 usize i8 i16 i32 i64 isize }

2

3

这样我们就完成了bit的操作

开始测试

我们创建一个新的文件tests.rs并添加如下内容

1
2
3
1use crate::bits::BitOpt; // 注意我们需要导入实现的BitOpt才能使用trait的功能

2

3

然后我们的lib.rs文件内容修改为

1
2
3
4
5
6
7
1#![no_std]

2pub mod bits;

3

4#[cfg(test)]

5mod tests;

6

7

我们就可以编写测试用例了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
1use crate::bits::BitOpt;

2

3#[test]

4fn length_test() {

5    assert_eq!(u8::length(), 8);

6    assert_eq!(u16::length(), 16);

7    assert_eq!(u32::length(), 32);

8    assert_eq!(u64::length(), 64);

9

10    assert_eq!(i8::length(), 8);

11    assert_eq!(i16::length(), 16);

12    assert_eq!(i32::length(), 32);

13    assert_eq!(i64::length(), 64);

14}

15

16#[test]

17fn test_set_bit_u8() {

18    let mut field = 0b11110010u8;

19    let mut func = |i| {

20        field.set_bit(i, true);

21        assert_eq!(field.get_bit(i), true);

22        field.set_bit(i, false);

23        assert_eq!(field.get_bit(i), false);

24        field.set_bit(i, true);

25        assert_eq!(field.get_bit(i), true);

26    };

27    for i in 0..8 {

28        func(i);

29    }

30}

31

32#[test]

33fn test_set_bit_u16() {

34    let mut field = 0b1111001010010110u16;

35    let mut func = |i| {

36        field.set_bit(i, true);

37        assert_eq!(field.get_bit(i), true);

38        field.set_bit(i, false);

39        assert_eq!(field.get_bit(i), false);

40        field.set_bit(i, true);

41        assert_eq!(field.get_bit(i), true);

42    };

43    for i in 0..16 {

44        func(i);

45    }

46}

47

48

49#[test]

50fn test_set_bit_u32() {

51    let mut field = 0b1111111111010110u32;

52    let mut func = |i| {

53        field.set_bit(i, true);

54        assert_eq!(field.get_bit(i), true);

55        field.set_bit(i, false);

56        assert_eq!(field.get_bit(i), false);

57        field.set_bit(i, true);

58        assert_eq!(field.get_bit(i), true);

59    };

60    for i in 0..32 {

61        func(i);

62    }

63}

64

65#[test]

66fn test_set_bit_u64() {

67    let mut field = 0b1111111111010110u64 << 32;

68    let mut func = |i| {

69        field.set_bit(i, true);

70        assert_eq!(field.get_bit(i), true);

71        field.set_bit(i, false);

72        assert_eq!(field.get_bit(i), false);

73        field.set_bit(i, true);

74        assert_eq!(field.get_bit(i), true);

75    };

76    for i in 0..64 {

77        func(i);

78    }

79}

80...

81

82

由于篇幅限制我们就不把测试用例全部列举出来了

接下来要做什么

在下一篇文章中我们需要实现2个比较重要的结构体VirtualAddr和PhysicalAddr,并些其实现一些地址操作,有了本章实现的内容,编写VirtualAddr和PhysicalAddr不会很难(大家加油!)