第三课《计算机为什么只认识0和1——二进制、进制转换与补码》这一课非常重要因为它实际上是一个“桥梁”计算机基础 → 二进制 → C → 位运算 → 初赛计算题后面很多 CSP-J 题目都会用到今天的知识。本课主要覆盖进制转换、 带符号数表示、BCD码以及 C 中的进制表示和位运算。大纲明确指出数值信息在计算机内部用二进制表示并系统介绍了二、八、十、十六进制及其转换。一、先问同学们一个问题我们上一节课讲到CPU执行程序。那么老师写int a 10; int b 20; int c a b;CPU真的认识int a b 吗答案是不认识。CPU最终处理的是0和1组成的信息。于是问题来了为什么偏偏是0和1二、计算机为什么喜欢0和1我们先不讲复杂的电子学。假设有一个开关。只有两种状态关闭 打开我们可以规定关闭 0 打开 1于是一个开关 ↓ 0 或 1如果有两个开关00 01 10 11一共有4种状态。三个开关000 001 010 011 100 101 110 111一共有8种状态。所以n个二进制位可以表示 2ⁿ 种状态。这是今天第一个非常重要的数学规律。三、什么叫“位”计算机里面经常看到bit它就是比特、位一个 bit 只有两种可能0 1例如101101里面有6个 bit。所以1 bit → 2种状态 2 bit → 4种状态 3 bit → 8种状态 4 bit → 16种状态 8 bit → 256种状态四、一个非常重要的公式如果有n 个 bit能够表示2ⁿ 种不同状态例如8位2⁸ 256所以8位无符号数可以表示0 255这也正好解释了我们上一课讲到的IPv4每一段为什么是0255因为一段是8 bit2⁸ 256种可能编号从0开始0 255五、什么是进制我们平时最熟悉的是十进制。因为我们有10个手指所以从小就习惯0 1 2 3 4 5 6 7 8 9一共10个基本数字。所以叫十进制进制的本质就是一个数字系统到底有多少个基本符号。讲义把进制定义为如果数制采用 R 个基本符号0~R-1就称为基 R 数制。六、四种最重要的进制进制基数使用的数字二进制20、1八进制807十进制1009十六进制1609、AF讲义给出的定义也是这四种进制并指出十六进制中的 AF 分别对应十进制的1015。七、为什么十六进制有A、B、C因为十六进制需要16个符号。但是我们只有09只有10个。怎么办继续使用字母A 10 B 11 C 12 D 13 E 14 F 15所以十六进制 0 1 2 3 4 5 6 7 8 9 A B C D E F八、先学最重要的二进制转十进制例如1011₂不要把它看成一个普通的“1011”。我们使用按权展开讲义也是采用“按权展开”的方法进行 R 进制到十进制的转换。九、什么叫“权”十进制1234实际上是1×1000 2×100 3×10 4×1也就是1×10³ 2×10² 3×10¹ 4×10⁰为什么因为每向左移动一位权就乘10。十、二进制也是一样只不过十进制的底数是10。而二进制的底数是2。所以1011₂从右往左1 0 1 1 ↓ ↓ ↓ ↓ 2³ 2² 2¹ 2⁰因此1011₂ 1×2³ 0×2² 1×2¹ 1×2⁰也就是 8 0 2 1 11所以1011₂ 11₁₀十一、再来一个110101₂展开1×2⁵ 1×2⁴ 0×2³ 1×2² 0×2¹ 1×2⁰计算32 16 0 4 0 1 53所以110101₂ 53₁₀十二、给同学们一个特别好用的“二进制位置表”以后做题可以直接写位 32 16 8 4 2 1 ↓ ↓ ↓ ↓ ↓ 2⁴ 2³ 2² 2¹ 2⁰例如101101对应32 16 8 4 2 1 1 0 1 1 0 1所以32 8 4 1 45十三、十进制转二进制反过来45怎么变成二进制讲义规定十进制整数转换为 R 进制整数除 R 取余法。对于二进制就是不断除2取余。十四、45除2取余45 ÷ 2 22 …… 1 22 ÷ 2 11 …… 0 11 ÷ 2 5 …… 1 5 ÷ 2 2 …… 1 2 ÷ 2 1 …… 0 1 ÷ 2 0 …… 1把余数从下往上读得到101101所以45₁₀ 101101₂十五、为什么余数要从下往上读这是同学们经常问的问题。因为第一次除2得到的是最低位。最后一次得到的是最高位。所以最后得到 ↑ 最高位 第一次得到 ↓ 最低位因此要倒过来读。十六、二进制小数怎么办整数会了小数也不能怕。例如0.625₁₀转换为二进制。讲义给出的方法是小数部分不断乘 R取整数部分。对于二进制就是乘2取整。十七、0.625 × 20.625 × 2 1.25取整数部分1留下0.25继续0.25 × 2 0.5取0继续0.5 × 2 1.0取1所以0.625₁₀ 0.101₂讲义中的例子正是0.625₁₀ 0.101₂。十八、这里总结两个转换口诀十进制整数 → R进制除R取余倒着读。十进制小数 → R进制乘R取整顺着读。这是初赛非常重要的两个方法。十九、八进制有什么意义为什么还要学习八进制因为1个八进制数字 3个二进制位例如101₂就是5₈因为101₂ 5₁₀二十、十六进制更重要因为1个十六进制数字 4个二进制位例如1010₂对应A₁₆因为1010₂ 10₁₀ A₁₆讲义明确指出每位八进制数相当于3位二进制每位十六进制数相当于4位二进制。二十一、二进制转十六进制最神奇的方法例如1011010₂从右边开始每4位一组。不够4位怎么办左边补0。所以0101 1010分别对应0101 5 1010 A因此1011010₂ 5A₁₆讲义也给出了类似的分组转换方法。二十二、十六进制转二进制反过来更简单。例如F7₁₆每个十六进制数字直接变成4位二进制F → 1111 7 → 0111所以F7₁₆ 11110111₂讲义给出的例子也是F7₁₆ 11110111₂。二十三、为什么十六进制特别适合计算机因为1个十六进制数字 4个二进制位所以1010 1100 0110可以非常容易写成AC6比一长串101011000110更容易阅读。所以程序员经常看到0x1A 0xFF 0xABC二十四、C中怎么写十六进制讲义中给出了int b 0x1A;这里0x表示后面的数字是十六进制。例如int a 0x1A; cout a;输出26因为1A₁₆ 1×16 10 26二十五、C中八进制怎么写讲义中也给了例子int a 010;这里以0开头表示八进制。所以010不是十进制10。而是10₈ 8₁₀这个在初赛选择题中非常容易设置陷阱。二十六、课堂“陷阱题”问int x 010; cout x;输出什么很多孩子会回答10错因为010是八进制。所以10₈ 8₁₀答案8二十七、进入今天第二个大主题原码、反码、补码现在我们已经知道计算机用二进制表示数据。可是又来了一个问题如果是5很好办。但是-5怎么办计算机也需要表示负数。于是就出现了原码 反码 补码二十八、原码最容易理解假设用8位表示一个数。规定第一位表示符号。0 → 正数 1 → 负数其余位表示数值。讲义对原码的定义正是符号位0表示正数1表示负数其余位表示数值部分。二十九、例如 55的二进制101补成7位0000101前面加符号位0 0000101所以8位原码00000101三十、-5的原码先写5 ↓ 0000101因为是负数符号位 1所以10000101因此-5的8位原码 10000101三十一、反码是什么对于正数反码和原码一样。对于负数符号位保持11其余位全部0 ↔ 1讲义给出的规则也是负数符号位不变其余位0、1互换。三十二、-5的反码原码10000101符号位不变1后面全部取反01111010所以-5的反码 11111010注意这里要非常小心。正确写法是原码 10000101 反码 11111010三十三、补码最重要为什么要搞这么复杂因为补码主要是为了方便计算机进行运算。讲义也明确指出补码的主要作用是方便计算机运算。三十四、负数补码怎么求记一个最简单的方法负数补码 反码 1例如-5原码10000101反码11111010加111111011所以-5的补码 11111011三十五、把三种码放在一起以-5为例原码 10000101 反码 11111010 补码 11111011孩子一定要记住正数原码 反码 补码负数反码 原码除符号位外全部取反补码 反码 1这个规律来自讲义的总结。三十六、为什么补码能让计算更方便我们做一个非常有趣的例子。假设5 (-5)应该等于0如果直接设计特殊的负数运算规则会比较麻烦。而使用补码可以把减法转换为加法。计算机就可以使用统一的加法器处理。这就是补码非常重要的原因。三十七、补码初赛题型讲义中给出了一个典型题在8位二进制补码中10101011表示的数是多少我们一起做。最高位1说明这是负数。三十八、补码转回真正的数对于负数补码 → 反码减1或者更常见补码 → 取反加1再加负号例如10101011先减110101010再取反11010101它的数值部分1010101对应64 16 4 1 85所以10101011₂8位补码 -85这也与讲义给出的答案一致。三十九、为什么补码没有两个“0”这是一个非常好的进阶问题。原码和反码都存在0 -0但是补码只有一个0。讲义也明确写出[0]补 [-0]补 00…0这也是补码相比原码、反码的一个重要优势。四十、第三个小知识BCD码这一部分不用讲得太深。BCDBinary-Coded Decimal中文二进制编码的十进制数讲义称其为BCD码也叫8421码。它使用4位二进制表示一个十进制数字09。四十一、BCD最容易犯的错误例如十进制39BCD不是100111而是3 → 0011 9 → 1001所以39 ↓ 0011 1001讲义给出的例子正是39的 BCD 码为00111001。四十二、BCD和普通二进制的区别这是非常值得讲清楚的。普通二进制39₁₀转换成二进制100111₂BCD把每一个十进制数字分别编码3 → 0011 9 → 1001得到00111001所以BCD不是把整个数字直接转换成二进制。而是一个十进制数字一个十进制数字地编码。四十三、现在进入 C位运算这一部分非常重要因为它开始真正连接初赛 C程序阅读讲义列出了 | 等整数位运算。四十四、按位与例如5 12先转换5 0101 12 1100逐位进行 AND0101 1100 ---- 0100所以5 12 4讲义也用类似的二进制逐位运算解释了。四十五、按位或|规则只要有一个1结果就是1。例如0101 1100 ---- 1101所以5 | 12 1101₂ 13讲义同样列出了|运算。四十六、左移例如5 15101左移1位1010也就是10所以5 1 10讲义明确将左移1位解释为二进制整体向左移动一位并指出在相应简单情形下相当于乘2。四十七、右移例如5 1101 ↓ 10所以5 1 2讲义也给出了这一例子并指出在相应简单情形下相当于除2。四十八、一个非常重要的口诀对于正整数、简单情况 1 ≈ ×2 1 ≈ ÷2例如3 2相当于3 × 2² 12又例如20 2相当于20 ÷ 2² 5不过这里要提醒孩子这个“乘2、除2”的口诀是帮助理解的简化规则。遇到负数、有符号类型、溢出等情况不能机械套用。四十九、初赛经典位运算题讲义给了一个非常经典的问题int CountBit(int x) { int ret 0; while (x) { ret; _________; } return ret; }目标统计一个非负整数二进制中1的个数。选项A. x 1 B. x x - 1 C. x | x 1 D. x 1答案B讲义给出的答案也是 B。五十、为什么x x-1能消掉一个1这是今天最值得让优秀孩子思考的地方。例如x 12二进制1100那么x - 1 1011进行1100 1011 ---- 1000原来的1100最右边那个1被消掉了。所以x x - 1;每执行一次消掉一个二进制中的1。因此while(x) { ret; x x - 1; }循环多少次恰好就是二进制中1的个数。这是一道非常典型的初赛位运算思想题。五十一、今天的知识地图现在把第三课全部串起来二进制 │ ┌─────────────┼─────────────┐ ↓ ↓ ↓ 进制转换 有符号数 位运算 │ │ │ ┌────┼────┐ 原码/反码/补码 │ ↓ ↓ ↓ │ 二 八 十六 │ │ │ │ └────→ 转换 ←────────────────────┘ C │ ┌────────┼────────┐ ↓ ↓ ↓ | 五十二、这一课 CSP-J 必背清单建议最后只让孩子记下面这些。① 二进制只有0、1两个数字。② n位二进制可以表示2ⁿ种状态。③ 二进制 → 十进制按权展开。④ 十进制整数 → R进制除R取余倒着读。⑤ 十进制小数 → R进制乘R取整顺着读。⑥ 八进制每一位对应3个二进制位。⑦ 十六进制每一位对应4个二进制位。⑧ 十六进制A10 B11 C12 D13 E14 F15⑨ 原码第一位表示符号。⑩ 反码负数符号位不变其余位取反。⑪ 补码负数补码 反码 1。⑫ 正数原码 反码 补码。⑬ BCD一个十进制数字用4位二进制编码。⑭ C进制010 // 八进制 0x1A // 十六进制⑮ 位运算 按位与 | 按位或 左移 右移⑯ 经典技巧x x - 1;消掉最低位的一个1。五十三、课后练习同学们要动笔算第一组进制转换1.101101₂ ?₁₀答案452.45₁₀ ?₂答案101101₂3.1011010₂ ?₈答案132₈4.1011010₂ ?₁₆答案5A₁₆这些转换方法和答案形式与讲义中的对应练习一致。五十四、第二组补码5.求-2的8位原码反码补码答案原码10000010 反码11111101 补码11111110这也是讲义给出的标准练习答案。6.8位补码11111111表示多少答案-1这是孩子必须熟练掌握的典型补码。五十五、第三组C位运算7.cout (5 12);答案48.cout (5 | 12);答案139.cout (5 1);答案1010.cout (20 2);答案5五十六、最后给同学们留一个“挑战题”不要马上告诉答案。int x 13; int ans 0; while (x) { ans; x x - 1; } cout ans;问最后输出多少先让孩子把13写成二进制1101有几个13个。所以ans 3这个小程序它把十进制 → 二进制 → 位运算 → 程序阅读全部连起来了。五十七、这一课真正要达到的目标第一目标是建立三个核心能力能力一看到二进制不害怕看到10110101知道“我可以按权展开。”能力二看到十六进制知道怎么处理看到A7知道A10并且每一位可以直接转换成4位二进制。能力三看到C位运算能够“翻译”看到x y x | y x 1 x 1 x x - 1脑子里马上出现二进制。这才是这节课最重要的成果。三课串起来以后现在第一单元前三课已经形成了一条非常清晰的主线第一课 计算机硬件 CPU / 内存 / 硬盘 ↓ 第二课 软件与网络 OS / 编译器 / IP / DNS / HTTP ↓ 第三课 计算机内部的数据 二进制 / 进制转换 / 补码 / 位运算 ↓ 第四课 程序到底有多快 变量 / 数据类型 / 运算 / 时间复杂度第三课尤其重要同学们会真正感觉到“原来那些看起来奇怪的0和1、十六进制、补码、、其实和我每天写的C程序是一回事。” CSP-J 初赛（以满分为目标）：第三课《计算机为什么只认识0和1？——二进制、进制转换与补码》
第三课《计算机为什么只认识0和1——二进制、进制转换与补码》这一课非常重要因为它实际上是一个“桥梁”计算机基础 → 二进制 → C → 位运算 → 初赛计算题后面很多 CSP-J 题目都会用到今天的知识。本课主要覆盖进制转换、 带符号数表示、BCD码以及 C 中的进制表示和位运算。大纲明确指出数值信息在计算机内部用二进制表示并系统介绍了二、八、十、十六进制及其转换。一、先问同学们一个问题我们上一节课讲到CPU执行程序。那么老师写int a 10; int b 20; int c a b;CPU真的认识int a b 吗答案是不认识。CPU最终处理的是0和1组成的信息。于是问题来了为什么偏偏是0和1二、计算机为什么喜欢0和1我们先不讲复杂的电子学。假设有一个开关。只有两种状态关闭 打开我们可以规定关闭 0 打开 1于是一个开关 ↓ 0 或 1如果有两个开关00 01 10 11一共有4种状态。三个开关000 001 010 011 100 101 110 111一共有8种状态。所以n个二进制位可以表示 2ⁿ 种状态。这是今天第一个非常重要的数学规律。三、什么叫“位”计算机里面经常看到bit它就是比特、位一个 bit 只有两种可能0 1例如101101里面有6个 bit。所以1 bit → 2种状态 2 bit → 4种状态 3 bit → 8种状态 4 bit → 16种状态 8 bit → 256种状态四、一个非常重要的公式如果有n 个 bit能够表示2ⁿ 种不同状态例如8位2⁸ 256所以8位无符号数可以表示0 255这也正好解释了我们上一课讲到的IPv4每一段为什么是0255因为一段是8 bit2⁸ 256种可能编号从0开始0 255五、什么是进制我们平时最熟悉的是十进制。因为我们有10个手指所以从小就习惯0 1 2 3 4 5 6 7 8 9一共10个基本数字。所以叫十进制进制的本质就是一个数字系统到底有多少个基本符号。讲义把进制定义为如果数制采用 R 个基本符号0~R-1就称为基 R 数制。六、四种最重要的进制进制基数使用的数字二进制20、1八进制807十进制1009十六进制1609、AF讲义给出的定义也是这四种进制并指出十六进制中的 AF 分别对应十进制的1015。七、为什么十六进制有A、B、C因为十六进制需要16个符号。但是我们只有09只有10个。怎么办继续使用字母A 10 B 11 C 12 D 13 E 14 F 15所以十六进制 0 1 2 3 4 5 6 7 8 9 A B C D E F八、先学最重要的二进制转十进制例如1011₂不要把它看成一个普通的“1011”。我们使用按权展开讲义也是采用“按权展开”的方法进行 R 进制到十进制的转换。九、什么叫“权”十进制1234实际上是1×1000 2×100 3×10 4×1也就是1×10³ 2×10² 3×10¹ 4×10⁰为什么因为每向左移动一位权就乘10。十、二进制也是一样只不过十进制的底数是10。而二进制的底数是2。所以1011₂从右往左1 0 1 1 ↓ ↓ ↓ ↓ 2³ 2² 2¹ 2⁰因此1011₂ 1×2³ 0×2² 1×2¹ 1×2⁰也就是 8 0 2 1 11所以1011₂ 11₁₀十一、再来一个110101₂展开1×2⁵ 1×2⁴ 0×2³ 1×2² 0×2¹ 1×2⁰计算32 16 0 4 0 1 53所以110101₂ 53₁₀十二、给同学们一个特别好用的“二进制位置表”以后做题可以直接写位 32 16 8 4 2 1 ↓ ↓ ↓ ↓ ↓ 2⁴ 2³ 2² 2¹ 2⁰例如101101对应32 16 8 4 2 1 1 0 1 1 0 1所以32 8 4 1 45十三、十进制转二进制反过来45怎么变成二进制讲义规定十进制整数转换为 R 进制整数除 R 取余法。对于二进制就是不断除2取余。十四、45除2取余45 ÷ 2 22 …… 1 22 ÷ 2 11 …… 0 11 ÷ 2 5 …… 1 5 ÷ 2 2 …… 1 2 ÷ 2 1 …… 0 1 ÷ 2 0 …… 1把余数从下往上读得到101101所以45₁₀ 101101₂十五、为什么余数要从下往上读这是同学们经常问的问题。因为第一次除2得到的是最低位。最后一次得到的是最高位。所以最后得到 ↑ 最高位 第一次得到 ↓ 最低位因此要倒过来读。十六、二进制小数怎么办整数会了小数也不能怕。例如0.625₁₀转换为二进制。讲义给出的方法是小数部分不断乘 R取整数部分。对于二进制就是乘2取整。十七、0.625 × 20.625 × 2 1.25取整数部分1留下0.25继续0.25 × 2 0.5取0继续0.5 × 2 1.0取1所以0.625₁₀ 0.101₂讲义中的例子正是0.625₁₀ 0.101₂。十八、这里总结两个转换口诀十进制整数 → R进制除R取余倒着读。十进制小数 → R进制乘R取整顺着读。这是初赛非常重要的两个方法。十九、八进制有什么意义为什么还要学习八进制因为1个八进制数字 3个二进制位例如101₂就是5₈因为101₂ 5₁₀二十、十六进制更重要因为1个十六进制数字 4个二进制位例如1010₂对应A₁₆因为1010₂ 10₁₀ A₁₆讲义明确指出每位八进制数相当于3位二进制每位十六进制数相当于4位二进制。二十一、二进制转十六进制最神奇的方法例如1011010₂从右边开始每4位一组。不够4位怎么办左边补0。所以0101 1010分别对应0101 5 1010 A因此1011010₂ 5A₁₆讲义也给出了类似的分组转换方法。二十二、十六进制转二进制反过来更简单。例如F7₁₆每个十六进制数字直接变成4位二进制F → 1111 7 → 0111所以F7₁₆ 11110111₂讲义给出的例子也是F7₁₆ 11110111₂。二十三、为什么十六进制特别适合计算机因为1个十六进制数字 4个二进制位所以1010 1100 0110可以非常容易写成AC6比一长串101011000110更容易阅读。所以程序员经常看到0x1A 0xFF 0xABC二十四、C中怎么写十六进制讲义中给出了int b 0x1A;这里0x表示后面的数字是十六进制。例如int a 0x1A; cout a;输出26因为1A₁₆ 1×16 10 26二十五、C中八进制怎么写讲义中也给了例子int a 010;这里以0开头表示八进制。所以010不是十进制10。而是10₈ 8₁₀这个在初赛选择题中非常容易设置陷阱。二十六、课堂“陷阱题”问int x 010; cout x;输出什么很多孩子会回答10错因为010是八进制。所以10₈ 8₁₀答案8二十七、进入今天第二个大主题原码、反码、补码现在我们已经知道计算机用二进制表示数据。可是又来了一个问题如果是5很好办。但是-5怎么办计算机也需要表示负数。于是就出现了原码 反码 补码二十八、原码最容易理解假设用8位表示一个数。规定第一位表示符号。0 → 正数 1 → 负数其余位表示数值。讲义对原码的定义正是符号位0表示正数1表示负数其余位表示数值部分。二十九、例如 55的二进制101补成7位0000101前面加符号位0 0000101所以8位原码00000101三十、-5的原码先写5 ↓ 0000101因为是负数符号位 1所以10000101因此-5的8位原码 10000101三十一、反码是什么对于正数反码和原码一样。对于负数符号位保持11其余位全部0 ↔ 1讲义给出的规则也是负数符号位不变其余位0、1互换。三十二、-5的反码原码10000101符号位不变1后面全部取反01111010所以-5的反码 11111010注意这里要非常小心。正确写法是原码 10000101 反码 11111010三十三、补码最重要为什么要搞这么复杂因为补码主要是为了方便计算机进行运算。讲义也明确指出补码的主要作用是方便计算机运算。三十四、负数补码怎么求记一个最简单的方法负数补码 反码 1例如-5原码10000101反码11111010加111111011所以-5的补码 11111011三十五、把三种码放在一起以-5为例原码 10000101 反码 11111010 补码 11111011孩子一定要记住正数原码 反码 补码负数反码 原码除符号位外全部取反补码 反码 1这个规律来自讲义的总结。三十六、为什么补码能让计算更方便我们做一个非常有趣的例子。假设5 (-5)应该等于0如果直接设计特殊的负数运算规则会比较麻烦。而使用补码可以把减法转换为加法。计算机就可以使用统一的加法器处理。这就是补码非常重要的原因。三十七、补码初赛题型讲义中给出了一个典型题在8位二进制补码中10101011表示的数是多少我们一起做。最高位1说明这是负数。三十八、补码转回真正的数对于负数补码 → 反码减1或者更常见补码 → 取反加1再加负号例如10101011先减110101010再取反11010101它的数值部分1010101对应64 16 4 1 85所以10101011₂8位补码 -85这也与讲义给出的答案一致。三十九、为什么补码没有两个“0”这是一个非常好的进阶问题。原码和反码都存在0 -0但是补码只有一个0。讲义也明确写出[0]补 [-0]补 00…0这也是补码相比原码、反码的一个重要优势。四十、第三个小知识BCD码这一部分不用讲得太深。BCDBinary-Coded Decimal中文二进制编码的十进制数讲义称其为BCD码也叫8421码。它使用4位二进制表示一个十进制数字09。四十一、BCD最容易犯的错误例如十进制39BCD不是100111而是3 → 0011 9 → 1001所以39 ↓ 0011 1001讲义给出的例子正是39的 BCD 码为00111001。四十二、BCD和普通二进制的区别这是非常值得讲清楚的。普通二进制39₁₀转换成二进制100111₂BCD把每一个十进制数字分别编码3 → 0011 9 → 1001得到00111001所以BCD不是把整个数字直接转换成二进制。而是一个十进制数字一个十进制数字地编码。四十三、现在进入 C位运算这一部分非常重要因为它开始真正连接初赛 C程序阅读讲义列出了 | 等整数位运算。四十四、按位与例如5 12先转换5 0101 12 1100逐位进行 AND0101 1100 ---- 0100所以5 12 4讲义也用类似的二进制逐位运算解释了。四十五、按位或|规则只要有一个1结果就是1。例如0101 1100 ---- 1101所以5 | 12 1101₂ 13讲义同样列出了|运算。四十六、左移例如5 15101左移1位1010也就是10所以5 1 10讲义明确将左移1位解释为二进制整体向左移动一位并指出在相应简单情形下相当于乘2。四十七、右移例如5 1101 ↓ 10所以5 1 2讲义也给出了这一例子并指出在相应简单情形下相当于除2。四十八、一个非常重要的口诀对于正整数、简单情况 1 ≈ ×2 1 ≈ ÷2例如3 2相当于3 × 2² 12又例如20 2相当于20 ÷ 2² 5不过这里要提醒孩子这个“乘2、除2”的口诀是帮助理解的简化规则。遇到负数、有符号类型、溢出等情况不能机械套用。四十九、初赛经典位运算题讲义给了一个非常经典的问题int CountBit(int x) { int ret 0; while (x) { ret; _________; } return ret; }目标统计一个非负整数二进制中1的个数。选项A. x 1 B. x x - 1 C. x | x 1 D. x 1答案B讲义给出的答案也是 B。五十、为什么x x-1能消掉一个1这是今天最值得让优秀孩子思考的地方。例如x 12二进制1100那么x - 1 1011进行1100 1011 ---- 1000原来的1100最右边那个1被消掉了。所以x x - 1;每执行一次消掉一个二进制中的1。因此while(x) { ret; x x - 1; }循环多少次恰好就是二进制中1的个数。这是一道非常典型的初赛位运算思想题。五十一、今天的知识地图现在把第三课全部串起来二进制 │ ┌─────────────┼─────────────┐ ↓ ↓ ↓ 进制转换 有符号数 位运算 │ │ │ ┌────┼────┐ 原码/反码/补码 │ ↓ ↓ ↓ │ 二 八 十六 │ │ │ │ └────→ 转换 ←────────────────────┘ C │ ┌────────┼────────┐ ↓ ↓ ↓ | 五十二、这一课 CSP-J 必背清单建议最后只让孩子记下面这些。① 二进制只有0、1两个数字。② n位二进制可以表示2ⁿ种状态。③ 二进制 → 十进制按权展开。④ 十进制整数 → R进制除R取余倒着读。⑤ 十进制小数 → R进制乘R取整顺着读。⑥ 八进制每一位对应3个二进制位。⑦ 十六进制每一位对应4个二进制位。⑧ 十六进制A10 B11 C12 D13 E14 F15⑨ 原码第一位表示符号。⑩ 反码负数符号位不变其余位取反。⑪ 补码负数补码 反码 1。⑫ 正数原码 反码 补码。⑬ BCD一个十进制数字用4位二进制编码。⑭ C进制010 // 八进制 0x1A // 十六进制⑮ 位运算 按位与 | 按位或 左移 右移⑯ 经典技巧x x - 1;消掉最低位的一个1。五十三、课后练习同学们要动笔算第一组进制转换1.101101₂ ?₁₀答案452.45₁₀ ?₂答案101101₂3.1011010₂ ?₈答案132₈4.1011010₂ ?₁₆答案5A₁₆这些转换方法和答案形式与讲义中的对应练习一致。五十四、第二组补码5.求-2的8位原码反码补码答案原码10000010 反码11111101 补码11111110这也是讲义给出的标准练习答案。6.8位补码11111111表示多少答案-1这是孩子必须熟练掌握的典型补码。五十五、第三组C位运算7.cout (5 12);答案48.cout (5 | 12);答案139.cout (5 1);答案1010.cout (20 2);答案5五十六、最后给同学们留一个“挑战题”不要马上告诉答案。int x 13; int ans 0; while (x) { ans; x x - 1; } cout ans;问最后输出多少先让孩子把13写成二进制1101有几个13个。所以ans 3这个小程序它把十进制 → 二进制 → 位运算 → 程序阅读全部连起来了。五十七、这一课真正要达到的目标第一目标是建立三个核心能力能力一看到二进制不害怕看到10110101知道“我可以按权展开。”能力二看到十六进制知道怎么处理看到A7知道A10并且每一位可以直接转换成4位二进制。能力三看到C位运算能够“翻译”看到x y x | y x 1 x 1 x x - 1脑子里马上出现二进制。这才是这节课最重要的成果。三课串起来以后现在第一单元前三课已经形成了一条非常清晰的主线第一课 计算机硬件 CPU / 内存 / 硬盘 ↓ 第二课 软件与网络 OS / 编译器 / IP / DNS / HTTP ↓ 第三课 计算机内部的数据 二进制 / 进制转换 / 补码 / 位运算 ↓ 第四课 程序到底有多快 变量 / 数据类型 / 运算 / 时间复杂度第三课尤其重要同学们会真正感觉到“原来那些看起来奇怪的0和1、十六进制、补码、、其实和我每天写的C程序是一回事。”