E2 进制与数据存储

对应大纲： 2.1.5-1（进制与进制转换）、2.1.5-5（ASCII 码）、2.1.2-4（位运算）、2.1.2-2（基本数据类型）

⚠️ 进制题出现在 19 套真题的 19 套里——一套不落。 这是初赛第一高频考点，本章必须吃透。

📝 S1_位运算与进制.md 讲的是复赛怎么用位运算；本章讲的是初赛怎么考。两份互补，都要看。

一、进制转换

权值表（背下来，考场上直接用）

十六进制的字母：$A{=}10,\ B{=}11,\ C{=}12,\ D{=}13,\ E{=}14,\ F{=}15$

转十进制：按权展开

$$270_8 = 2\times64 + 7\times8 + 0 = 184 \qquad 1011_2 = 8+0+2+1 = 11$$

十进制转 R 进制：除 R 取余，倒着写

$$904 \div 16 = 56 \cdots 8;\quad 56 \div 16 = 3 \cdots 8;\quad 3 \div 16 = 0 \cdots 3 \Rightarrow 388_{16}$$

二 ↔︎ 八 ↔︎ 十六：直接分组，不用过十进制

• 二进制 → 八进制：从右往左每 3 位一组
• 二进制 → 十六进制：从右往左每 4 位一组

1101 0110 1011  →  十六进制  D 6 B
110 101 101 011 →  八进制    6 5 5 3

📝 这就是十六进制流行的原因：一位十六进制正好等于四位二进制。

小数部分

小数点右边的权是 $\dfrac{1}{R}, \dfrac{1}{R^2}, \dots$：

$$101.11_2 = 4 + 1 + \frac12 + \frac14 = 5.75 \qquad 32.1_8 = 24 + 2 + \frac18 = 26.125$$

📝 背这三个：$0.1_2 = 0.5$，$0.01_2 = 0.25$，$0.11_2 = 0.75$。

⚠️ 进制题的三条铁律

① 混进制运算，一律先全部转成十进制再算，最后再转回题目要的进制。

CSP 2024 第 2 题：$(14_8 - 1010_2) \times D_{16} - 1101_2$ → $(12 - 10) \times 13 - 13 = 13$ ✓

② 选项进制各不相同时，把选项也全转成十进制再比。

CSP 2019 第 9 题：$101010_2 + 166_8 = 42 + 118 = 160$。 选项 $(10110000)_2 = 176$、$(236)_8 = 158$、$(158)_{10} = 158$、$(A0)_{16} = \mathbf{160}$ ✓

③ 在原进制下直接做竖式加法，务必逐位算完再看选项。

CSP 2023 第 2 题：$12345670_8 + 07654321_8 = 22222211_8$（不是 $22222221_8$）——四个选项只差最后两位。

二、原码、反码、补码与整数范围

计算机里的负数用补码存储。

对 8 位为例，$-5$：

原码  1000 0101   （最高位是符号位，1 表示负）
反码  1111 1010   （符号位不变，其余取反）
补码  1111 1011   （反码 + 1）  ← 实际存的是这个

📝 正数的原码 = 反码 = 补码。 只有负数要变。

整数范围（必背）

⚠️ 负数比正数多一个（因为 $0$ 占了正数那侧的一个位置）。口诀：负的那头是整的（$-2147483648$），正的那头减一（$2147483647$）。

📝 两个近似值背下来：$2^{31} \approx 2.1 \times 10^9$（int 上限）、$2^{32} \approx 4.3 \times 10^9$（unsigned 上限）。

⚠️ 溢出：int 存不下就会「绕回去」。$2147483647 + 1 = -2147483648$。看到 a * b 且 $a, b$ 都上万，先想会不会溢出。

三、ASCII 码

只背三个基准值，其余全靠加减：

$$\texttt{'0'} = 48, \qquad \texttt{'A'} = 65, \qquad \texttt{'a'} = 97$$

📝 ASCII 表的顺序：数字 < 大写字母 < 小写字母。 所以 'A' < 'a' 成立。

⚠️ (char)('a' + 13) 是什么？ $97 + 13 = 110 = $ 'n'（CSP 2024 第 8 题）。用码值算，别数字母——数字母最容易差一。

⚠️ char 在常见平台上是有符号的，(char)0xff 是 $-1$ 不是 $255$。CSP 2021 第 17 题就考了这个（table 初始化成 0xff，输出 int(table[0]) 得 $-1$）。

⚠️ cout << 一个 char 打印的是字符不是数字。 要按数字打印必须写 cout << (int)c。CSP 2022 第 16 题就靠这个把「short 改成 char」变成了错误选项。

四、位运算

必背的三个套路

📝 由此推出两个高频结论：

• x & (x-1) == 0 ⟺ $x$ 是 2 的幂（只有一个 1）
• 反复做 x &= x - 1 直到 $x=0$，做的次数 = $x$ 的二进制里 1 的个数（popcount）

⚠️ CSP 2021 第 16 题整道题就是这两个套路：f(x) 数 1 的个数、g(x) 取 lowbit。认出来这题就秒了。

异或的性质（考得多）

$$a \oplus a = 0, \qquad a \oplus 0 = a, \qquad a \oplus b \oplus b = a$$

📝 所以**「一堆数里只有一个出现奇数次，其余都出现偶数次」→ 全部异或起来就是答案。**

五、浮点数的坑

⚠️ CSP 2022 第 18 题：(ans * ans == n) 这个浮点相等判断，$n$ 不是完全平方数时永远为 0，迭代再多次也没用。

⚠️ CSP 2023 第 16 题：输入 1 1 5 这种构不成三角形的边长，海伦公式里根号内是负数，实测输出 nan——所以「程序总是输出四位小数」是错的。

📝 浮点数的乘法交换顺序会改变二进制位（CSP 2023 第 16 题实测：$1\sim120$ 的全部三元组里有 142190 组的 double 结果不完全相同），但保留 4 位小数后看不出差别。这个细节值得记住。

30 秒自测

1. $270_8$ 是十进制多少？$904$ 的十六进制是多少？
2. 二进制转十六进制，从哪边开始、每几位一组？
3. int 的范围是多少？为什么负数比正数多一个？
4. '0'、'A'、'a' 的 ASCII 码各是多少？
5. x & (x-1) 和 x & (-x) 分别是干什么的？
6. 怎么判断 $x$ 是不是 $2$ 的幂？
7. $a \oplus b \oplus b$ 等于什么？
8. 为什么不能写 if (a == b) 比较两个 double？