信息学集训 | 03 位运算与进制初步

导读

信息学能够有助于孩子未来工作发展，提升孩子的综合能力。

从这节课开始，我们走进编码和进制领域，了解有关于原码、反码、补码等编码知识，了解有关于十进制、二进制、八进制、十六进制的基本知识及其转换和运算。然后我们会讲解位运算的相关知识。

本节课我们学习一些有关于位运算和移位运算的知识，掌握相关的运算法则和注意事项；学习进制的一些基础知识，为后续深入学习进制打下基础。

1 位运算与移位运算

首先我们要先来看一下位运算！

我们之前讲了很多运算符，最常用的包括：

算术运算符
赋值运算符
关系运算符
逻辑运算符
三目运算符
点运算符和指针运算符
括号运算符

今天我们再讲最后两类运算符：位运算符、移位运算符。这两类运算符其实可以统称为位运算符，但是为了能更好地让大家理解，我们就分成两部分给大家讲解。

1 二进制及其单位

我们前面有讲过，一个完整的字节（Byte）有8位（bit），也就是说：

1B = 8b

其中每一个bit，就是一个二进制位，每一位上的数据只能存放0和1。这个是因为当前的计算机，都是通过电路控制的，通过电路的通和断（也就是电路连通和电路断开）来表示数据。

如果我们只有一个电路单元，这一个电路单元只有两种状态：

0：电路断开
1：电路连通

如果我们有两个电路单元，就可以产生四种状态：

00：两个电路单元都断开
01：第一个电路单元断开，第二个电路单元连通
10：第一个电路单元连通，第二个电路单元断开
11：两个电路单元都连通

我们如果有八个电路单元，就可以产生 

我们现在日常生活中最常见的大小是KB，MB，GB和TB。

KB和MB现在一般都是网络传输过程中每秒传输的最大的数据量。

GB和TB现在一般都是电脑内存，以及外部存储设备的常用容量。

它们之间的转换关系如下：

1KB = 1024B = 2^10B

1MB = 1024KB = 2^10KB = 2^20B
1GB = 1024MB = 2^10MB = 2^30B
1TB = 1024GB = 2^10GB = 2^40B

在后面我们的学习中，我们通常考虑一个字节的数据的运算，也就是八位的数据，在具体的写法中，我们四位写在一起。例如：

0000 0000
1010 0101

2 常用位运算

1、位运算介绍

位运算就是针对于二进制位数据所做的运算！

位运算包括：

按位与

按位或
按位取反（按位非）
按位异或

2、位运算法则

由于二进制位只有0和1，也就是说，位运算参数的数据是0和1。在逻辑运算中，参与逻辑运算的表达式结果只有ture和false，运算后的表达式的结果也只有ture和false。也就是说，二进制的位运算和表达式的逻辑运算的原理是一致的。只不过，二进制多了一个异或运算。

对于按位与，我们有一句口诀：全1为1，有0就0。

对于按位或，我们有一句口诀：有1为1，全0才0。

对于按位非，就是0变为1，1变为0。

上面的比较简单，我们主要来讲一下按位异或，按位异或是计算机中为了实现加法运算而设计的。

按位异或的口诀为：相同为0，不同为1。举几个例子：

0和0做异或运算，因为0和0相同，那运算结果就为0。
0和1做异或运算，因为0和1不同，那运算结果就为1。
1和0做异或运算，因为1和0不同，那运算结果就为1。
1和1做异或运算，因为1和1相同，那运算结果就为0。

3、C++中的位运算表示

C++中对于每一个运算也都有具体的符号来表示：

我们举几个例子：

1100 0011 & 0010 1011 = 0000 0011
1100 0011 | 0010 1011 = 1110 1011
1100 0011 ^ 0010 1011 = 1110 1000
~1100 0011 = 0011 1100

3 移位运算符

移位运算符也是针对于二进制位数据做操作。不过是针对数据做移位操作。

移位运算符包括：左移位运算符和右移位运算符。

1、左移位运算符

左移位运算符，就是将二进制数据的每一个位置上的数据向左移动固定个位置，后面补0。例如：

将二进制0000 0011左移一位：
移位前：0000 0011
移位后：0000 0110

因为这是二进制数据，左移位1位会将数据扩大两倍。

左移位会出现数据溢出的情况：

将二进制1100 0011左移一位：
移位前：1100 0011
移位后：1000 0110
最前面的1溢出，数据丢失

所以左移位时候要考虑数据移位后是否会超出数据存储范围。在数据不会溢出的前提下，左移位n位，就是将数据扩大了 

2、右移位运算符

右移位运算符，就是将二进制数据的每一个位置上的数据向右移动固定个位置，在最前面补零。例如：

将二进制0000 1100 右移一位：
移位前：0000 1100
移位后：0000 0110

因为这是二进制数据，右移位1位会将数据缩小两倍。

右移位会出现数据丢失的情况：

将二进制1100 0011 右移一位：
移位前：1100 0011
移位后：0110 0001
最后面的1丢失

所以右移位时候要考虑数据移位的后几位数据是否有1，如果有1，则右移位的时候会损失精度。在数据不会损失精度的前提下，右移位n位，就是将数据缩小了 

注意：在计算机实现中，移位运算的效率比对应的乘法、除法运算效率高。这是因为，乘法和乘方运算，需要先转换为加法运算，或者使用专用的乘法和乘方运算法则，效率没有移位高。

3、C++中的移位运算

在C++中用到的左移和右移的运算符如下：

<<：左移位运算符
>>：右移位运算符

我们通过代码来看具体的例子：

#include<iostream>
using namespace std;
int main(){ 
  int a;
  cin>>a; 
  a = a<<2; //左移两位，扩大2^2倍 
  cout<<"左移位："<<a<<endl;
  a = a>>1; //右移两位，缩小2^1倍
  cout<<"右移位："<<a<<endl; 
  
  return 0;
}

执行结果如下：

2 进制初步

接下来我们来看一下进制。

1 常用进制

常用进制包括：

十进制
二进制
八进制
十六进制

十进制就是我们平常所用的进制，由0-9组成。

二进制是计算机常用的，由0和1组成。

八进制数据为0-7；

十六进制数据由0-9和A-F组成，其中：

A表示10
B表示11
C表示12
D表示13
E表示14
F表示15

大家能发现，k进制数据，所包含的就是从0到k-1。

2 C++中的进制表示

在C++中，我们一般表示的数据是十进制的数据，一般在C++中，我们不表示2进制，对一个十进制整数做位运算，计算机会自动转换为二进制数据做操作。

对于八进制，如果我们想要将一个整数表示成8进制，就要在这个整数前面加一个0：

int a = 0144; //八进制
int a = 144;  //十进制

对于16进制，如果我们想要将一个整数表示成16进制，就要在这个整数前面加一个0x或0X，需要注意：

0X中：0是数字0，而不是英文字母o；X大小写均可
整数部分的字母A-F，大小写均可。

举几个例子：

#include<iostream>
using namespace std;
int main(){ 
  int a,b;
  a = 0x12A; 
  cout<<a<<endl;
  b = 0X12b;
  cout<<b<<endl; 
  return 0;
}

输出会按照十进制输出，具体如何进行进制转换，我们在后面讲解。执行结果如下：

3 走进竞赛

有了这些基础知识，我们来看几道竞赛题目！

1 二进制单位转换

下面这道题是NOIP2011年普及组的真题；考察的知识就是二进制单位的关系：

其中：

1GB = 1024MB
8GB = 8*1024MB

那么就能存：

8*1024MB / 2MB = 4*1024 ≈ 4000 张

所以选择C。

这道题比较简单，通过这道题目，老师希望大家能够掌握一个小技巧，就是先不要把数据相乘，等把所有的公式写出来之后，先尽可能的消去一些再计算。

2 二进制位存储

前面我们讲到一个字节最多能存256种不同数据，一个字节有8位，和我们这道题有异曲同工之妙。

下面这道题是NOIP2016年普及组的真题：

我们知道256 =  

4 作业

本节课的作业，就是复习上面的所有知识，并完成下面的两道题目！

1 NOIP2018普及组真题

2 NOIP2017提高组真题

​ ​ ​ ​ ​

AI与区块链技术