07 计算机数论

Posted on Wed, 25 Dec 2024 16:46:32 +0800 by LiangMingJian

1.进制 #

1.1 进制的表示 #

1.1.1 十进制 #

• 基数：0、1、2、3、4、5、6、7、8、9
• 逢十进一
• 如：10D = 9 + 1。

1.1.2 二进制 #

• 基数：0、1
• 逢二进一
• 如：10B = 1 + 1。

1.1.3 十六进制 #

• 基数：0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F
• 逢十六进一
• 如：10H = F + 1。0x10 = F + 1。

1.1.4 八进制 #

• 基数：0、1、2、3、4、5、6、7
• 逢八进一
• 如：10Q = 7 + 1。

1.2 进制的转换 #

1.2.1 按权展开法（R 进制转十进制） #

• 十六进制数 0x11，按权展开 0x11 = $ 1 * 16 ^ 1 + 1 * 16 ^ 0 $ = 17。

1.2.2 短除法（十进制转 R 进制） #

• 十进制数 6，短除法 $ 6/2 = 3…0, 3/2 = 1…1, 1/2 = 0…1 $，商为 0 时结束，将余数从后往前读，即 110 为对应二进制数。

1.2.3 十六进制转二进制（特别的） #

• 十六进制数的每一位相对于 4 位二进制数，即 0x21 = 0010 0001B，2H = 0010B，1H = 0001B。反之亦然，每 4 位二进制数等于 1 位十六进制数。

1.2.4 八进制转二进制（特别的） #

• 八进制数的每一位相对于 3 位二进制数，即 0x21 = 010 001B，2Q = 010B，1Q = 001B。反之亦然，每 3 位二进制数等于 1 位八进制数。

2.计算机中的数 #

2.1 地址 #

• 将计算机的内存按照约定的大小分成很多个区域，然后给每一个区域一个编号，编号的内容就是计算机中的地址。

2.2 位（bit） #

• 在计算机中，一个位就代表一个 0 或 1，位简写为小写字母 b。
• 如：1bit，2bit。

2.3 字节（byte） #

• 在计算机中，每 8 个位组成一个字节（byte），字节简写为大写字母 B。
• 如：1B = 8bit，2B。
• 注意：一个英文字母占用一个字节，一个汉字占用两个字节。

2.4 字与字长 #

• 在计算机中，CPU 一次能处理的二进制就是一个字，一次能处理的二进制的位数就是字长。
• 如：64 位的CPU，一次能处理 64 位的二进制，即 1字 = 64 bit，字长 64。

2.5 转换 #

• 1 B = 8 bit
• 1 KB = $2^{10}$ B = 1024 B
• 1 MB = $2^{10}$ KB = $2^{20}$ B
• 1 GB = $2^{10}$ MB = $2^{20}$ KB = $2^{30}$ B
• 特别的：100 0000 0000 B = 1 KB，二进制每 10 个 0 可化简为 $2^{10}$。

2.6 编码空间 #

• n 位二进制能表示的编码个数为 $2^{10}$ 。
• 在计算一个区域内的编码个数时，需要用最大编号减去最小编号，然后再加一。
• 比如：内存区域 A5000H 到 DCFFFH，区域的存储容量 = DCFFFH - A5000H + 1 = 48000H = 224 KB

3.码制 #

3.1 机器数 #

• 各种数据在计算机中表示的形式称为机器数，其特点是采用二进制计数制，用 0、1 表示。
• 在机器数中，最高位被使用来表示一个数的正负，0 表示正数，1 表示负数。
• 在机器数中，小数点隐含表示，不占位置，如果是整数，小数点位在最低有效数位之后，如果是小数，小数点在符号位之后，最高有效数位之前。
• 在机器数使用过程中，计算机系统往往会约定一个固定长度的二进制位来表示一个数，可以是 8 位，也可以是 32 位。
• 比如：使用 8 个二进制来表示一个固定的数，最高位表示正负，剩余 7 位表示数值，-1D = 1 000 0001。

3.2 码制 #

3.2.1 原码 #

• 最高位为符号位，0 表示正数，1 表示负数。
• 8 位原码表示范围是 -127 到 127。
• n 位原码表示范围是 $-2^{n-1}-1$ 到 $2^{n-1}-1$。
• 缺点：在加减计算时，符号位也会进行运算，结果会出现错误。

3.2.2 反码 #

• 正数的反码是自身，负数的反码符号位不变，数值部分按位求反。
• 比如：原码 1 0110100B，则反码为 1 1001011B。
• 8 位反码表示范围是 -127 到 127。
• n 位反码表示范围是 $-2^{n-1}-1$ 到 $2^{n-1}-1$。
• 缺点：在加减计算时，符号位也会进行运算，结果会出现错误。

3.2.3 补码 #

• 正数的补码是自身，负数的补码符号位不变，数值部分按位求反，然后整个数加 1。
• 比如：原码 1 0110100B，则补码为 1 1001100B。
• 8 位补码的表示范围是 -128 到 127。
• n 位补码表示范围是 $-2^{n-1}$ 到 $2^{n-1}-1$。
• 优点：符号位和有效值部分一起参加运算，将减法运算转换为加法运算，可以得出正确的二进制数加减法运算结果（计算结果仍然是补码，需要转换回原码）。

3.2.4 移码（增码） #

• 移码 = 真值 + 偏移量。
• 比如：-128 的移码，因为 -128 无法使用符号数表示，也就没办法通过符号位取反得到，因此可以将其变更为移码进行计算。-128 + 偏置值 $2^7$ = 0(00000000)。
• 8 位移码的表示范围是 -128 到 127。
• n 位移码表示范围是 $-2^{n-1}$ 到 $2^{n-1}-1$。
• 优点：使得所有的数都移动到正数上（包括0）。
• 优点：在偏移 2n-1 的情况下，移码等于补码的符号位取反，用作浮点数的阶码（决定浮点数的数值范围），保证浮点数的机器零全为 0，利于机器中判 0 电路的实现。

3.3 溢出 #

3.3.1 溢出的定义 #

• 当两个同符号的数相加或相异符号的数相减时，运算结果可能产生溢出。
• 比如：4 位原码 0 110(+6) + 0 100(+4) = 1 010(-2)，发生溢出，正确答案应为 0 1010(+10)。

3.3.2 进位判决法 #

• 记 C(n-1) 位表示最高数值位向最高位的进位，C(n) 表示符号位的进位，计算 C(n-1) ⊕ C(n)，若异或结果为真，则表示溢出，反之不溢出。
• 比如：4 位原码 0 110(+6) + 0 100(+4)，最高数值位相加进 1，符号位相加不进为 0，计算 1 ⊕ 0 = 1，结果为真，发生溢出。

3.3.3 双符号位判决法 #

• 计算时，采用双符号位，00 表示正号，11 表示负号。如果结果发生溢出，则双符号位会不一致（异或结果为真）。当结果的符号位为 01 时，称为上溢（正溢出），结果为 10 时，称为下溢（负溢出）。
• 比如：5 位原码 00 110(+6) + 00 100(+4)，相加结果为 01 010，结果符号位 01，发生溢出，出现上溢。

3.4 校验码 #

3.4.1 校验码的概念 #

• 校验码的使用是为了避免在数据传输过程中，可能出现的数据丢失，异化等问题。
• 校验码至少需要完成检错和纠错中的一项。
• 码距是指同一编码中，任意两个合法编码之间不同二进制数位数的最小值，比如：0011，0001，1111 都是有效的编码，0011 与 0001 只有 1 位不同，所以码距是 1，0011 与 1111 有 2 位不同，所以码距是 2，因为要取最小值，所以 0011，0001，1111 这组编码的码距是 1。
• 码距影响着检错和纠错，比如：码距为 1 时无法检错，码距为 2 时无法纠错。

3.4.2 奇偶校验码 #

• 奇偶校验码仅支持检错，不支持纠错。
• 奇校验可检测奇数位的错误。
• 在传输数据时，奇校验会在数据最高位前增加一位校验位 0 或 1，使得编码里面 1 的个数为奇数，比如：对数据 011，增加校验位 1，结果为 1011，此时若结果出现异常，则奇校验就会发现 1 的个数不是奇数，从而发现错误。
• 偶校验可检测偶数位的错误。
• 在传输数据时，偶校验会在数据最高位前增加一位校验位 0 或 1，使得编码里面 1 的个数为偶数，比如：对数据 011，增加校验位 0，结果为 0011，此时若结果出现异常，则偶校验就会发现 1 的个数不是偶数，从而发现错误。

3.4.3 CRC 循环冗余检验码 #

• 循环冗余校验码（CRC），简称循环码，是一种常用的、具有检错、纠错能力的校验码。
• 循环冗余校验码不同于奇偶校验码和海明校验码采用奇偶检测为手段检错和纠错，循环冗余校验通过某种数学运算来建立数据位和校验位的约定关系的。
• 循环冗余校验码由信息码 n 位和校验码 k 位构成，k 位校验位拼接在 n 位数据位后面，n+k 为循环冗余校验码的字长。
• CRC 编码时，将 n 位信息位表示为一个报文多项式 $f(x)$，最高幂次是 $x^{n-1}$。然后约定一个生成多项式 $G(x)$ ，多项式是一个 $k+1$ 位的二进制数，最高幂次是 $x^k$。将 $f(x)$ 乘以 $x^k$，即左移 k 位后，再使用模 2 除法除以 $G(x)$，得到的 $k$ 位余数就是校验位。
• CRC 码在存储或传送后，接收方可以使用生成多项式进行校验纠错。一个 CRC 码一定能被生成多项式整除，如果余数为0，则码字没有错误；若余数不为 0，则说明某位出错，不同的出错位置余数不同。在生成多项式确定时，出错位置和余数的对应关系是确定的。
• 示例如下：
  • 设约定的生成多项式为 $G(x)=x^4+x+1$，其二进制表示（ x=2 时）为 10011，共 5 位，其中 k=4。
  • 假设要发送数据序列的二进制为 101011（ $f(x)$ ），共 6 位。
  • 首先在要发送的数据后面加 4 个 0（ $f(x) * x^k$ ），二进制表示为 101011-0000，共 10 位。
  • 用生成多项式的二进制表示 10011 去除乘积 101011-0000（ $1010110000\over 10011$ ），按模 2 算法求得余数比特序列为 0100（注意余数一定是k位的）。
  • 将余数添加到要发送的数据后面，得到真正要发送的数据的比特流：101011-0100，其中前 6 位为原始数据，后 4 位为 CRC 校验码。
• 模 2 除法时，若被除数位数足够，即位数 ≥ 除数位数，则商对应写 1，不够则商对应写 0 ，然后进行异或运算，且不考虑进位和借位。比如下面算式：1111 位数 ≥ 1101，商取 1，对结果异或运算得 0010，10 的位数小于 1101，因此商取 0，向后借位直到位数大于 1101。

3.4.4 海明码 #

• 海明码，又称汉明码，是一种常用的、具有检错、纠错能力的校验码。
• 海明码在整个编码的 n 次方位置设置校验位，且要使所有二进制表示位置的第二位是 1 的数据异或值为 0。
• 海明码的校验码位数 k 必须是满足公式 $ 2^k-1 >= n+k $ 的最小值。（n 数据码位数）
• 示例如下：
  • 假设编码 1010110，数据位 n = 7，解得不等式 4，即：校验码有 4 个。
  • 在编码开头的 $2^0, 2^1, 2^2, 2^3$ 位设置校验码，数据位按顺序填充剩下的空间，即：ab 1 c 010 d 110。
  • 位置 1-7 二进制表示后（0001，0010…），对第二位是 1 的数据进行异或运算，有 b^1^1^0^1^0 = 0，可以解得：b = 1，a = 0，c = 1，d = 0。
  • 海明码有 01 1 1 010 0 110。

4.定点数与浮点数 #

4.1 定点数 #

• 约定所有数据的小数点隐含在某一个固定位置上，小数点位置固定不变，全称为定点表示法。
• 定点数分为定点整数与定点小数，小数点分别固定在最低有效数位之后与符号位之后，最高有效数位之前。
• 比如：0.1，1.0。
• 缺点：定点数所能表示的数值范围比较小，运算中很容易因结果超出范围而溢出。

4.2 浮点数 #

• 类似于科学计数法，约定一个数的小数点位置不是固定的，是可以浮动，小数点位置的变化，不会影响整体数值的大小，全称为浮点表示法。
• 浮点数的表示形式为：$ N = M * R ^ e $，其中 M 称为尾数， R 称为底数，e 称为阶码或指数。
• 浮点数所能表示的数值范围由阶码决定，所表示数值的精度则由尾数决定。
• 比如：$1 * 10^{10}$，$0.1 * 10^{11}$。
• 优点：在总位数相同的情况下，浮点数可以表示更大的数值。
• 注意：在计算机中，由于底数默认是 2，因此浮点数将按照（阶符 + 阶码 + 数符 + 数码）的格式顺序存储。
• 注意：无论是定点表示法还是浮点表示法的小数点，在计算机处理中都不占用二进制存储位。
• 注意：浮点数计算时，必须保证数的阶码一致，即对阶。

5.逻辑运算 #

• 或（||，OR，+）：一个为真则为真；
• 与（&&，AND，*）：一个为假则为假；
• 异或（⊕，XOR）：相异为真；
• 同或（⊙）：相同为真；
• 非（！，~，NOT）：取反；