计算机科学概论（微课版）· 第3章 数据表示与运算 · 教学课件

高等学校计算机专业核心课程精品系列教材计算机科学概论（微课版）第3章数据表示与运算数制转换·机器数·逻辑运算·移位与算术运算·硬件实现三千万士兵举旗传递的0与1，如何变成计算机里的数、逻辑与电路？本章从《三体》的人列计算机出发，回答“计算机如何表示数据、如何完成运算”这一根本问题。《三体》中的人列计算机：白旗为0、黑旗为1教材图3-1，见教材第31页LEARNINGGOALS学习目标与知识导图第3章知识结构导图（教材章首）本章学习目标❶理解进位计数制的基数与位权，熟练完成二进制、八进制、十进制、十六进制之间的相互转换；❷掌握机器数与原码、反码、补码的定义与特点，理解计算机采用补码的原因；❸掌握与、或、非、异或等逻辑运算及逻辑移位、算术移位；❹理解补码加减、浮点数运算与补码一位乘法的实现思路。能力落点：从半加器、全加器到四位串行加法器／运算器，看清“逻辑门→数字电路→ALU”的硬件实现路径，理解加减乘除最终都归结为加法与移位。计算机科学概论（微课版）｜第3章数据表示与运算02CONTENTS本章目录3.1数制——数据的表示常用数制与数制转换｜机器数与原码、反码、补码｜定点数与浮点数3.2逻辑运算情景案例：诚实国与说谎国｜与、或、非、异或｜位模式层面的逻辑运算3.3移位运算逻辑移位（无符号数）｜算术移位（有符号数）｜左移乘2、右移除23.4算术运算补码定点加减｜浮点数加减五步骤｜补码一位乘法：乘法化为加法与移位3.5计算机硬件实现数字电路与逻辑门｜半加器、全加器｜四位串行加法器与加减运算器章末3.6本章小结｜3.7拓展知识：八/十六进制的意义与difflogic｜3.8课后习题计算机科学概论（微课版）｜第3章数据表示与运算033.1数制——数据的表示从《三体》人列计算机说起：为什么是二进制图3-1《三体》中的人列计算机：士兵举白旗表示0、黑旗表示1（教材第31页）《三体》中，三千万士兵组成“人列计算机”，每人举白旗（0）或黑旗（1），通过旗语传递信号完成运算。为什么两种颜色就够了？因为二进制只有0、1两个数码，最容易用物理器件的两种稳定状态（开/关、高/低电平）可靠表示。进位计数制的两要素·基数R：可用数码的个数（二进制R=2，十进制R=10）·位权：数码所处位置决定的权重，第i位的权为R的i次幂同一个数，多种写法：(101)10=(1100101)2=(145)8=(65)16记法两种：下标法(101)10；字母法D/B/Q/H，如843D、1001B、70Q、95FH十进制早在商代就已使用，是人类的天然选择；而计算机内部一切数据——数、字符、图像、指令——最终都统一表示为0和1组成的二进制位串。计算机科学概论（微课版）｜第3章数据表示与运算043.1.1常用数制与数制转换数制转换（一）：与十进制互转①其他进制→十进制：按权展开各位数码乘以其位权后求和。(1010.01)2=1×23+1×21+1×2-2=(10.25)10(27.16)8=2×81+7×80+1×8-1+6×8-2≈(23.219)10(5E.24)16≈(94.141)10②十进制→其他进制整数部分：除基取余，余数倒序排列。(22)10=(10110)2(143)10=(217)8=(8F)16小数部分：乘基取整，整数正序排列。(0.625)10=(0.101)2(0.23)10≈(0.165)8课堂提示：整数与小数要分别转换后再拼接；乘基取整可能永不结束，此时按精度要求截取——十进制小数未必能精确表示为有限位二进制小数。数制基数可用数码进位规则示例十进制D100~9逢十进一95二进制B20、1逢二进一1001B八进制Q80~7逢八进一70Q十六进制H160~9、A~F逢十六进一5FH表3-1四种常用数制对比（教材第32页）计算机科学概论（微课版）｜第3章数据表示与运算053.1.1常用数制与数制转换数制转换（二）：二进制↔八进制↔十六进制分组依据：23=8，24=161位八进制↔3位二进制；1位十六进制↔4位二进制。方法：以小数点为界向两侧分组，不足补0，逐组改写。二进制→八进制（3位一组）(1100.1011)2→001100.101100→14.54=(14.54)8二进制→十六进制（4位一组）(101110.001)2→00101110.0010→2E.2=(2E.2)16八进制↔十六进制：没有直接对应关系，借二进制“搭桥”间接转换。反向转换同样成立：每个八进制位展成3位、每个十六进制位展成4位二进制，再去掉首尾多余的0。计算机科学概论（微课版）｜第3章数据表示与运算063.1.2机器数与原码、反码、补码符号数码化：原码、反码、补码机器数：把符号“数字化”后在机器内表示的数（最高位作符号位，0正1负）；真值：机器数对应的带符号实际数值。例：+1011001→01011001，−1011001→11011001。编码定义（负数以X₂=−1011001为例）运算特点0的表示原码符号位+绝对值[X₂]原=11011001表示简单，但加减需区分符号、需两套电路不唯一（+0/−0）反码负数＝原码除符号位外逐位取反[X₂]反=10100110只需加法器，但最高位进位要回加到最低位不唯一补码负数＝反码末位+1[X₂]补=10100111只需加法器，进位直接舍弃，应用最广唯一补码加法示例：14+(−7)[14]补=01110，[−7]补=11001→01110+11001=100111，最高位进位舍弃，得00111=+7✓为什么计算机偏爱补码？符号位与数值位可以统一处理，减法转化为加法，硬件只需一套加法器即可完成有符号加减运算——这正是3.4节算术运算和3.5节硬件实现的基础。计算机科学概论（微课版）｜第3章数据表示与运算073.1.3定点数与浮点数小数点怎么办：定点数与浮点数定点数：小数点位置固定·定点整数：小数点约定在最低位之后·定点小数：纯小数，小数点约定在符号位之后、数值最高位之前·表示范围有限，但运算简单浮点数：N=M×RE·R：基数（通常为2，隐含约定）·M：尾数，纯小数，决定精度·E：阶码，纯整数，决定表示范围；小数点随阶码“浮动”图3-2浮点数的一般格式：阶符+阶码+数符（尾符）+尾数（教材第35页）示例：−3.25的浮点表示−3.25=−0.1101×2+10；取阶码3位、尾数5位（均用补码）：阶码010，尾数10011，拼接得01010011——阶码与尾数各带符号位，合起来就是一个完整的机器浮点数。计算机科学概论（微课版）｜第3章数据表示与运算083.2逻辑运算情景案例：诚实国与说谎国《三体》中，冯·诺依曼向秦始皇展示“与门”：两名士兵各举一面旗作输入，第三人根据规则举旗作输出，一千万个这样的门部件组成人列计算机系统。逻辑运算（布尔运算）处理的正是“真/假”两种逻辑值。岔路口之问诚实国人永远说真话，说谎国人永远说假话。岔路口一人（国籍未知），只问一句：“你来自诚实国、这条路通向说谎国，这两个问题的回答是相同的吗？”回答“是”→走这条路；回答“否”→走另一条。A来自诚实国B通向说谎国C回答相同D前一问回答E最终回答00110011011010011111表3-2诚实国与说谎国问题真值表（教材第38页）规律：最终回答E与“这条路通向说谎国”B的真值完全相同——一句精心设计的复合问句，把“对方是否说谎”这个未知因素抵消掉了。计算机科学概论（微课版）｜第3章数据表示与运算093.2.3位层面的逻辑运算与、或、非：三种基本逻辑运算与运算ANDY=A·B（串联电路）：两个输入全为1，输出才为1。或运算ORY=A+B（并联电路）：两个输入全为0，输出才为0。非运算NOTY=X̄（一元运算）：输入取反，0变1、1变0。图3-3/3-4/3-5与、或、非运算的电路类比（教材第38~39页）xy与x·y或x+y异或x⊕y非¬x000001010111100110111100表3-4四种逻辑运算真值表：异或——输入相同得0、不同得1（教材第39页）计算机科学概论（微课版）｜第3章数据表示与运算103.2.4模式层面的逻辑运算按位运算：两个n位模式逐位对应把逻辑运算推广到整个二进制位串：对两个n位模式的对应位分别做同一运算，得到n位结果。下面以10010101与11011100为例（NOT为一元运算）。AND10010101∧11011100=10010100图3-6按位与：对应位全1结果才为1OR10010101∨11011100=11011101图3-7按位或：对应位全0结果才为0XOR10010101⊕11011100=01001001图3-8按位异或：对应位不同结果为1NOT¬10010101=01101010图3-9按位非：每一位0、1互换应用一瞥：按位与可用于“掩码”提取特定位；异或可用于加密与校验（相同数异或两次还原）。计算机科学概论（微课版）｜第3章数据表示与运算113.3移位运算从十进制移位到逻辑移位图3-10十进制整数相乘竖式：103×245=25235，乘数每左移一位相当于×10（教材第40页）十进制中我们早就会“移位”：小数点右移一位×10，左移一位÷10。二进制同理：左移一位相当于×2，右移一位相当于÷2。移位运算广泛用于位操作、加密、数据压缩与编解码。对二进制数，按是否考虑符号位，分为逻辑移位与算术移位两类。逻辑移位：把数看作无符号位串，所有位一起移动。逻辑左移图3-11最高位移入进位标志CF，最低位补0：01110101→11101010（教材第40页）逻辑右移图3-12最高位补0，最低位丢弃：10110101→01011010（教材第41页）计算机科学概论（微课版）｜第3章数据表示与运算123.3.2算术移位算术移位：保住符号位的×2与÷2算术左移（相当于×2）图3-13规则与逻辑左移相同：最高位移出、最低位补0，数值翻倍（教材第41页）算术右移（相当于÷2）图3-14最高位用自身复制填补、最低位丢弃：10110101→11011010，符号保持不变（教材第41页）对比项逻辑移位算术移位适用对象无符号位串（位模式）有符号数（符号位不动）左移全体左移、末位补0规则相同，相当于×2（注意溢出）右移最高位补0最高位复制符号位填补，相当于÷2注意：十进制移位没有符号位概念，二进制移位必须考虑符号位——算术左移与逻辑左移操作一致但意义不同；算术右移与逻辑右移则结果完全不同。计算机科学概论（微课版）｜第3章数据表示与运算133.4.1定点数加减运算补码加减：减法化为加法核心公式（mod2n+1）：[X₁]补+[X₂]补=[X₁+X₂]补[X₁−X₂]补=[X₁]补+[−X₂]补例①22+(−17)[22]补=010110，[−17]补=101111010110+101111=1000101进位舍弃→000101=+5✓例②(+1010)−(+0101)[X₁]补=01010，[−X₂]补=1101101010+11011=100101进位舍弃→00101=+0101✓求[−X]补的快捷方法（由[X]补直接得到）从右向左扫描：第一个1及其右侧各位原样输出，其左侧各位（含符号位）全部取反。如[X₂]补=00101→扫描得[−X₂]补=11011。意义：加、减法统一为加法，硬件只需一个加法器即可完成有符号数的加减运算——这正是补码“硬件友好”的直接体现。计算机科学概论（微课版）｜第3章数据表示与运算143.4.2浮点数加减运算浮点数加减：规格化与五步骤规格化与变形补码·规格化：尾数最高数值位为有效值（原码S.1X…X；补码00.1X…X或11.0X…X）·变形补码：双符号位，00正、11负·结果符号位出现01或10→溢出。例：010010+010100=100110误判；变形补码0100110立即可检出左规与右规·左规格化：结果为00.0X或11.1X时，尾数左移、阶码−1，可多次·右规格化：结果为01.X或10.X时，尾数右移一位、阶码+1，只一次·阶码随之增减，保持数值不变浮点加减五步骤①对阶：求阶差，阶码小的尾数右移、向大阶看齐②尾数加减：按定点补码加减法运算③规格化：左规或右规④舍入：处理移出位⑤溢出处理：阶码溢出才算溢出例：X₁=2010×0.1101，X₂=2100×(−0.1001)。对阶后尾数相减、规格化，得Y=2011×(−0.10111)。计算机科学概论（微课版）｜第3章数据表示与运算153.4.3乘除运算补码一位乘法：乘法=加法+移位乘法和除法都可以分解为“加法+移位”的序列。补码一位乘法从乘数末位开始，每次比较相邻两位yn+1、yn，按下表决定加什么，然后整体右移一位。yₙ₊₁与yₙ的关系操作含义yₙ₊₁=yₙ（00或11）加0，右移一位部分积不变yₙ₊₁yₙ=10加[X]补，右移一位减权→加被乘数yₙ₊₁yₙ=01加[−X]补，右移一位加权→减被乘数示例：(+11)2×(+10)2的补码一位乘法[X]补=011，[Y]补=010，[−X]补=101；乘数末尾补辅助位0，共做n+1步，最后一步只加不移位。结果[X×Y]补=00110，即+1102=+6，对应十进制3×2=6✓要点回顾：乘积取2n+1位；整个过程中符号位与数值位一起参与运算，无需单独处理符号。除法同样可化为加减与移位（补码不恢复余数除法等）。至此，四则运算在计算机内部全部归结为加法器+移位器就能完成的任务。计算机科学概论（微课版）｜第3章数据表示与运算163.5计算机硬件实现数字电路：运算的物理载体算盘也是一种“硬件实现”。现代计算机中，运算器（ALU）是CPU的核心部件，它由数字电路构成。数字信号的自变量与因变量都是离散的；处理数字信号的数字（逻辑）电路以二进制为基础，分为组合逻辑与时序逻辑两大类。图3-15计算机硬件组成：运算器+控制器=CPU，加存储器为主机，输入/输出为外部设备，经系统总线相连（教材第44页）组合逻辑电路输出只取决于当前输入，与历史无关——类比密码锁：按下正确组合立即开锁。加法器、译码器都属此类。时序逻辑电路输出与过去的输入也有关——类比转盘式保险柜：同样的数字，顺序错了也开不了。寄存器、计数器都属此类。图3-16两类“锁”的类比：密码锁（组合逻辑，只看当前输入）与转盘保险柜（时序逻辑，还看输入顺序）（教材第44页）。数字系统用逻辑代数L={K,+,·,‾,0,1}描述：变量只取0/1，运算只有与、或、非三种基本形式。计算机科学概论（微课版）｜第3章数据表示与运算173.5.1数字电路与逻辑门逻辑门：从基本门到复合门三种基本逻辑门·或门：符号“≥1”，任一为1输出1·与门：符号“&”，全为1输出1·非门：符号“1○”，输入取反——任何复杂数字电路都可由它们搭出图3-17基本逻辑门符号（教材第45页）复合逻辑门基本门的组合：与非门、或非门、与或非门、异或门等，一个封装完成复合功能。图3-18异或门，符号“=1”：仅当输入恰有一个1时输出1承上启下3.2节的与、或、非、异或是“数学定义”，本节的门电路是“物理实现”——接下来就能看到：仅用异或门和与门，就能拼出二进制加法的基本单元。计算机科学概论（微课版）｜第3章数据表示与运算183.5.2加法器的硬件实现半加器与全加器半加器：不考虑低位进位ABSC0000011010101101表3-5/图3-19半加器真值表与电路（教材第45~46页）全加器：连低位进位一起加和：Si=Ai⊕Bi⊕Ci-1进位：Ci=(Ai⊕Bi)Ci-1+AiBi三输入（两个加数位+低位进位），两输出（本位和+向高位进位），真值表见表3-6。设计要点半加：S=A⊕B，C=AB——一个异或门加一个与门即可实现；全加器可由两个半加器+一个或门组成。加法器是算术运算器的基本单元，其他运算都建立在它之上。计算机科学概论（微课版）｜第3章数据表示与运算193.5.2加法器的硬件实现四位串行加法器：全加器的级联图3-21全加器的符号表示（FA）：Ai、Bi、Ci-1输入，Si、Ci输出（教材第46页）从1位到n位把四个全加器级联：低位FA的进位输出C接高位FA的进位输入，最低位进位输入接地（0），最高位进位输出即进位标志。n位加法器同理——这就是“串行（行波）加法器”。图3-22四位串行加法器：四个全加器低位进位接高位，逐位“行波”传递（教材第46页）计算机科学概论（微课版）｜第3章数据表示与运算203.5.2加法器的硬件实现加减一体：四位串行运算器图3-23四位串行运算器：FA的B输入端各接一个异或门，由控制符P统一控制（教材第47页；原书校样顶部输入字母缺失，为校样自带问题）P=0→加法异或门另一输入为0时，B原样通过，且最低位进位输入为0：电路就是普通的四位加法器，计算A+B。P=1→减法异或门另一输入为1时，B逐位取反，同时P接入最低位进位“+1”——正好是求[−B]补，于是A+(−B)实现减法。计算机科学概论（微课版）｜第3章数据表示与运算213.6本章小结小结：数据如何表示，运算如何实现01数制与转换基数+位权是进位计数制的两要素；与十进制互转用“按权展开/除基取余/乘基取整”，二、八、十六之间按3位、4位分组互换。02机器数：补码是计算机的实际选择原码、反码、补码三种表示中，补码让符号位与数值位统一处理、减法化为加法、0的表示唯一。03移位：逻辑移位与算术移位逻辑移位面向无符号位串；算术移位面向有符号数——左移×2、右移÷2，算术右移用符号位复制填补，十进制移位则无符号位概念。04算术运算：归结为“加法+移位”补码加减只需加法器；浮点加减按对阶、尾数加减、规格化、舍入、溢出处理五步进行，阶码溢出才是溢出；乘除同样化为加法与移位。0