本课程主要介绍高级语言程序中的数据类型及其运算、语句和过程调用等是如何在计算机系统中实现的。主要包含三个主题：（1）表示。不同数据类型（如带符号整数、无符号整数、浮点数、数组、结构等）数据在寄存器或存储器中的表示和存储；指令的格式、编码及其在存储器中的存储；存储地址（指针）的表示。（2）转换。高级语言程序中的过程（函数调用）、循环、选择等语句与机器级代码之间的对应关系。（3）链接。多个可重定位目标文件如何链接生成可执行目标文件并加载到系统中。 通过本课程的学习，使学习者能从程序员角度认识计算机系统，能够建立高级语言程序、ISA、OS、编译器、链接器等之间的相互关联，对指令在硬件上的执行过程和指令的底层硬件执行机制有一定的认识和理解，从而增强在程序调试、性能提升、程序移植和健壮性等方面的能力，并为后续的“计算机组成与设计”、“操作系统”、“编译原理”、“计算机体系结构”等课程打下坚实基础。 学完本课程后，学习者将对以下问题有比较深刻的认识，并能解决相关实际问题。 ----程序中处理的数据在机器中如何表示和运算？ ----程序中各类控制语句对应的机器级代码结构是怎样的？ ----多个程序模块是如何链接起来形成可执行目标文件的？ ----机器级代码及构成机器级代码的指令是如何在机器上执行的？
W4-1 整数乘法运算
Loading...
來自 Nanjing University 的課程
计算机系统基础（一） ：程序的表示、转换与链接
46 個評分
從本節課中
WEEK4
基于运算电路基础，介绍高级语言中的整数乘除运算与底层实现之间的关系；然后介绍浮点数的运算，特别是浮点运算中的精度问题。
與講師見面
袁春风教授
计算机科学与技术系
[音乐] 在前面介绍的C语言程序涉及的
运算中，我们主要介绍了各类算术运算的实现
前一节课介绍了整数加减运算的实现 本讲主要介绍整数乘运算的实现
通常在高级语言中
两个n位整数相乘，得到的结果通常也是n位的
整数，也就是说两个n位数相乘的结果是2n位
但是我们一般只取2n位乘积当中的
低n位乘积，比如说在C语言当中
因为要求参加运算的两个操作数的类型和结果的类型必须一致
两个int型的数据乘出来的结果也应该是int型的
如果不一致的话呢应该先转化为一致的数据类型再进行计算
比如说这个函数当中，x、 y呢都是int型的
z返回值也是int型的 在这个高级语言对应的机器级代码当中
乘运算x*y通常是转换成乘法
指令，在乘法指令执行的时候，也就是这个硬件 执行的时候，实际上在乘法的运算电路当中
是能够得到64位的乘积的，但是呢 最后我们只把低32位赋给z这个变量
然后返回，对于整数的乘运算，在机器内部
x²不一定大于等于0，虽然现实世界当中
x不管是正数还是负数，它的平方一定是大于等于0的
在机器内部它是不一定的 如果x是带符号整数的话，x²有可能是个负数
那如果x是一个浮点数，比如说是float型的、 double型的
那么x²一定是大于等于0的 我们可以举一个例子，当n等于4的时候
4位的带符号整数5，它的平方就不是等于25，而是等于-7
因为在机器里面，5和5相乘，乘出来 的结果是25，是这样的一个八位的
二进制，因为我们的结果只取低4位，所以这个低4位的
1001这个机器数对应的真值应该是等于-111
-111就是等于十进制的-7，5乘5就变成了-7，因此
在机器里面就会出现这样的问题，这个是因为结果溢出了，也就是用4位
来表示这个乘积的结果是无法表示的，在这个函数当中如何
判断这个z这个值是一个正确的值呢？我们只要在返回之前
进行一个判断z和x,y之间的关系 在返回之前通过这个
关系表达式来判断它是不是等于真 就是如果当x等于0的时候
这个返回的z一定是正确的 当x等于0，那返回的z也是等于0，那肯定是正确的值
或者是z除x等于y的时候，也就是说
这个乘完了以后我们再把这个乘积除上x，等于y，那说明
这个z是一个正确的结果，我们也可以返回，所以 我们在写程序的时候，如果我们要写得严谨一点
那么每乘一次都要进行这样的判断 就是在这个表达式成立的时候，乘出来的乘积才是正确的
在什么情况下乘积是正确的呢？对于
用高级语言来说我们只要用这样一个关系表达式来判断就行了
如果我们的程序员不去做上面的这个式子，不去 判断的话，如果让我们的编译器去做判断的时候
编译器怎样通过指令来判断这个乘积是否正确，是否没有溢出呢？
实际上我们知道因为在机器里面这个int型的这种带符号的
整数是用补码表示的，对于n位的补码，这个乘积是一个n位的补码
那么它的表述范围是在这个里面，这个范围就意味着
乘积的高n位一定是全0或者全1
并且呢是要等于低n位的最高位 也就是说它的高n加1位应该是全是一样的
如果一个乘积它的高n位加上随后的那一位
是全0或者全1的话，那么这个乘积一定是一个正确的乘积
全0表示正数，全1呢就表示负数，就是高n加1位
它可以表示这个符号，对于unsigned的这种
带符号的乘来说，也就是这边的x,y,z都改成unsigned的话
那么它的判断方式实际上更简单，是什么呢？ 它得到的2n位的乘积
因为只取低n位 所以它的高n位应该是全0，也就是说有效数字
不会进到高n位当中去，如果编译器去进行溢出判断的话
它只要用一条指令来判断一下得到的这个高n位的乘积在那个寄存器里面
那个寄存器是不是全0，如果不是的话那就溢出，如果是的话
那就不溢出，那如果是程序员自己去判断的话
当然也是用这个式子，是完全一样的，程序员自己去判断可以用这个表达式来判断
编译器去判断的时候要转换成指令判断，用的是这个规则
带符号数用的是这个规则，我们来看一看机器当中
无符号乘法器和带符号乘法器它们之间有什么关系
对于一个无符号乘法器，它的输入的两个乘数xu和yu
这两个乘数它的对应的 机器数，也就是对应的这种二进制的表示是Xu
和Yu，在这个里面进行二进制的
乘运算，乘出来的当然是2n位的乘积，假定我们把高n位
它的机器数用Puh表示，低n位的
机器数，也就是那个0 1序列我们用Pu表示，那么对于带符号的乘法
两个乘数xs和ys 这两个数对应的补码表示也就是它的机器数是Xs
和Ys，在带符号乘法器里面计算
它也能得到2n位的乘积，其中高n位呢我们用Psh表示
低n位用Ps表示，一共有2n位 那这个里面实际上
如果Xu和Xs 是相等，并且Yu和Ys相等的话
那么这个低n位的乘积是一定一样的，也就是说这个无符号乘法器当中的两个输入端
和带符号乘法器的两个输入端如果完全一样 那么在用无符号乘法
来算和带符号乘法来算，得到的2n位的乘积当中
低n位的乘积是完全一样的，不同的是高n位的
机器数，因此我们不去用高n位来判溢出的话 那么就可以在机器里面只用
一个无符号乘法器来实现带符号数的乘法 如果编译器要去判断是否溢出
编译器要用指令，指令当中要用到高n位来判断溢出，就是我们刚才讲的
对于无符号数的话看看高n位是不是等于全0，对于带符号数的话看看这个高n位是不是
所有的位都等于低n位当中的最高位
来判断溢出，这个是编译器用指令它可以直接取到这个机器数来判断
那么对于高级语言程序员在写程序的时候自己去判溢出的时候
这时候我们可以不要用到高n位的 这个乘积，直接拿乘出来的这个低n位的乘积
和原来的乘数进行相比，就是刚才我们前面 讲的，这表达式我们只要拿这个乘积
和两个乘数去做相应的比较， 满足某种条件说明不溢出。
这种情况下我们就可以在这个机器当中，只用
一个无符号乘法器来实现带符号乘法器。
这时候就无法用编译器来进行 判断而只能高级语言程序员自己通过这个
乘积和这两个乘数的关系来进行比较，这是
整数乘的一些底层跟运算电路相关的一些概念。
那么我们可以举些例子，这个地方 有若干个例子，这些例子当中，
两个乘数的机器数都是一样的0110， 1010，那么这两个机器数对于分别
是无符号乘和带符号乘，它的结果我们可以看到 它是低n位是
一样的，低四位是一样的，高四位不一样。
因为对于无符号乘来说0110实际上是6，
1010实际上是10，也就是6和10相乘应该等于60，也就是说乘出来的这个八位- 数，它是
这样的一个数字，如果只取低四位的话，它也就是12，12不等于60，也就说最后是- 溢出了。
这个溢出我们直接可以判断根据前面的高四位是非全零，那么说明它就发生了溢出。
在高级语言当中比较的话，12 除上6不等于10，所以也是溢出的。
对于带符号乘来说0110就是6， 1010就是-6，乘出来的结果应该是-36.
那么用带符号的乘法器来乘的时候，-36实际上乘出来是这样的一个八位数字。
如果我们只取低四位的话，就得到的是-4，显然也是溢出的，我们只要用
-4除以6可以看到它不等于-6，所以高级语言程序员可以这样来判断
也能判断出它是溢出的，那么编译器来判断的时候它可以根据 高四位和低四位的最高位比，如果
不相等，这边并不是每一位都等于1， 说明它发生了溢出，如果是每一位都等于1，
并且等于最高位的1，那么就不溢出，那这个例子就是下面的这个例子。
在这个两个机器数分别是0010和1100的时候，
在无符号乘的时候是表示2*12， 得到的八位的机器数是这样的一个机器数，
那么实际上就是24，如果我们把高四位丢掉只取低四位的话，那它就是个8，
那无符号数里面是8，显然这个里面高四位不是全零，因此是溢出的。
而且用高级语言当中的结果来进行判断的话，比如说
高级语言程序员来写的时候用8去除2的时候，很显然是4，不等于12，
也能判断它是溢出，而对于带符号乘来说，
0010等于2，1100等于-4，
在带符号乘法器里面算出来八位的成绩， 应该是等于1111
1000，但这个里面， 很显然用编译器进行溢出判断的时候，它只要看高四位是不是全1，
并且呢是不是等于低四位当中的第一位符号位， 显然是满足的，说明它没有溢出低四位的结果，
就是整个乘积的结果，则是-8，因为这个8位的补码也是-8，
四位的补码也表示-8，因此高四位是可以丢掉的。
那么如果高级语言程序员在高级语言里面用乘积直接去比的话，那它只要用-8
除上2等于-4， 来进行判断。
因为相等所以结果也是不溢出的，这个例子反映了 具体的一些乘数，乘出来的这个结果
是符合我们前面讲的那些规则的。
我们可以看出 在乘法器当中这个乘法器这种硬件它是不判溢出的
它只是把 2n 位的乘积留下来放到寄存器里面。
这个软件也就是可以是编译器，编译器可以用 2n 为乘积当中的高 n 位 和低 n 位去比，或者是看高 n
位是不是等于全零，对于带无符号数来说 如果高级语言程序员自己不去进行判断不去防止，
判断是否溢出，不去进行一些防范的话，编译
器就必须来做这件事情，如果编译器也不去
进行溢出处理，实际上我们的这个程序 就会有隐患，这些隐患会由于乘积
溢出，就是整数相乘，乘出来乘积溢出而带来一些问题。
因此我们可以看出在无符号乘和带符号乘当中，它乘出来的这个2n
位的乘积实际上是不一样的，对于带符号乘法器当中的两个乘数
分别和无符号乘法器的两个乘数分别相等的时候， 它得到的
2n 位的乘积是不一样的，因此在机器当中
它要分无符号数的乘指令和带符号数的乘指令。
而对于前面我们讲的加减运算当中实际上我们可以看出两个
加数a和b一旦确定以后，不管它是带符号数还是无符号数，它得到的那个 sum
是完全一样的，因此在加减运算的时候可以不分无符号加，带符号加，无符号减和带符号减。
也就是说无符号的加减运算和带符号的加减运算可以 完全是用同一条减法指令或者是加法指令。
而这样的乘法指令必须分无符号和带符号，当然如果你只取
低n位的话这两个也是可以合起来的，但是这时候编译器是无法来进行
判断溢出了，只能是高级语言程序员自己去写代码，判溢出。
比如说我们在 IA-32 当中，
它有一条乘法指令，乘数给出 来的是 n
位的，比如说给出来的是个 8位的寄存器，这个
其中的一个乘数是在给出来的 8 位寄存器里面，另外
一个乘数是在累加器里面，那么8位的和8位的配， 配出来的这个乘积相乘以后的结果
那就是一个16位的乘积，如果给出来的是一个十六位的寄存器， 那么它就和十六位的累加器配，两个十六位的数相乘
乘出来的是一个三十二位的乘积，放在这两个寄存器里， 那么如果原操作数在32位的寄存器当中，
那么这个三十二位的数和三十二位的累加器的数进行相乘，乘出来的结果是一个六十四位- 的乘积。
放在这两个寄存器当中，这个是 IA-32 当中的其中 的一种乘法指令。
在 MIPS 处理器当中，这是一个 带符号乘的指令，它会将
32 位寄存器当中的这个值， 也就是带符号整数，乘，乘出来的结果呢是有64位的乘积。
这64位的乘积放在两个32位的寄存器里面。
Hi和Lo里面，因此编译器可以根据 Hi
寄存器每一位 来看是否等于 Lo 寄存器当中的第一位
来判断溢出，这个时候编译器就可以来判断溢出了。
那么乘法指令我们刚才讲过它是 不能生成溢出标志的，因为这个乘法器
或者乘法运算电路，它不生成溢出标志，因此指令也不会产生溢出标志。
编译器不是通过溢出标志来判断，而是 通过2n位乘积当中的高n位和低n位之间的关系，
或者无符号数当中就直接用高n位是否等于零， 来进行判断是否溢出的。
我们下面可以看一个例子， 在这个例子当中是有一个漏洞的，这个漏洞是什么呢？
这个例子是一个复制数组的例子， 那么给定一个数组，这个数组的首地址作为参数
传递过来，然后这个复制的数组的元素个数是 作为一个参数
count，那么首先我们要 在堆区动态的申请一块区域，
这个是复制到的目的地的一块区域。
就是把已知的数组当中的一块数据 复制到堆里面去，因此在这里面我们申请
count 个数组元素，每个数组元素呢 是四个字节，对于32位机器来说是四个字节，因此我们
在堆里面申请了这么一块空间，如果这个申请了这块空间 能够正常执行的时候，那么我们就可以继续做
复制操作，这个复制是复制count这个数组元素 从给定的这个数组首地址
开始，array[0]，array[1] 一个一个地复制到申请的那块区域里面去
这个里面就存在一个问题，就是当参数count很大的时候 这个乘积是会发生溢出的。
比如说，当count 是等于2的30加1这么大的时候
这两个数乘起来，它的结果就是一个很大的数
比如说2的30次方加1，这个是count的值
如果是乘以数组元素的长度，也就是int型的这个
长度是4个字节，那么这个乘起来很显然它是2的32次方加4
在机器里面，实际上我们一直讲过它是一种模运算系统
所以这个乘法，最终只取32位
这个2的32次方就无法表示，实际上是32位以外的那个1
就被丢掉了，因此最终得到的这个乘积 就是4，取模，意味着把高位丢弃
当这个等于4的时候，所以 在这个堆里面，实际上我们只申请了
4个字节，这儿假定是4个字节
因此我们执行这个循环的时候，当i等于0的时候，把array[0]
附到了这个申请的这个空间里面去 传送了4个字节。
当这个i继续加 当i等于1、 等于2、
等于3的时候，那么这个循环里面的这个赋值语句 就会继续对这个空间进行复制，对这个空间进行复制
那么实际上我们在堆里面只分配了4个字节的空间
如果继续对这个区域 进行复制的话，这块区域当中
原来的那些数据就会被 破坏。
这个就是这个里面的一个漏洞 这种漏洞
实际上可以造成非常严重的问题。
如果 有攻击者要进行干坏事的话，他可以构造
一个特殊的参数，比如说构造这个count一个很大的这种参数，然后来触发这种
溢出，溢出以后就可以使得 它把自己预设的一段信息，比如说在这个
数组当中，预设一段信息，然后这段信息可以通过这个赋值语句
来覆盖已分配的这个堆缓冲区 那么这样的话，把自己要想做的一些破坏性的程序
把它通过这个赋值语句 送到这个堆里面去，如果启动这段代码运行的话
就会使得远程的服务器崩溃，或者 改变一些内存当中的数据
造成非常严重的问题 这样的事情在历史上曾经
是发生过的 变量和常数之间的乘运算
可以有一些简便的方法，因为在机器当中整数的乘法运算
比移位和加法等运算的时间要长得多
因为乘法运算，它实际上是通过加减运算 和移位运算来实现的。
这个小学的时候我们就学过 乘法运算是通过重复地加若干次得到的。
因此我们在机器里面实际上也就是通过 重复地加若干次，每加一次移位一下，每加一次移位一下
因此一个乘法运算要用很多时钟周期来实现 而一个时钟周期我们可以实现一次移位
或者一次加或者一次减，甚至不用一个时钟周期就能实现 一次移位、 一次加或者一次减。
因此在编译器 处理常数和变量进行相乘的时候
往往是把乘法转换成移位、 加法或者减法的组合运算来实现的
比如说高级语言当中有这么一个表达式，x乘上20
编译器呢就通过20等于16加4 来进行转换，把x乘20转换
成x左移4位，就相当于乘上16 再加上x左移两位，相当于x乘上4
那么就等于16x加上4x就等于20x
这样的话，一次乘运算就转换成了两次移位和一次加法
不管是无符号数还是带符号整数
的这个乘法，那在这个里面x不管是无符号数还是带符号数 如果x乘上这个常数是溢出的
那么它转换成移位和加减运算的组合的时候也是溢出的 也就是说，这两种方式它们的结果是完全一样的。
不溢出，也是不溢出，溢出，它也会溢出
所以编译器可以完全地不考虑溢出，而直接用这个来实现
这种情况下，是否溢出，我们可以用刚才我们前面讲的高级语言
程序语言的话用乘积和一个乘数 去除，除出来的结果看看是不是等于另外一个乘数
这种方式来判断溢出。
[音乐] [音乐]
