尧图网页设计 
听故事学语言 · 第三章 类型的诞生本章回答四个问题。类型是什么char 为什么本质上是整数一个数为什么会超界变成负数小数为什么算不准序章埋下的给 B 加上类型在本章展开全貌。32768 冤案本章开庭。一、类型是标签第二章立过一条论数据的本质其实就是内存里面的存放空间。内存是一排排编了号的字节盒子但上一章只说了一半。一盒 8 个开关读作 01100101它是十进制 101还是字母 e盒子没有任何提示两种读法都对也都不对。决定怎么读的是贴在盒子上的标签。C 语言把它叫作类型。一张类型标签只写两件事。一是多大占几个字节二是怎么读按什么规则解读这些开关。同一盒字节贴 int 标签就按整数读贴 char 标签就按字符读。字节一个都没变变的是读法。这个认识是本章的地基。程序里大量的离奇错误数据本身完好无损坏的是读法。第二章 1TB 变 931GB 的冤案正是同族字节一个没少尺子换了一把。类型也不是凭空设计的。序章讲过1972 年PDP-11 的字节寻址逼着里奇给 B 加上类型char 为字节而生int 为计算而设。本章把这张标签的里里外外讲全。二、整数族谱与一条下限规则C 语言的整数类型是一张族谱先给零基础读者一张速览表。类型典型宽度常见取值范围用途一句话char1 字节-128 127小整数与字符第三节的主角short2 字节-32768 32767省内存的小整数int4 字节约 ±21.4 亿日常计算的主力long4 或 8 字节随平台与平台纠缠的类型long long8 字节约 ±922 亿亿给大数准备的类型这张表要先读出一条反常的规则。典型宽度不等于保证宽度。C 标准从不写死 int 是几个字节只规定下限int 至少 16 位long long 至少 64 位。第一章语法卡里那个奇怪的 -32767正是在这条规则下露出的马脚标准连 int 的最小范围都只敢从 -32767 保起。为什么不敢写死因为宽度随硬件一步步变大。int 出生在 16 位的 PDP-11 上2 个字节最大 32767记住这个数字本章第四节的开庭主角。后来 32 位计算机普及int 变成 4 个字节今天的家用计算机上int 的常见范围是正负 21.4 亿。同一份代码在两代机器上读出两个宽度所以标准只敢写下限写死的那部分交给了历史。族谱里最新的一页属于 long long。二十世纪九十年代64 位计算登场各家编译器各造各的大数类型微软自造了__int64。1999 年C99 标准把 long long 正式收编至少 64 位能数到 922 亿亿。有意思的是微软的反应它拖到 2010 年前后的 Visual Studio 才承认这个标准类型直到今天64 位 Windows 上 long 依然是 4 个字节与 Unix 阵营各走各路。又一个该死的标准大数类型也有派系。变量的声明写法从本章起正式启用。int score 98; // 声明一个 int 盒子贴上 int 标签放进 98 char initial D; // char 盒子放一个字符 long long big 9007199254740993; // long long 盒子放一个大数 printf(%lld\n, big); // 大数的专用格式符 %lld变量就是带标签的盒子。盒子里那几个字节就放在内存的某个地址上。第二章的地址第三章的标签从此合流。变量的第一件本事是交换两个盒子里的数。讲到哪里就练到哪里三种方法一条比一条妙。【例1】交换两个数第三方变量法。int a 13, b 7;借一个临时变量 tt a; a b; b t;交换完成。这是最稳的写法竞赛与工程通用。【例2】交换两个数求和赋值法。不用第三个变量a a b; b a - b; a a - b;走一遍a 里存的是和 20b 先取走差得到 13a 再减去新的 b 得到 7。数学上无懈可击但 ab 一旦超出 int 的上限就会出错超界的后果本章第四节专门开庭。两数相加可能超 21.4 亿时老老实实用第三方变量。【例3】交换两个数位运算异或法。a ^ b; b ^ a; a ^ b;三步交换一个临时变量都没用。原理是异或的可逆性同一个数异或两次就复原三步下来恰好各归各位。警告一条若 a 与 b 是同一个存储位置第一步a ^ a直接把它清成 0交换变成销毁日后在数组里遇到自己和自己交换时要当心。三、伪装成字符的整数char 是族谱里最特殊的成员它只有 1 个字节标签上却写着字符。可一旦翻开底册char 是一位伪装成字符的整数。底册叫ASCIIAmerican Standard Code for Information Interchange美国信息交换标准代码。1963 年美国标准协会发布了这份编码表7 个位128 个码位1967 年修订时补齐了小写字母。它规定 65 号是 A97 号是 a48 号是字符 0。注意最后这条。字符 0 与数字 0 是两位住户字符 0 存的是码位 48数字 0 存的是数值 0。char 与整数可以互相换算两条输出当场验证。printf(%d\n, A); // 65%d 拿整数读法读 char printf(%c\n, 65); // A%c 拿字符读法读整数同一个字节%d 按整数读%c 按码表读。char 之所以本质上是整数因为它骨子里就是一个 8 位整数只是平时按码表解读。这张码表里藏着第二章位运算的第一次实战。看这两个数。A 是 65a 是 97相差 32而 32 恰好是 2 的五次方。大小写之间只隔一个开关。把第 5 号开关拨上大写变小写拨下来小写变大写。printf(%c\n, A 32); // a加 32第 5 号开关拨上 printf(%c\n, e ^ 32); // E异或 32开关一拨大小写互换用位运算拨一个开关就完成一次大小写转换。第二章的魔法在第三章兑现。ASCII 的前 32 个码位没有字母全是控制字符那是电传打字机时代的遗迹。10 号叫换行LF纸卷上滚一行13 号叫回车CR打字头缩回行首。打字机要换到下一行行首得先缩打字头、再滚纸卷两个动作。电传打字机消亡五十年它的操作规程却保留在每一份 Windows 文本文件里Windows 的换行至今是 CR 加 LF 两个字符Unix 阵营只用一个 LF。第一章代码里那个 \n就是码位 10。一条 1963 年的规程穿过六十年还站在代码里该死的标准名单上它排得进前三。char 既然是整数就能参与运算A 1 是 B字母表在 C 语言里是一条等差数列。顺便预告一个有趣的事实。z 的下一个字符是花括号 {字母表在码表里不绕回头128 个码位排队排到底。这一练很有意思见本章练习第 4 题。四、时钟上的负数标签解决了怎么读的问题但是有一个一般人注意不到的“坑”还得拿出来说一下。负数。8 个开关只能摆出 0 到 255负号从哪来工程师们试过三套方案。原码把最高位当符号位0 正 1 负简洁却造出两个零正零与负零减法还要专门的减法器。反码让负数按位取反两个零还在。补码用表盘理解最直观零合成一个减法可以借加法器倒着拨硬件省下一半。1945 年冯·诺依曼的 EDVAC 报告就采用补码设计此后所有主流处理器统一补码。三套方案的胜负逻辑与第二章二进制的胜出如出一辙不是更优雅的赢是更省元件的赢。补码的直觉是一只时钟。n 位的整数类型就是一块 2 的 n 次方格的表盘8 位类型256 格。0 到 127 顺时针排满前半圈再往前拨落进后半圈。后半圈贴着负数贴纸-128 恰好在 0 的正对面然后是 -127、-126逆着排回去一直排到 -1。十点的钟拨过 12 点10 点加 4 小时得到 2 点。表盘不会空着表针只会落进下一圈。超界的数也一样不消失绕到对面。落点有一条公式。对 n 位类型数 x 超界后的落点按下式计算。(x 2^(n−1)) mod 2ⁿ − 2^(n−1)8 位存 128(128128) mod 256 − 128 0 − 128 −128恰好是 0 的正对面。16 位存 32768(3276832768) mod 65536 − 32768 −32768。同一块表65536 格的版本。考题最爱的超界求落点全部出自这一条公式。亲手开庭。手记第 12 题的冤案答案写 32768 照样成立真机却给出负数。先看它的 8 位缩样。#include stdio.h int main(void) { signed char c 127; // 8 位表盘的最大值 01111111 c c 1; // 顺时针拨一格落点在 0 的正对面 printf(%d\n, c); // 输出 -128 return 0; }这段代码里埋着两颗雷都是考试重点。第一颗为什么必须写c c 1存回去不能直接printf(%d\n, c 1)因为 C 语言有条规则叫整型提升char 参与运算时先升级成 int。c 1 是在 32 位的 int 盒子里算的128 安然无恙只有把 128 存回 8 位小盒绕圈才会发生。第二颗为什么用 signed char 不用 charchar 带不带符号由编译器自定常见的 x86 环境带符号ARM 环境常不带signed char 把带符号三个字写死在标签上。两颗雷同属标准只写下限家族标准留了余地雷就埋在余地里。现在提审 32768 原案分三层宣判。第一层当年为什么绕。int 出生在 16 位机器上最大 32767往 32768 迈一步65536 格的表盘把它送到 -32768对面落点公式原样命中。第二层今天为什么可能不绕。int 已宽到 32 位32768 连边都摸不着想在今天的机器上重现原案请用 short2 字节本章练习第 6 题供亲手复现。第三层标准怎么说。有符号整数的溢出是未定义行为标准不承诺绕到 -32768补码绕回是主流硬件的实际行为是各家都这么做不是标准保证这么做。答案的错就错在把某一台机器某一年的习惯写成了天条。至此手记第 12 题销案手记里那道三个答案的题还剩最后一层留在运算符那一章捅破。补码与类型备齐第二章的位运算从此可以在竞赛里放心施展。讲到哪里就练到哪里下面十例是竞赛一线最常用的技法先把兵器认全数组章之后逐一实战。【例4】取出第 k 位。(x k) 1先把第 k 位挪到最低位再与 1 相与。13 的二进制是 1101第 2 位是 1第 1 位是 0。上机验证printf(%d %d\n, (13 2) 1, (13 1) 1);输出 1 0。【例5】把第 k 位置 1。x | (1 k)按位或上一张只有第 k 位是 1 的掩码。把 13 的第 1 位置 1得 15。上机验证printf(%d\n, 13 | (1 1));输出 15。【例6】把第 k 位置 0。x ~(1 k)~ 生成一张只有第 k 位是 0、其余全是 1 的掩码~ 的原理就是本节补码。把 13 的第 3 位置 0得 5。上机验证printf(%d\n, 13 ~(1 3));输出 5。【例7】翻转第 k 位。x ^ (1 k)异或同一张掩码两次恰好复原。13 翻转第 1 位得 15再翻一次回到 13。上机验证printf(%d %d\n, 13 ^ (1 1), 15 ^ (1 1));输出 15 13。【例8】判断奇偶。x 1最低位是 1 即奇数是 0 即偶数比 % 2 直接。上机验证printf(%d %d\n, 13 1, 12 1);输出 1 0。【例9】判断 2 的整数次幂。2 的幂在二进制里只有一个 1减 1 之后后面全变 1两者相与必为 0。8 与 7 相与得 012 与 11 相与得 8。前提是 x 大于 0。上机验证printf(%d %d\n, 8 7, 12 11);输出 0 8。【例10】乘、除与取模的位运算版。13 2 得 52即 13×413 2 得 3即 13÷4 向下取整13 3 得 1即 13 对 4 取模取的是最低两位。上机验证printf(%d %d %d\n, 13 2, 13 2, 13 3);输出 52 3 1。【例11】lowbit抓最右侧的 1。x -x负数按补码理解本节刚讲完两者相与只剩最右侧那个 1 连同它后面的 0。12 的二进制 110012 与 -12 相与得 4。这是树状数组的核心零件竞赛里出场率极高。上机验证printf(%d\n, 12 -12);输出 4。【例12】异或消去成对。性质三条a ^ a 得 0a ^ 0 得 a异或满足交换与结合。于是 5 ^ 7 ^ 5 得 7成对的 5 相互抵消。一堆数里只有一个数单独出现、其余成对全体异或一遍剩下的就是它。这个题的正式赛题版需要数组第八章见。上机验证printf(%d\n, 5 ^ 7 ^ 5);输出 7。【例13】大数左移的坑。1 31 想要 21 亿多的数在 int 里却绕成 -2147483648落点公式原样命中这也是未定义行为主流平台实测如此。要 64 位结果把 1 写成 long long 再移。上机验证printf(%d %lld\n, 1 31, 1LL 31);输出 -2147483648 2147483648。五、小数说不准整数之外还有小数。C 语言的浮点类型有两个规格float4 字节约 7 位有效数字double8 字节约 16 位有效数字。日常计算首选 double输出格式符是 %f 与 %lf。先看案卷。printf(%.17f\n, 0.1 0.2); // 0.30000000000000004 printf(%.1f\n, 0.1 0.2); // 0.3舍到一位小数假装无事发生侦破从一条进制常识开始。十进制里1÷30.333……无限循环写不尽但在三进制里它就是干干净净的 0.1。反过来0.1 在十进制里干净在二进制里却是 0.0001100110011……无限循环。浮点类型的尾数空间有限double 约 53 个位装不下无限循环存进盒子那一刻就四舍五入了两个近似的数相加和还是近似落到第 17 位露出 4 的马脚。0.1 0.2 不等于 0.3不是哪个编译器的故障是有限位存储无限小数这套标尺的固有性质。给这套标尺立规矩的是 1985 年的 IEEE 754 标准主设计师是伯克利的威廉·卡亨William Kahan他后来获图灵奖获奖理由主要就是这项工作。标准把浮点数统一成科学计数法的二进制版符号、指数、尾数三段1.234×10² 的二进制亲戚。在此之前各家计算机的浮点格式互不兼容同一份代码换台机器结果就变IEEE 754 定于一尊才有了今天在哪台机器上算都一样错的公道。至于浮点加法内部如何对齐指数、如何舍入尾数那是计算机组成原理的地界本书点到为止留给往后的课程。实战守则一条。浮点数判等不用 用误差范围即判断两个浮点数的差是否小于一个极小的阈值。这道守则请直接写进习惯。竞赛速查表操作写法一句话说明取出第 k 位(x k) 1右移到最低位再与 1第 k 位置 1x (1 k)或上一张单位掩码第 k 位置 0x ~(1 k)与上一张反掩码翻转第 k 位x ^ (1 k)异或两次复原判断第 k 位x (1 k)非 0 即为 1判断奇偶x 11 奇 0 偶判断 2 的幂(x (x - 1)) 0前提 x 大于 0乘 2 的 k 次方x k左移即乘除 2 的 k 次方x k正数向下取整对 2 的 k 次方取模x ((1 k) - 1)取后 k 位取最低位的1x -x抓最右侧的 1消去最右侧的 1x x - 1循环起来即统计 1 的个数统计 1 的个数__builtin_popcount(x)GCC 内置竞赛直接用异或三性质a ^ a 为 0a ^ 0 为 a可交换结合消去成对元素无临时变量交换a ^ b; b ^ a; a ^ b;忌同一存储位置掩码表示集合mask (1 i) 一族状压 DP 基本件数组章之后展开速查表是给复习用的。第一次见面光看公式确实抽象记住三件事就好。这一节的例数全程只用一个 45二进制 101101是第二章短除法算出来的老朋友掩码的英文是 mask面具意思是 1 的位置露出来、0 的位置遮住每个操作都能画成两排灯的对齐游戏亮为 1灭为 0。下面把最有代表性的四个动作画出来。与运算是照着面具擦黑板。掩码 15 的 001111 高两位是 0不管 45 的高两位原来是什么一律擦成 0低四位是 1原样保留。表里判断第 k 位对 2 的 k 次方取模用的都是这套动作。异或最擅长找不同。经典的局面是一群盗贼两两配对只有一个落了单。把所有人的编号全部异或一遍成对的互相抵消归零落单的那个原样浮现。一行循环不用数组也不用排序表里异或三性质说的就是它。左移一位每个位的位权全体翻倍所以左移 k 位等于乘 2 的 k 次方右移则除。这是乘除 2 的幂最快的方式CPU 一条指令就完成。最难的一条画出来反而最简单x -x 只留下最右边的那个 1。它有专门的名字叫 lowbit是树状数组的地基数组章之后会大用特用。速查表之外还有三条坑。移位优先级低于加减法(1 k) - 1必须加括号少括号就先算减法负数右移高位补 1别拿 对负数做除法int 里 1 31 已经溢出64 位场景写 1LL k。语法卡本章语法规则速查。考试与写代码时的对照物。int score 98; // 整型配 %d short small 300; // 短整型配 %hd long long big 9007199254740993; // 长长整型配 %lld char letter A; // 字符%c 按码表读%d 按码位读 double x 0.1; // 双精度浮点用 %lfprintf 里 %f 亦可类型典型宽度常见取值范围格式符char1 字节-128 127是否带符号由编译器自定%c / %dsigned char1 字节-128 127符号写死%dshort2 字节-32768 32767%hdint4 字节-2147483648 2147483647%dlong4 或 8 字节随平台%ldlong long8 字节约 ±9.2×10¹⁸%lldfloat4 字节约 7 位有效数字%fdouble8 字节约 16 位有效数字%lf / %f四条规则。有符号整数溢出标准定性为未定义行为补码绕回是主流硬件的实际行为不是承诺。char 参与运算先升级为 int术语叫整型提升char 的符号性由编译器自定要写死符号用 signed char。浮点数判等不用 用误差范围。超界落点公式为 (x 2^(n−1)) mod 2ⁿ − 2^(n−1)n 为位宽。练习以下练习均在编程环境中直接运行验证。老纪律先写预测再运行机器是唯一裁判。运行printf(%d\n, A);与printf(%c\n, 65);各输出什么先写预测。用一条输出验证 a 与 A 的码位相差 32。把字符 e 转成大写输出至少写出两种写法减 32 与异或 32 都试。输出printf(%c\n, z 1);它会给出一个意想不到的字符。对照第三节解释为什么。把本章第四节的演示原样运行再把第一行改成signed char c 128;运行并记录输出用落点公式核对。short 版 32768 冤案short s 32767; s s 1;先用公式心算落点再输出验证。声明long long big 9007199254740993;并用 %lld 输出再试着把同一个数装进 int 盒子记录现象int 的上限约 21.4 亿。在同一程序里跑两行printf一行%.1f一行%.17f都输出 0.1 0.2记录两个结果并解释为什么保留一位小数时看起来没事。输出printf(%.17f\n, 1.0 / 3);看三分之一的真身。它精确吗综合声明一个 char 存自己姓名拼音的首字母输出它的码位%d与字符%c再输出该码位加 32 后按 %c 读的结果看看发生了什么。本章回顾类型是标签只写两件事一是占几个字节二是按什么规则读。数据完好而读法出错是大量离奇错误的共同源头。整数族谱五档char、short、int、long、long long标准只写下限不写死宽度long long 是 C99 收编的大数类型。char 本质是 8 位整数ASCII 码表是底册65 是 A97 是 a大小写只隔一个开关\n 是 1963 年电传打字机的操作规程。负数住在补码里n 位类型是一块 2ⁿ 格的表盘超界不消失绕到对面落点公式一条管全部。32768 冤案三层宣判当年绕今天可能不绕标准不保证。交换两数有三法第三方变量、求和赋值、位运算异或第三方变量最稳竞赛速查表是位运算的随身兵器。浮点是近似的艺术0.1 在二进制里无限循环double 约 53 位尾数装不下IEEE 754 统一了标尺浮点判等用误差范围。下一章是输入与输出。程序到目前为止只会自说自话scanf 登场让机器听见声音。而它那个古怪的 就是第二章说过的地址。参考文献本章史料经 AI 查证与人工复核主要来源如下。C 整数类型宽度「只写下限」ISO/IEC 9899C 标准各版本对 char/short/int/long/long long 最小宽度的规定C99 新增 long longISO/IEC 9899:1999。Microsoft 对 long long 的支持进度与 LLP64 数据模型64 位 Windows 上 long 保持 32 位Microsoft Learn 官方文档Visual C 历史版本说明与数据模型页。ASCIIANSI X3.4-1963 初版发布1967 年修订补齐小写字母控制字符LF10、CR13为电传打字机操作规程的遗产Windows 换行 CRLF 与 Unix LF 的分野为公认史实。补码的胜出First Draft of a Report on the EDVAC1945即采用补码设计原码/反码/补码三方案的取舍为计算机组成原理通识零唯一、减法借加法器实现。有符号整数溢出为未定义行为ISO/IEC 9899C 标准6.5 表达式条款补码绕回是主流硬件的实际行为而非标准承诺。IEEE 754-1985 浮点标准与 William Kahan 的主导工作IEEE 标准 754-1985Kahan 获 1989 年图灵奖ACM 官方获奖理由含浮点数值标准的贡献。0.1 的二进制表示无限循环0.000110011…与 0.10.2≠0.3IEEE 754 双精度约 53 位尾数的固有舍入任何采用该标准的系统均可复现。 听故事学语言 · 第三章 类型的诞生
听故事学语言 · 第三章 类型的诞生本章回答四个问题。类型是什么char 为什么本质上是整数一个数为什么会超界变成负数小数为什么算不准序章埋下的给 B 加上类型在本章展开全貌。32768 冤案本章开庭。一、类型是标签第二章立过一条论数据的本质其实就是内存里面的存放空间。内存是一排排编了号的字节盒子但上一章只说了一半。一盒 8 个开关读作 01100101它是十进制 101还是字母 e盒子没有任何提示两种读法都对也都不对。决定怎么读的是贴在盒子上的标签。C 语言把它叫作类型。一张类型标签只写两件事。一是多大占几个字节二是怎么读按什么规则解读这些开关。同一盒字节贴 int 标签就按整数读贴 char 标签就按字符读。字节一个都没变变的是读法。这个认识是本章的地基。程序里大量的离奇错误数据本身完好无损坏的是读法。第二章 1TB 变 931GB 的冤案正是同族字节一个没少尺子换了一把。类型也不是凭空设计的。序章讲过1972 年PDP-11 的字节寻址逼着里奇给 B 加上类型char 为字节而生int 为计算而设。本章把这张标签的里里外外讲全。二、整数族谱与一条下限规则C 语言的整数类型是一张族谱先给零基础读者一张速览表。类型典型宽度常见取值范围用途一句话char1 字节-128 127小整数与字符第三节的主角short2 字节-32768 32767省内存的小整数int4 字节约 ±21.4 亿日常计算的主力long4 或 8 字节随平台与平台纠缠的类型long long8 字节约 ±922 亿亿给大数准备的类型这张表要先读出一条反常的规则。典型宽度不等于保证宽度。C 标准从不写死 int 是几个字节只规定下限int 至少 16 位long long 至少 64 位。第一章语法卡里那个奇怪的 -32767正是在这条规则下露出的马脚标准连 int 的最小范围都只敢从 -32767 保起。为什么不敢写死因为宽度随硬件一步步变大。int 出生在 16 位的 PDP-11 上2 个字节最大 32767记住这个数字本章第四节的开庭主角。后来 32 位计算机普及int 变成 4 个字节今天的家用计算机上int 的常见范围是正负 21.4 亿。同一份代码在两代机器上读出两个宽度所以标准只敢写下限写死的那部分交给了历史。族谱里最新的一页属于 long long。二十世纪九十年代64 位计算登场各家编译器各造各的大数类型微软自造了__int64。1999 年C99 标准把 long long 正式收编至少 64 位能数到 922 亿亿。有意思的是微软的反应它拖到 2010 年前后的 Visual Studio 才承认这个标准类型直到今天64 位 Windows 上 long 依然是 4 个字节与 Unix 阵营各走各路。又一个该死的标准大数类型也有派系。变量的声明写法从本章起正式启用。int score 98; // 声明一个 int 盒子贴上 int 标签放进 98 char initial D; // char 盒子放一个字符 long long big 9007199254740993; // long long 盒子放一个大数 printf(%lld\n, big); // 大数的专用格式符 %lld变量就是带标签的盒子。盒子里那几个字节就放在内存的某个地址上。第二章的地址第三章的标签从此合流。变量的第一件本事是交换两个盒子里的数。讲到哪里就练到哪里三种方法一条比一条妙。【例1】交换两个数第三方变量法。int a 13, b 7;借一个临时变量 tt a; a b; b t;交换完成。这是最稳的写法竞赛与工程通用。【例2】交换两个数求和赋值法。不用第三个变量a a b; b a - b; a a - b;走一遍a 里存的是和 20b 先取走差得到 13a 再减去新的 b 得到 7。数学上无懈可击但 ab 一旦超出 int 的上限就会出错超界的后果本章第四节专门开庭。两数相加可能超 21.4 亿时老老实实用第三方变量。【例3】交换两个数位运算异或法。a ^ b; b ^ a; a ^ b;三步交换一个临时变量都没用。原理是异或的可逆性同一个数异或两次就复原三步下来恰好各归各位。警告一条若 a 与 b 是同一个存储位置第一步a ^ a直接把它清成 0交换变成销毁日后在数组里遇到自己和自己交换时要当心。三、伪装成字符的整数char 是族谱里最特殊的成员它只有 1 个字节标签上却写着字符。可一旦翻开底册char 是一位伪装成字符的整数。底册叫ASCIIAmerican Standard Code for Information Interchange美国信息交换标准代码。1963 年美国标准协会发布了这份编码表7 个位128 个码位1967 年修订时补齐了小写字母。它规定 65 号是 A97 号是 a48 号是字符 0。注意最后这条。字符 0 与数字 0 是两位住户字符 0 存的是码位 48数字 0 存的是数值 0。char 与整数可以互相换算两条输出当场验证。printf(%d\n, A); // 65%d 拿整数读法读 char printf(%c\n, 65); // A%c 拿字符读法读整数同一个字节%d 按整数读%c 按码表读。char 之所以本质上是整数因为它骨子里就是一个 8 位整数只是平时按码表解读。这张码表里藏着第二章位运算的第一次实战。看这两个数。A 是 65a 是 97相差 32而 32 恰好是 2 的五次方。大小写之间只隔一个开关。把第 5 号开关拨上大写变小写拨下来小写变大写。printf(%c\n, A 32); // a加 32第 5 号开关拨上 printf(%c\n, e ^ 32); // E异或 32开关一拨大小写互换用位运算拨一个开关就完成一次大小写转换。第二章的魔法在第三章兑现。ASCII 的前 32 个码位没有字母全是控制字符那是电传打字机时代的遗迹。10 号叫换行LF纸卷上滚一行13 号叫回车CR打字头缩回行首。打字机要换到下一行行首得先缩打字头、再滚纸卷两个动作。电传打字机消亡五十年它的操作规程却保留在每一份 Windows 文本文件里Windows 的换行至今是 CR 加 LF 两个字符Unix 阵营只用一个 LF。第一章代码里那个 \n就是码位 10。一条 1963 年的规程穿过六十年还站在代码里该死的标准名单上它排得进前三。char 既然是整数就能参与运算A 1 是 B字母表在 C 语言里是一条等差数列。顺便预告一个有趣的事实。z 的下一个字符是花括号 {字母表在码表里不绕回头128 个码位排队排到底。这一练很有意思见本章练习第 4 题。四、时钟上的负数标签解决了怎么读的问题但是有一个一般人注意不到的“坑”还得拿出来说一下。负数。8 个开关只能摆出 0 到 255负号从哪来工程师们试过三套方案。原码把最高位当符号位0 正 1 负简洁却造出两个零正零与负零减法还要专门的减法器。反码让负数按位取反两个零还在。补码用表盘理解最直观零合成一个减法可以借加法器倒着拨硬件省下一半。1945 年冯·诺依曼的 EDVAC 报告就采用补码设计此后所有主流处理器统一补码。三套方案的胜负逻辑与第二章二进制的胜出如出一辙不是更优雅的赢是更省元件的赢。补码的直觉是一只时钟。n 位的整数类型就是一块 2 的 n 次方格的表盘8 位类型256 格。0 到 127 顺时针排满前半圈再往前拨落进后半圈。后半圈贴着负数贴纸-128 恰好在 0 的正对面然后是 -127、-126逆着排回去一直排到 -1。十点的钟拨过 12 点10 点加 4 小时得到 2 点。表盘不会空着表针只会落进下一圈。超界的数也一样不消失绕到对面。落点有一条公式。对 n 位类型数 x 超界后的落点按下式计算。(x 2^(n−1)) mod 2ⁿ − 2^(n−1)8 位存 128(128128) mod 256 − 128 0 − 128 −128恰好是 0 的正对面。16 位存 32768(3276832768) mod 65536 − 32768 −32768。同一块表65536 格的版本。考题最爱的超界求落点全部出自这一条公式。亲手开庭。手记第 12 题的冤案答案写 32768 照样成立真机却给出负数。先看它的 8 位缩样。#include stdio.h int main(void) { signed char c 127; // 8 位表盘的最大值 01111111 c c 1; // 顺时针拨一格落点在 0 的正对面 printf(%d\n, c); // 输出 -128 return 0; }这段代码里埋着两颗雷都是考试重点。第一颗为什么必须写c c 1存回去不能直接printf(%d\n, c 1)因为 C 语言有条规则叫整型提升char 参与运算时先升级成 int。c 1 是在 32 位的 int 盒子里算的128 安然无恙只有把 128 存回 8 位小盒绕圈才会发生。第二颗为什么用 signed char 不用 charchar 带不带符号由编译器自定常见的 x86 环境带符号ARM 环境常不带signed char 把带符号三个字写死在标签上。两颗雷同属标准只写下限家族标准留了余地雷就埋在余地里。现在提审 32768 原案分三层宣判。第一层当年为什么绕。int 出生在 16 位机器上最大 32767往 32768 迈一步65536 格的表盘把它送到 -32768对面落点公式原样命中。第二层今天为什么可能不绕。int 已宽到 32 位32768 连边都摸不着想在今天的机器上重现原案请用 short2 字节本章练习第 6 题供亲手复现。第三层标准怎么说。有符号整数的溢出是未定义行为标准不承诺绕到 -32768补码绕回是主流硬件的实际行为是各家都这么做不是标准保证这么做。答案的错就错在把某一台机器某一年的习惯写成了天条。至此手记第 12 题销案手记里那道三个答案的题还剩最后一层留在运算符那一章捅破。补码与类型备齐第二章的位运算从此可以在竞赛里放心施展。讲到哪里就练到哪里下面十例是竞赛一线最常用的技法先把兵器认全数组章之后逐一实战。【例4】取出第 k 位。(x k) 1先把第 k 位挪到最低位再与 1 相与。13 的二进制是 1101第 2 位是 1第 1 位是 0。上机验证printf(%d %d\n, (13 2) 1, (13 1) 1);输出 1 0。【例5】把第 k 位置 1。x | (1 k)按位或上一张只有第 k 位是 1 的掩码。把 13 的第 1 位置 1得 15。上机验证printf(%d\n, 13 | (1 1));输出 15。【例6】把第 k 位置 0。x ~(1 k)~ 生成一张只有第 k 位是 0、其余全是 1 的掩码~ 的原理就是本节补码。把 13 的第 3 位置 0得 5。上机验证printf(%d\n, 13 ~(1 3));输出 5。【例7】翻转第 k 位。x ^ (1 k)异或同一张掩码两次恰好复原。13 翻转第 1 位得 15再翻一次回到 13。上机验证printf(%d %d\n, 13 ^ (1 1), 15 ^ (1 1));输出 15 13。【例8】判断奇偶。x 1最低位是 1 即奇数是 0 即偶数比 % 2 直接。上机验证printf(%d %d\n, 13 1, 12 1);输出 1 0。【例9】判断 2 的整数次幂。2 的幂在二进制里只有一个 1减 1 之后后面全变 1两者相与必为 0。8 与 7 相与得 012 与 11 相与得 8。前提是 x 大于 0。上机验证printf(%d %d\n, 8 7, 12 11);输出 0 8。【例10】乘、除与取模的位运算版。13 2 得 52即 13×413 2 得 3即 13÷4 向下取整13 3 得 1即 13 对 4 取模取的是最低两位。上机验证printf(%d %d %d\n, 13 2, 13 2, 13 3);输出 52 3 1。【例11】lowbit抓最右侧的 1。x -x负数按补码理解本节刚讲完两者相与只剩最右侧那个 1 连同它后面的 0。12 的二进制 110012 与 -12 相与得 4。这是树状数组的核心零件竞赛里出场率极高。上机验证printf(%d\n, 12 -12);输出 4。【例12】异或消去成对。性质三条a ^ a 得 0a ^ 0 得 a异或满足交换与结合。于是 5 ^ 7 ^ 5 得 7成对的 5 相互抵消。一堆数里只有一个数单独出现、其余成对全体异或一遍剩下的就是它。这个题的正式赛题版需要数组第八章见。上机验证printf(%d\n, 5 ^ 7 ^ 5);输出 7。【例13】大数左移的坑。1 31 想要 21 亿多的数在 int 里却绕成 -2147483648落点公式原样命中这也是未定义行为主流平台实测如此。要 64 位结果把 1 写成 long long 再移。上机验证printf(%d %lld\n, 1 31, 1LL 31);输出 -2147483648 2147483648。五、小数说不准整数之外还有小数。C 语言的浮点类型有两个规格float4 字节约 7 位有效数字double8 字节约 16 位有效数字。日常计算首选 double输出格式符是 %f 与 %lf。先看案卷。printf(%.17f\n, 0.1 0.2); // 0.30000000000000004 printf(%.1f\n, 0.1 0.2); // 0.3舍到一位小数假装无事发生侦破从一条进制常识开始。十进制里1÷30.333……无限循环写不尽但在三进制里它就是干干净净的 0.1。反过来0.1 在十进制里干净在二进制里却是 0.0001100110011……无限循环。浮点类型的尾数空间有限double 约 53 个位装不下无限循环存进盒子那一刻就四舍五入了两个近似的数相加和还是近似落到第 17 位露出 4 的马脚。0.1 0.2 不等于 0.3不是哪个编译器的故障是有限位存储无限小数这套标尺的固有性质。给这套标尺立规矩的是 1985 年的 IEEE 754 标准主设计师是伯克利的威廉·卡亨William Kahan他后来获图灵奖获奖理由主要就是这项工作。标准把浮点数统一成科学计数法的二进制版符号、指数、尾数三段1.234×10² 的二进制亲戚。在此之前各家计算机的浮点格式互不兼容同一份代码换台机器结果就变IEEE 754 定于一尊才有了今天在哪台机器上算都一样错的公道。至于浮点加法内部如何对齐指数、如何舍入尾数那是计算机组成原理的地界本书点到为止留给往后的课程。实战守则一条。浮点数判等不用 用误差范围即判断两个浮点数的差是否小于一个极小的阈值。这道守则请直接写进习惯。竞赛速查表操作写法一句话说明取出第 k 位(x k) 1右移到最低位再与 1第 k 位置 1x (1 k)或上一张单位掩码第 k 位置 0x ~(1 k)与上一张反掩码翻转第 k 位x ^ (1 k)异或两次复原判断第 k 位x (1 k)非 0 即为 1判断奇偶x 11 奇 0 偶判断 2 的幂(x (x - 1)) 0前提 x 大于 0乘 2 的 k 次方x k左移即乘除 2 的 k 次方x k正数向下取整对 2 的 k 次方取模x ((1 k) - 1)取后 k 位取最低位的1x -x抓最右侧的 1消去最右侧的 1x x - 1循环起来即统计 1 的个数统计 1 的个数__builtin_popcount(x)GCC 内置竞赛直接用异或三性质a ^ a 为 0a ^ 0 为 a可交换结合消去成对元素无临时变量交换a ^ b; b ^ a; a ^ b;忌同一存储位置掩码表示集合mask (1 i) 一族状压 DP 基本件数组章之后展开速查表是给复习用的。第一次见面光看公式确实抽象记住三件事就好。这一节的例数全程只用一个 45二进制 101101是第二章短除法算出来的老朋友掩码的英文是 mask面具意思是 1 的位置露出来、0 的位置遮住每个操作都能画成两排灯的对齐游戏亮为 1灭为 0。下面把最有代表性的四个动作画出来。与运算是照着面具擦黑板。掩码 15 的 001111 高两位是 0不管 45 的高两位原来是什么一律擦成 0低四位是 1原样保留。表里判断第 k 位对 2 的 k 次方取模用的都是这套动作。异或最擅长找不同。经典的局面是一群盗贼两两配对只有一个落了单。把所有人的编号全部异或一遍成对的互相抵消归零落单的那个原样浮现。一行循环不用数组也不用排序表里异或三性质说的就是它。左移一位每个位的位权全体翻倍所以左移 k 位等于乘 2 的 k 次方右移则除。这是乘除 2 的幂最快的方式CPU 一条指令就完成。最难的一条画出来反而最简单x -x 只留下最右边的那个 1。它有专门的名字叫 lowbit是树状数组的地基数组章之后会大用特用。速查表之外还有三条坑。移位优先级低于加减法(1 k) - 1必须加括号少括号就先算减法负数右移高位补 1别拿 对负数做除法int 里 1 31 已经溢出64 位场景写 1LL k。语法卡本章语法规则速查。考试与写代码时的对照物。int score 98; // 整型配 %d short small 300; // 短整型配 %hd long long big 9007199254740993; // 长长整型配 %lld char letter A; // 字符%c 按码表读%d 按码位读 double x 0.1; // 双精度浮点用 %lfprintf 里 %f 亦可类型典型宽度常见取值范围格式符char1 字节-128 127是否带符号由编译器自定%c / %dsigned char1 字节-128 127符号写死%dshort2 字节-32768 32767%hdint4 字节-2147483648 2147483647%dlong4 或 8 字节随平台%ldlong long8 字节约 ±9.2×10¹⁸%lldfloat4 字节约 7 位有效数字%fdouble8 字节约 16 位有效数字%lf / %f四条规则。有符号整数溢出标准定性为未定义行为补码绕回是主流硬件的实际行为不是承诺。char 参与运算先升级为 int术语叫整型提升char 的符号性由编译器自定要写死符号用 signed char。浮点数判等不用 用误差范围。超界落点公式为 (x 2^(n−1)) mod 2ⁿ − 2^(n−1)n 为位宽。练习以下练习均在编程环境中直接运行验证。老纪律先写预测再运行机器是唯一裁判。运行printf(%d\n, A);与printf(%c\n, 65);各输出什么先写预测。用一条输出验证 a 与 A 的码位相差 32。把字符 e 转成大写输出至少写出两种写法减 32 与异或 32 都试。输出printf(%c\n, z 1);它会给出一个意想不到的字符。对照第三节解释为什么。把本章第四节的演示原样运行再把第一行改成signed char c 128;运行并记录输出用落点公式核对。short 版 32768 冤案short s 32767; s s 1;先用公式心算落点再输出验证。声明long long big 9007199254740993;并用 %lld 输出再试着把同一个数装进 int 盒子记录现象int 的上限约 21.4 亿。在同一程序里跑两行printf一行%.1f一行%.17f都输出 0.1 0.2记录两个结果并解释为什么保留一位小数时看起来没事。输出printf(%.17f\n, 1.0 / 3);看三分之一的真身。它精确吗综合声明一个 char 存自己姓名拼音的首字母输出它的码位%d与字符%c再输出该码位加 32 后按 %c 读的结果看看发生了什么。本章回顾类型是标签只写两件事一是占几个字节二是按什么规则读。数据完好而读法出错是大量离奇错误的共同源头。整数族谱五档char、short、int、long、long long标准只写下限不写死宽度long long 是 C99 收编的大数类型。char 本质是 8 位整数ASCII 码表是底册65 是 A97 是 a大小写只隔一个开关\n 是 1963 年电传打字机的操作规程。负数住在补码里n 位类型是一块 2ⁿ 格的表盘超界不消失绕到对面落点公式一条管全部。32768 冤案三层宣判当年绕今天可能不绕标准不保证。交换两数有三法第三方变量、求和赋值、位运算异或第三方变量最稳竞赛速查表是位运算的随身兵器。浮点是近似的艺术0.1 在二进制里无限循环double 约 53 位尾数装不下IEEE 754 统一了标尺浮点判等用误差范围。下一章是输入与输出。程序到目前为止只会自说自话scanf 登场让机器听见声音。而它那个古怪的 就是第二章说过的地址。参考文献本章史料经 AI 查证与人工复核主要来源如下。C 整数类型宽度「只写下限」ISO/IEC 9899C 标准各版本对 char/short/int/long/long long 最小宽度的规定C99 新增 long longISO/IEC 9899:1999。Microsoft 对 long long 的支持进度与 LLP64 数据模型64 位 Windows 上 long 保持 32 位Microsoft Learn 官方文档Visual C 历史版本说明与数据模型页。ASCIIANSI X3.4-1963 初版发布1967 年修订补齐小写字母控制字符LF10、CR13为电传打字机操作规程的遗产Windows 换行 CRLF 与 Unix LF 的分野为公认史实。补码的胜出First Draft of a Report on the EDVAC1945即采用补码设计原码/反码/补码三方案的取舍为计算机组成原理通识零唯一、减法借加法器实现。有符号整数溢出为未定义行为ISO/IEC 9899C 标准6.5 表达式条款补码绕回是主流硬件的实际行为而非标准承诺。IEEE 754-1985 浮点标准与 William Kahan 的主导工作IEEE 标准 754-1985Kahan 获 1989 年图灵奖ACM 官方获奖理由含浮点数值标准的贡献。0.1 的二进制表示无限循环0.000110011…与 0.10.2≠0.3IEEE 754 双精度约 53 位尾数的固有舍入任何采用该标准的系统均可复现。