软件设计师考试 - 计算机科学基础知识

Mar 15, 2025 · 6 分钟阅读 · 软考软件设计师 ·

文章目录

一、进制及其转换

1.1 常见进制

二进制（Binary）：由0和1组成，基数为2；位权：$\ldots, 2^2, 2^1, 2^0 $。
八进制（Octal）：由0-7组成，基数为8；位权：$\ldots, 8^2, 8^1, 8^0 $。
十进制（Decimal）：由0-9组成，基数为10；位权：$\ldots, 10^2, 10^1, 10^0 $。
十六进制（Hexadecimal）：由0-9和A-F组成，基数为16；位权：$\ldots, 16^2, 16^1, 16^0 $。

1.2 进制转换

二进制转十进制：按位权展开，逐位相加。
- 例如：1011(二进制) = $$ \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 \times 2^3 & 0 \times 2^2 & 1 \times 2^1 & 1 \times 2^0 \\ \end{bmatrix} $$ = 8 + 0 + 2 + 1 = 11(十进制)。
八进制转十进制：按位权展开，逐位相加。
- 例如：127(八进制) = $$ \begin{bmatrix} 1 & 2 & 7 \\ 1 \times 8^2 & 2 \times 8^1 & 7 \times 8^0 \\ \end{bmatrix} $$ = 64 + 16 + 7 = 87(十进制)。
十六进制转十进制：按位权展开，逐位相加。
- 例如：1A3(十六进制) = $$ \begin{bmatrix} 1 & A & 3 \\ 1 \times 16^2 & 10 \times 16^1 & 3 \times 16^0 \\ \end{bmatrix} $$ = 256 + 160 + 3 = 419(十进制)。
十进制转二进制、八进制、十六进制：除基数取余，余数逆序。

十进制转二进制	十进制转八进制	十进制转十六进制
除`2`取余，余数逆序。例如`11`= $$ \left [ \begin{array}{l} 11 \div 2 = 5 & \cdots 1 \\ 5 \div 2 = 2 & \cdots 1 \\ 2 \div 2 = 1 & \cdots 0 \\ 1 \div 2 = 0 & \cdots 1 \\ \end{array} \right \uparrow = 1011 $$	除`8`取余，余数逆序。例如`87`= $$ \left[ \begin{array}{l} 87 \div 8 = 10 & \cdots 7 \\ 10 \div 8 = 1 & \cdots 2 \\ 1 \div 8 = 0 & \cdots 1 \\ \end{array} \right \uparrow = 127 $$	除`16`取余，余数逆序。例如`419`= $$ \left[ \begin{array}{l} 419 \div 16 = 26 & \cdots 3 \\ 26 \div 16 = 1 & \cdots 10 \\ 1 \div 16 = 0 & \cdots 1 \\ \end{array} \right \uparrow = 1A3 $$

二进制转八进制、十六进制：从右向左将二进制数分组，对于八进制每3位一组转换，对于十六进制每4位一组转换。
- 例如：10110001(二进制) = 010 110 001 = 261(八进制)。
- 例如：10110001(二进制) = 1011 0001 = B1(十六进制)。

1.3 浮点数进制转换

R进制：基数为R；位权：$\ldots, R^2, R^1, R^0, R^{-1}, R^{-2}, \ldots $。
R进制转十进制：按位权展开，逐位相加。
- 例：127.1(八进制)= $$ \begin{bmatrix} 1 & 2 & 7 & 1 \\ 1 \times 8^2 & 2 \times 8^1 & 7 \times 8^0 & 1 \times 8^{-1} \\ 1 \times 64 & 2 \times 8 & 7 \times 1 & 1 \times \left(\frac{1}{8}\right)^{1} \\ \end{bmatrix} $$ = 64+16+7+0.125 =87.125(十进制)。
十进制转R进制：整数部分-除以基数取余,余数逆序；小数部分-乘以基数取整,整数正序。
- 例：0.625(十进制)= $$ \left[ \begin{array}{l} 0.625 \times 2 = 1.25 & 取1，剩余0.25 \\ 0.25 \times 2 = 0.5 & 取0，剩余0.5 \\ 0.5 \times 2 = 1.0 & 取1，剩余0.0 \\ \end{array} \right] $$ = 0.101(二进制)。
二进制转八进制、十六进制：小数点开始,向左和向右分组，对于八进制每3位一组转换，对于十六进制每4位一组转换。
- 例如：10110001.0111(二进制) = 010 110 001.011 100 = 261.34(八进制)。
- 例如：10110001.0111(二进制) = 1011 0001.0111 = B1.7(十六进制)。

二、计算机内数据表示

2.1 基本单位

位（Bit）：最小数据单位，0或1。
字节（Byte）：8位组成1字节，可表示范围 00000000（0）到 11111111（255）。

2.2 数值数据的表示

计算机内部使用二进制表示数据，数值表示方式有：

定点数（Fixed-point Number）：一种固定小数位数的表示方法，小数点的位置是固定的。整数部分和小数部分的位数是固定的，例如一个16位的定点数可以表示为8位整数 + 8位小数。常用于对计算速度要求高且数值范围较小的场景，如嵌入式系统、数字信号处理（DSP）、金融计算等。
浮点数（Floating-point Number）：一种科学计数法的表示方法，小数点的位置可以浮动。例如，IEEE754标准的单精度浮点数（32位）表示为：1位符号位 + 8位指数位 + 23位尾数位。常用于处理大范围数值或高精度计算，如科学计算、图形处理、机器学习等。
整数（Integer）：用于表示整数值，分为有符号和无符号两种。
定点小数（Fixed-point Decimal）：专门用于表示小数，常用于金融计算。
高精度数（Arbitrary-precision Number）：用于需要极高精度的场景，如密码学。

2.2.1 整数

无符号整数（Unsigned Integer）：直接二进制表示（如00101011=43），范围为 [$0$, $2^n$-1]（$n$为位数），例如，8位无符号整数范围：0 到 255。
有符号整数（Signed Integer）：最高位为符号位（0正1负），其余位表示数值。在计算机中，有符号整数通常采用补码表示，范围为 [$-2^{n-1}$, $2^{n-1}$-1]（$n$为位数），例如，8位有符号整数范围：-128 到 127。
- 原码：最高位为符号位（0正1负），如+5原码= 00000101，-5原码= 10000101
- 反码：对负数进行按位取反（符号位不变），如+5反码= 00000101，-5反码= 11111010
- 补码：在反码的基础上，对负数再加1。
  - 正数：与原码相同；负数：反码+1，如 +5补码= 00000101，-5补码= 11111011
  - 优势：解决了“+0”和“-0”不唯一的问题（00000000=0，10000000=-128）, 统一加减法运算，无需额外处理符号位。
  - 补码的表示范围比原码（8位原码范围：-127到127）和反码多一个负数（如8位补码范围是 -128 到 127）。
- 移码：数值 + 偏移量（通常为 $2^{n-1}$，其中 $n$ 是位数），使所有数都变为非负数。
  - 例如：对于8位移码，偏移量为128。+5移码= 10000101(5+128 = 133)，-5移码= 01111011(-5+128 = 123)。
  - 移码主要用于浮点数的指数部分，方便比较大小。移码的表示范围对称，且没有符号位问题。

2.2.2 浮点数（IEEE754标准）

浮点数表示方法： $ \text{数值} = (-1)^S \times 1.M \times 2^E $
- $ S $ 是符号（0正，1负）
- $ M $ 是尾数，由于浮点数的规范化表示，尾数的最高位总是1，因此实际尾数为$ 1.M $
- $ E $ 是指数，偏移量为 $2^{n-1}-1$，即8位的移码的偏移量为 $2^{8-1}-1=127$
- 类似于十进制的科学计数法，如 $81.25=0.8125 \times 10^2$，二进制如 $101.011=0.101011 \times 2^3$。
IEEE754标准主要支持两种浮点数格式：单精度（32位）（4字节）和双精度（64位）（8字节），具体表示格式如下：

字段 S（符号位） E（指数位） M（尾数位）

单精度（32位） 1位 8位（偏移量127） 23位

双精度（64位） 1位 11位（偏移量1023） 52位
示例：以单精度（32位）为例： $ 0 \,\, 10000010 \,\, 11000000000000000000000 $
- 符号位 $ S = 0 $，表示正数。
- 指数位 $ E = 10000010_2 = 130_{10} $，实际指数 $ E_{\text{实际}} = 130 - 127 = 3 $
- 尾数位 $ M = 11000000000000000000000_2 $，实际尾数 $ 1.M = 1.11_2 = 1.75_{10} $
- 因此，该浮点数的数值为： $ (-1)^0 \times 1.75 \times 2^3 = 1.75 \times 8 = 14.0 $
IEEE754标准定义的特殊值的表示：
- 零值：指数和尾数全为0，符号位为0表示+0，符号位为1表示-0。
- 无穷大：指数全为1，尾数全为0，符号位为0表示+∞，符号位为1表示-∞。
- NaN（非数）：指数全为1，尾数不全为0，表示无效的浮点数。

字段	S（符号位）	E（指数位）	M（尾数位）
单精度（32位）	1位	8位（偏移量127）	23位
双精度（64位）	1位	11位（偏移量1023）	52位

2.3 非数值数据的表示

2.3.1 字符（Character）

常用编码标准：
1. ASCII码：7位二进制编码，覆盖128个字符（如A=65=01000001）；扩展ASCII（8位）支持256个字符（含特殊符号）。
2. Unicode：16位或更多位表示的全球字符集，常用实现为UTF-8、UTF-16。
  - UTF-8（变长编码）：英文 1字节（兼容ASCII），中文：通常3字节，如 汉 → E6 B1 89
  - UTF-16/UTF-32：固定2或4字节

2.3.2 其他数据类型

布尔值（Boolean）：用1位表示，0表示False，1表示True。
字符串（String）：由多个字符组成，通常以空字符（’\0’）结尾，如 "Hello" → 48 65 6C 6C 6F 00。
指针（内存地址）：用于存储内存地址。常用十六进制表示，如 0x7FFF4500。
复合类型
- 数组：连续内存存储同类型数据
- 结构体：不同数据类型的组合，需考虑内存对齐

2.4. 数据类型总结

数据类型	表示方式	特点
整数	无符号、有符号（原码、反码、补码）	简单、高效
定点数	固定小数点位置	计算快，范围有限
浮点数	符号位 + 指数位 + 尾数位	范围大，精度高，计算复杂
字符	ASCII、Unicode	表示文本数据
布尔值	1位（0或1）	表示逻辑值
字符串	字符序列 + 结束符	表示文本
指针	内存地址	用于间接访问数据

三、计算机内数据的运算

3.1 算数运算

二进制算数运算（加减乘除）基本原理与十进制类似。

浮点数的运算：①对阶(小阶向大阶看齐，小阶增加几位其尾数就右移几位)，②尾数计算，③结果规格化，④舍入，⑤溢出/下溢处理。
示例：单精度浮点数 $ 2.25 $ 和 $ 1.5 $ 表示为IEEE 754格式：
- $ 2.25 = 0 \, 10000000 \, 00100000000000000000000 = 1.M \times 2^{E-127} = 1.001 \times 2^1 $
- $ 1.5 = 0 \, 01111111 \, 10000000000000000000000 = 1.M \times 2^{E-127} = 1.1 \times 2^0 $
计算加法（ $ 2.25 + 1.5 $）：
1. 对阶：将 $ 1.5 $ 的指数调整为1，尾数变为 $ 0.11 \times 2^1 $
2. 尾数相加：$ 1.001 + 0.11 = 1.111 $
3. 规范化：结果为$ 1.111 \times 2^1 = 3.75 $
计算减法（ $ 2.25 - 1.5 $）：
1. 对阶：将 $ 1.5 $ 的指数调整为1，尾数变为 $ 0.11 \times 2^1 $
2. 尾数相减：$ 1.001 - 0.11 = 0.011 $
3. 规范化：结果为 $ 0.011 \times 2^1 = 1.1 \times 2^{-1} = 0.75 $
计算乘法（ $ 2.25 \times 1.5 $）：
1. 指数相加：$ 1+0=1 $
2. 尾数相乘：$ 1.001 \times 1.1 = 1.1011 $
3. 规范化：结果为$ 1.1011 \times 2^1 = 3.375 $
计算除法（ $ 2.25 \div 1.5 $）：
1. 指数相减：$ 1-0=1 $
2. 尾数相除：$ 1.001 \div 1.1 = 0.1100 $
3. 规范化：结果为 $ 0.11 \times 2^1 = 1.1 \times 2^0 = 1.5 $

3.2 逻辑运算

逻辑运算基于布尔代数，主要处理真（True）和假（False）两种值。包括：
- 与（AND）（符号：∧ 或 &&）：只有当所有输入都为真时，输出才为真。当遇到为假的条件时停止计算（短路）。
- 或（OR）（符号：∨ 或 ||）：只要有一个输入为真，输出就为真。当遇到为真的条件时停止计算（短路）。
- 非（NOT）（符号：¬ 或 !）：对输入进行取反操作。
- 异或（XOR）（符号：⊕）：当输入值不同时，输出为真(有且仅有一个为真)。
- 同或（XNOR）（符号：⊙）：当输入值相同时，输出为真。
- 与非（NAND）（符号：⊼）：与运算后再取反。
- 或非（NOR）（符号：⊽）：或运算后再取反。
二进制逻辑运算是对二进制数（位）进行逐位操作的运算。
- 与（AND，符号：&）：逐位进行与运算，两个逻辑值全1时才取1。
- 或（OR，符号：| ）：逐位进行或运算，只要有一个1就取1。
- 非（NOT，符号：~）：逐位进行取反操作。
- 异或（XOR，符号：^）：逐位进行异或运算。
- 左移（Left Shift）（符号：<<）：将二进制数向左移动指定位数，右侧补零。
- 右移（Right Shift）（符号：>>）：将二进制数向右移动指定位数，左侧补零或补符号位（取决于实现）。
- 或非（NOR，符号：⊽）：先进行或运算，然后对结果取非。
应用场景
- 逻辑运算：用于条件判断、布尔表达式、逻辑电路设计等。
- 二进制逻辑运算：用于位操作、数据压缩、加密算法、硬件控制等。

3.3 校验码（Check Code）

**校验码（Check Code）**是计算机系统中一种用于验证数据完整性的技术。（是一种冗余信息，附加在原始数据上）

奇偶校验码（Parity Check）：在数据中添加一个校验位，使得数据中(二进制)1的个数为奇数（奇校验）或偶数（偶校验）。只能检测奇数个数据位出错。
校验和（Checksum）：将数据分成若干字节（Byte），将所有字节相加，取结果的低8位或低16位作为校验和。无法检测某些特定错误（如字节顺序错误）。
循环冗余校验码CRC（Cyclic Redundancy Check）：采用模2取余的方式来构造固定长度的校验码。用于在数据传输过程中检测错误。检测能力强，能检测多数据位错误、突发错误。
海明码（Hamming Code）：在数据中插入多个校验位，通过异或运算检测和纠正单数据位错误。校验位数量较多，冗余度较高。
里德-所罗门码（Reed-Solomon Code）：基于有限域的纠错码，能够纠正多个错误。纠错能力强，适合纠正突发错误。冗余度较高。

3.3.1 校验码对比

校验码	检测能力	纠正能力	计算复杂度	应用场景
奇偶校验码	奇数个比特错误	无	低	简单数据传输
校验和	部分错误	无	低	网络协议、文件校验
CRC	多位错误、突发错误	无	中	数据存储、网络通信
海明码	单比特错误、双比特错误	单比特错误	中	内存纠错、通信系统
里德-所罗门码	多位错误、突发错误	多位错误	高	光盘、卫星通信、二维码

如果需要简单的错误检测，选择奇偶校验码或校验和。
如果需要较强的错误检测能力，选择CRC。
如果需要纠错能力，选择海明码或里德-所罗门码。

3.3.2 海明码校验位计算

海明码是一种纠错码，通过在数据位中插入校验位，使得可以检测并纠正单个比特的错误，甚至检测双比特错误。

校验位的数量 $ k $ 必须满足：$\boxed{ 2^k \geq m + k + 1 }$，其中 $ m $ 是数据位的位数，$ k $ 是校验位的位数。
- 例如，4位数据需要3个校验位，因为 $ (2^3 = 8) \geq (4 + 3 + 1 = 8) $。
校验位都位于2的幂次位置上，即 $ P_j $ 位于位序 $ 2^{j-1} $（如$ P_1 $在$2^0=1$，$ P_2 $在$2^1=2$，$ P_3 $在$2^2=4$，$ P_4 $在$2^3=8$）。
- 例如，对于一个7位的数据，需要插入4个校验位，分别位于第1、2、4、8位。
覆盖规则：每个校验位$ P_i $（位置为$ 2^{i-1} $）覆盖所有位置二进制表示中第$ i $位为1的位。例如：
- 校验位$ P_1 $（位置1）覆盖二进制表示中第1位为1的位，即001,011,101,111,…（即位置1,3,5,7,…）
- 校验位$ P_2 $（位置2）覆盖二进制表示中第2位为1的位，即010,011,110,111,…（即位置2,3,6,7,…）
- 校验位$ P_3 $（位置4）覆盖二进制表示中第3位为1的位，即100,101,110,111,…（即位置4,5,6,7,…）

计算示例

问题1：32位数据至少需要多少个校验位才能构成海明码？
- 计算过程：
  1. 代入 $ m = 32 $，求最小的 $ k $ 使得不等式成立： $ 2^k \geq 32 + k + 1 $
  2. 尝试不同的 $ k $：
    - $ k = 5 $: $ 2^5 = 32 \geq 32 + 5 + 1 = 38 $ → 不成立（32 < 38）。
    - $ k = 6 $: $ 2^6 = 64 \geq 32 + 6 + 1 = 39 $ → 成立（64 ≥ 39）。
  3. 因此，最少需要 6 位校验位。
问题2：计算4位数据1011，插入校验位，形成的海明码。
- 计算过程：
  1. 确定校验位的位置:
    - 4位数据需要3个校验位，位置为1、2、4，即：
```
 位置：1  2  3  4  5  6  7
 类型：P1 P2 D1 P4 D2 D3 D4
 值：  ?  ?  1  ?  0  1  1
```
  2. 确定每个校验位覆盖的数据位:
    - 校验位$ P_1 $（位置1）覆盖二进制表示中第1位为1的位，即001,011,101,111（即位置1,3,5,7）
    - 校验位$ P_2 $（位置2）覆盖二进制表示中第2位为1的位，即010,011,110,111（即位置2,3,6,7）
    - 校验位$ P_3 $（位置4）覆盖二进制表示中第3位为1的位，即100,101,110,111（即位置4,5,6,7）
  3. 计算每个校验位的值：每个校验位的值是其覆盖的所有数据位的 异或(XOR) 结果。
    - 校验位$ P_1 $（位置1）覆盖位置3, 5, 7：$ P_1 = D_1 \oplus D_2 \oplus D_4 = 1 \oplus 0 \oplus 1 = 1 \oplus 1 = 0 $
    - 校验位$ P_2 $（位置2）覆盖位置3, 6, 7：$ P_2 = D_1 \oplus D_3 \oplus D_4 = 1 \oplus 1 \oplus 1 = 0 \oplus 1 = 1 $
    - 校验位$ P_3 $（位置4）覆盖位置5, 6, 7：$ P_4 = D_2 \oplus D_3 \oplus D_4 = 0 \oplus 1 \oplus 1 = 1 \oplus 1 = 0 $
  4. 将计算得到的校验位插入到相应的位置，最终的海明码为 0 1 1 0 0 1 1。

END .