C++ GESP 三级认证手册：计算机基础与算法

• 问题：存在'正负 0'（+0 原码 00000000，-0 原码 10000000），导致计算矛盾。

2.1.2 反码

• 定义：正数反码 = 原码；负数反码 = 符号位不变，数值位按位取反（0 变 1，1 变 0）。
• 示例（8 位 char）：

// 5 反码 = 00000101（与原码一致）
// -5 反码 = 11111010（符号位 1 不变，数值位 0000101 取反为 1111010）

• 问题：仍存在'正负 0'（-0 反码 11111111），未解决计算问题。

2.1.3 补码（计算机实际存储方式）

• 定义：正数补码 = 原码；负数补码 = 反码 + 1（末尾加 1，若有进位则传递）。
• 示例（8 位 char）：

// 5 补码 = 00000101
// -5 补码 = 11111010 + 1 = 11111011

• 优势：解决'正负 0'问题（+0 和 -0 补码均为 00000000），简化减法运算（a - b = a + (-b)，只需加法器）。

2.2 进制转换

在计算机中，数据常以不同进制表示。

2.2.1 进制的表示

• 十进制：日常使用，由 0-9 组成，C++ 中直接书写（如 123）。
• 二进制：由 0-1 组成，C++ 中以 0b 前缀表示（如 0b101 表示 5）。
• 八进制：由 0-7 组成，C++ 中以 0 前缀表示（如 017 表示 15）。
• 十六进制：由 0-9、A-F（或 a-f）组成，C++ 中以 0x 前缀表示（如 0x1F 表示 31）。

2.2.2 转换方法

1. 非十进制转十进制 规则：按'位权展开求和'，位权 = 基数 ^ 位索引（从右往左，起始索引为 0）。 示例：
   • 二进制 1011 转十进制： 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 8 + 0 + 2 + 1 = 11
   • 十六进制 0x3A 转十进制： 3×16¹ + 10×16⁰ = 48 + 10 = 58（A 代表 10）
2. 十进制转非十进制 规则：整数部分'除基取余，逆序排列'；小数部分'乘基取整，顺序排列'。 示例：
   • 十进制 13 转二进制： 13 ÷ 2 = 6 余 1 6 ÷ 2 = 3 余 0 3 ÷ 2 = 1 余 1 1 ÷ 2 = 0 余 1 逆序取余得 1101。
   • 十进制小数 0.625 转二进制： 0.625 × 2 = 1.25 → 整数部分为 1（二进制小数第一位），剩余小数部分 0.25 0.25 × 2 = 0.5 → 整数部分为 0（二进制小数第二位），剩余小数部分 0.5 0.5 × 2 = 1.0 → 整数部分为 1（二进制小数第三位），剩余小数部分 0（转换结束） 将取出的整数部分按顺序排列，得到 0.101
3. 二进制与八 / 十六进制互转
   • 二进制转八进制。 规则：将二进制数从右往左每 3 位分为一组，若最左侧不足 3 位，则在左侧补 0 凑满 3 位；每组 3 位二进制对应 1 位八进制数（0-7），最后拼接所有结果。 示例：二进制数 10110：
     • 1.分组：从右往左每 3 位一组。 二进制数 10110 共 5 位，从右往左拆分： 右侧第一组：110（最后 3 位） 剩余左侧：10（只有 2 位，不足 3 位）
     • 2.补 0 凑位：对左侧不足 3 位的部分，在左边补 0，凑成 3 位。 左侧剩余的 10 补 1 个 0 → 010
     • 3.分组结果：010（补 0 后）和 110
     • 4.每组转换为八进制： 010 对应的十进制是 0×2² + 1×2¹ + 0×2⁰ = 2 → 八进制为 2 110 对应的十进制是 1×2² + 1×2¹ + 0×2⁰ = 6 → 八进制为 6
     • 5.拼接结果：将两组的八进制数按顺序拼接 → 26
   • 二进制转十六进制。 规则：将二进制数从右往左每 4 位分为一组，若最左侧不足 4 位，则在左侧补 0 凑满 4 位；每组 4 位二进制对应 1 位十六进制数（0-9、A-F，其中 A=10，B=11…F=15），最后拼接所有结果。 示例：二进制数 10110 :
     • 1.分组：从右往左每 4 位一组。 二进制数 10110 共 5 位，从右往左拆分： 右侧第一组：0110（最后 4 位） 剩余左侧：1（只有 1 位，不足 4 位）
     • 2.补 0 凑位：对左侧不足 4 位的部分，在左边补 0，凑成 4 位。 左侧剩余的 1 补 3 个 0 → 0001
     • 3.分组结果：0001（补 0 后）和 0110
     • 4.每组转换为十六进制： 0001 对应的十进制是 0×2³ + 0×2² + 0×2¹ + 1×2⁰ = 1 → 十六进制为 1 0110 对应的十进制是 0×2³ + 1×2² + 1×2¹ + 0×2⁰ = 6 → 十六进制为 6
     • 5.拼接结果：将两组的十六进制数按顺序拼接 → 16
   • 八进制转二进制。 规则：将八进制的每一位数字，转换为对应的 3 位二进制数（不足 3 位时在左侧补 0），最后拼接所有结果。 示例：八进制数 265 ：
     • 1.拆分八进制的每一位：2、6、5
     • 2.每一位转换为 3 位二进制： 八进制 2 → 二进制 010（2 的二进制是 10，补 1 个前导 0 凑 3 位） 八进制 6 → 二进制 110（6 的二进制是 110，刚好 3 位） 八进制 5 → 二进制 101（5 的二进制是 101，刚好 3 位）
     • 3.拼接结果：010 + 110 + 101 = 010110101 因此，八进制 265 转换为二进制是 010110101（可省略前导 0，简写为 10110101）。
   • 十六进制转二进制。 规则：将十六进制的每一位数字（0-9、A-F），转换为对应的 4 位二进制数（不足 4 位时在左侧补 0），最后拼接所有结果。 示例：十六进制数 3A7 ：
     • 1.拆分十六进制的每一位：3、A、7（A 代表 10）
     • 2.每一位转换为 4 位二进制： 十六进制 3 → 二进制 0011（3 的二进制是 11，补 2 个前导 0 凑 4 位） 十六进制 A（10）→ 二进制 1010（10 的二进制是 1010，刚好 4 位） 十六进制 7 → 二进制 0111（7 的二进制是 111，补 1 个前导 0 凑 4 位）
     • 3.拼接结果：0011 + 1010 + 0111 = 001110100111 因此，十六进制 3A7 转换为二进制是 001110100111（可省略前导 0，简写为 1110100111）。

2.3 位运算

位运算是直接对整数的二进制位进行操作的运算，效率极高，常用于底层编程、状态压缩等场景。GESP 三级要求掌握 6 种基本位运算：

2.3.1 基本位运算符

三、C++ 知识

3.1 一维数组

数组是相同类型数据的连续集合，一维数组是 GESP 三级的核心数据结构，用于存储批量数据。

3.1.1 数组的定义与初始化

定义：数据类型 数组名 [长度];（长度必须是常量）。

// 方式 1：指定长度并初始化（未赋值元素默认为 0）
int arr1[5] = {1, 2, 3}; // arr1 = [1, 2, 3, 0, 0]
// 方式 2：省略长度，由初始化元素个数决定
int arr2[] = {4, 5, 6}; // 长度为 3，arr2 = [4, 5, 6]

3.1.2 数组的访问与遍历

访问：通过索引（从 0 开始）访问，如 arr[0]（第一个元素）。 遍历：常用 for 循环遍历所有元素：

int arr[] = {10, 20, 30, 40};
int len = sizeof(arr) / sizeof(arr[0]); // 计算数组长度（4）
for (int i = 0; i < len; i++) {
    cout << arr[i] << " "; // 输出：10 20 30 40
}

3.1.3 数组作为函数参数

数组传参时，实际传递的是首地址，需额外传递长度：

// 求数组元素和
int sumArray(int arr[], int len) {
    int sum = 0;
    for (int i = 0; i < len; i++) {
        sum += arr[i];
    }
    return sum;
}

int main() {
    int nums[] = {1, 2, 3, 4};
    int len = 4;
    cout << "和为：" << sumArray(nums, len); // 输出 10
    return 0;
}

3.2 字符串及其函数

字符串是字符的序列，C++ 中常用 char 数组和 string 类（更便捷）表示，需掌握字符串的基本操作。

3.2.1 字符串的定义

// 1. char 数组（需以'\0'结尾，表示字符串结束）
char str1[] = "hello"; // 自动添加'\0'，长度为 6（h,e,l,l,o,\0）
// 2. string 类（需包含<string>头文件，无需手动加结束符）
#include <string>
string str2 = "world";

3.2.2 常用字符串函数

1. 长度与拼接
   • length()/size()：返回字符串长度。
   • • 或 append()：拼接字符串。

string s1 = "abc", s2 = "def";
cout << s1.length(); // 输出 3
cout << s1 + s2;     // 输出"abcdef"

2. 大小写转换
   • 需结合头文件的 toupper()（转大写）和 tolower()（转小写）：

#include <cctype>
string s = "AbC";
for (int i = 0; i < s.size(); i++) {
    s[i] = toupper(s[i]); // 转大写，结果为"ABC"
}

3. 查找与替换
   • find(sub, pos)：从 pos 位置开始查找子串 sub，返回起始索引（未找到返回 string::npos 注意判断其值为 -1）。
   • replace(pos, len, sub)：从 pos 位置替换 len 个字符为 sub。

string s = "hello world";
int pos = s.find("world"); // pos=6
if (pos != string::npos) {
    s.replace(pos, 5, "C++"); // 替换为"hello C++"
}

4. 分割字符串
   • substr(pos, count)：用于从字符串中提取子串。
     • 参数说明：
       • pos：子串的起始位置（从 0 开始计数），默认值为 0。
       • count：子串的长度，默认值为 std::string::npos（一个静态常量，表示'直到字符串末尾'）。

示例：

string s = "I love C++";
string delimiter = " ";
size_t pos = 0;
while ((pos = s.find(delimiter)) != string::npos) {
    string part = s.substr(0, pos); // 截取从 0 到 pos 的子串
    cout << part << endl;           // 输出"I"、"love"
    s.erase(0, pos + delimiter.length()); // 移除已处理部分
}
cout << s; // 输出"C++"

3.3 枚举算法

枚举算法（穷举法）是逐一尝试所有可能解，从中找出符合条件的解，适合解空间较小的问题。

3.3.1 核心思想

1. 确定枚举范围（可能解的集合）；
2. 明确判断条件（解需要满足的规则）；
3. 遍历所有可能解，筛选出符合条件的解。

3.4 模拟算法

模拟算法是按问题的实际流程，用代码一步步重现过程，从而得到结果，适合解决规则明确的过程性问题。

3.4.1 核心思想

1. 分析问题的步骤和规则；
2. 用变量模拟过程中的关键状态；
3. 按步骤逐步更新状态，直至过程结束。