深入理解计算机系统(2.6)------整数的运算

  前面两篇博客我们详细讲解了计算机中整数的表示,包括有符号和无符号(补码编码)的详细介绍。那么这篇博客我们将对它们的运算有个详细的了解。

  在讲解之前首先看下面的一个程序,看看输出结果是啥?

#include <stdio.h>

int main()
{
	int i = 2147483647;
    printf("%d\n",i+1);
    printf("%d\n",i+i);
	return 0;
}

  结果是:

  我们预期的:

i+1 = 2147483647 + 1 = 2147483648

  i+i = 2147483647 + 2147483647  = 4 294 967 294

  为什么程序中的结果和我们数学中的常识会有这么大的区别?两个正数相加得到负数。这就需要我们理解计算机中整数的运算原理。

1、计算机整数运算的局限

  我们知道计算机是用二进制序列来表示数的。而二进制序列的长度是和计算机本身的字长有关。不同的数据类型定义的二进制序列长度不一样,即不同的数据类型表示数的大小范围是不一样的。但是不管是什么数据类型,它定义的二进制序列长度是有限的,即它表示的数的大小范围是有限的

  所以两个数做运算,如果结果超出了定义数据类型所表示数的大小范围,那么结果将会出现失真。而且这个失真的结果也不是随机的,而是有迹可循的,那么到底是怎么产生失真的,请接着往下面看。

  PS:下面给出 64 位机器上C语言的整型数据类型的取值范围。本篇博客中程序运行环境都是在64位系统中进行。

2、无符号数加法运算

  前面我们讲过,对于一个 w 位的无符号二进制整数[xw-1 , xw-2 , … , x2 , x1 , x0],其值大小满足 0 <= x <= 2w-1.

如果两个无符号数相加,那么其结果应该是 0 <= x+y <=2w+1-2。很显然表示这个范围的数必须要 w+1 位二进制。

  当我们对无符号数做加法运算的时候,如果结果超过了 2w-1,那么这个结果就会失真。

#include <stdio.h>

int main()
{
	unsigned short int i = 65535;
	unsigned short int j = i+1;
    printf("%u\n",j);
	return 0;
}

  结果为:

  对于上面的程序,我们是在64位系统中进行运算。由上面给出的图片我们可以知道 unsigned short int 在计算机中占用 2 个字节。表示的数据范围是 0——216-1,即0——65535

  我们在程序中定义 i = 65535,那么 i+1=65536,这个结果是超出了 unsigned short 表示的数据范围。所以结果失真了,但是结果为什么是 0 呢?

  上一篇博客我们讲过C语言中二进制数的截断:

将一个 w 位的数 [xw-1 , xw-2 , … , x2 , x1 , x0] 截断为一个 k 位数字时,我们会丢弃高 w-k 位。得到 [xk-1 , xk-2 , … , x2 , x1 , x0]

  对于上面的 i = 65535,二进制表示为:[1111 1111 1111 1111],加1 结果为 65536,用二进制表示为 [1 0000 0000 0000 0000],为了将结果保持在 4个字节,即32位二进制序列,我们去掉最高位的 1,那么结果就变成了 [0000 0000 0000 0000],也就是打印出来的结果 0.

  一般而言,无符号加法等价于计算和模上2w

比如上面的两者计算和为 65536,模上 2w,即模上216=65536,结果为0

  ps:模表示两者相处取余

现在定义 0<= x,y <2w,那么它们运算满足下面关系:

  注意:当 2w <= x+y < 2w+1,对 x + y 进行2w的取模运算,与 x + y - 2w是等价的。

所以如果两个无符号整数作加法运算。当 x+y < 2w 时,它们的结果不变;当 2w <= x+y < 2w+1,它们的结果为 x+y-2w

3、补码加法运算 

  对于补码加法运算,因为补码编码是表示有符号的整数。

  对于一个 w 位的补码二进制整数[xw-1 , xw-2 , … , x2 , x1 , x0],其值大小满足 -2w-1 <= x <= 2w-1-1。那么 -2w <= x+y <=2w-1

想要表示上面的两个数相加和的范围,那么可能需要 w+1 来表示。这里我们也需要截取。

  与无符号加法运算不同,补码加法会出现三种情况:正溢出、正常、负溢出。定义如下:

    范围在  -2w-1  <= x,y <= 2w-1-1 做加法运算时,满足

  简单来说:补码加法运算就是先按照无符号加法进行运算,而后在进行无符号和有符号的转换。

这里我们看个例子:

#include <stdio.h>

int main()
{
	short int i = -32768;
 	short int j = i-1;
    printf("%d\n",j);
	return 0;
}

  结果为:

为什么 -32768-1 结果会是 32767?

  根据上面的公式:

  我们需要先将 -32768 和 -1 分别转换成无符号数进行加法运算,然后对得到的结果转换成有符号数。

  ①、-32768 转换成无符号数也就是 -32768+2^16=32768  

  ②、-1 转换成无符号数也就是-1+2^16=65535 

  ③、将上面两步的结果相加,然后转换成有符号数:

    即(65535+32768)-2^16=65535+32768-65536=32767

  这个过程用到的公式分别有:

4、无符号数乘法运算

  对于一个 w 位的无符号二进制整数[xw-1 , xw-2 , … , x2 , x1 , x0],其值大小满足 0 <= x <= 2w-1.

如果两个无符号数相乘,那么其结果应该是 0 <= x*y <=(2w-1)2=22w-2w+1+1。很显然表示这个范围的数可能需要 2w 位来表示。也就是 2w 位的整数乘积的低 w 位表示的值。根据我们前面讲的截断原理:可以看做是计算乘积模2w,即:

#include <stdio.h>

int main()
{
	unsigned short int i = 2;
 	unsigned short int j = i*2;
    printf("%u\n",j);
	return 0;
}

  比如上面的程序结果是:(2*2)mod 216=4 mod 65536=4

5、补码乘法 

   对于一个 w 位的补码二进制整数[xw-1 , xw-2 , … , x2 , x1 , x0],其值大小满足 -2w-1  <= x <= 2w-1-1

  那么它们的乘积x*y的取值范围在 -2w-1*(2w-1-1)=22w-2+2w-1 到 -2w-1*2w-1=-22w-2 之间。

同理 2w 位的整数乘积的低 w 位表示的值。根据我们前面讲的截断原理:补码乘法运算公式为

  假设对于w位的两个补码数来说,它们的乘积的低w位与无符号数乘积的低w位是一样的。这意味着计算机可以使用一个指令执行无符号和补码的乘法运算。下面我们来证明:

  其中x’和y’分别代表x和y的补码编码。

  那么:

(应用有符号转为无符号公式可得)

  即:          

(2w mod 2w = 0)

   由于模运算符,所有带权重 2w 的项都丢弃了,因此我们看到 x*y  和 x’*y’ 的低 w 位是相同的。

6、乘法优化

  由于在大多数机器上,整数乘法指令相当慢,需要 10 个或多个时钟周期,而其他整数运算(比如加法、减法、位级运算和移位)只需要 1 个时钟周期。

  因此编译器使用了一项重要的优化,使用移位和加法的组合来代替乘法。

结论:对于一个w位的二进制数来说,它与2k的乘积,等同于这个二进制数左移k位,在低位补k个0。

  证明过程如下:

  我们前面说过,整数乘法代价要比移位和加法代价大得多。那么C编译器会以移位、加法、减法的组合来消除很多整数乘以常数的情况。

  比如:

    计算 x*14 的乘积。 由于 14 = 23+22+21   ,那么编译器会将乘法重写为(x<<3)+(x<<2)+(x<<1)。这样就将乘法替换为三个移位和两个加法。无论 x 是无符号还是补码,甚至当乘法会导致溢出时,两个计算都会得到一样的结果。

    更好的编译器,可能会将 14 = 24-21。那么就会变成(x<<4)-(x<<1),只需要两个移位和一个减法。

7、除法运算

  实际上在大多数机器上,整数除法要比整数乘法更慢,需要 30 或更多个时钟周期。

结论:对于除以 2 的幂可以用移位来运算。无符号除法使用逻辑移位,补码除法使用算术移位。

  ①、逻辑右移在左端补k 个0。C语言中对于无符号数据必须逻辑右移。

  对于位向量[xw-1,xw-2,...,x0]逻辑右移 k 位会得到位向量:[0,...,0,xw-1,xw-2,...,xk]。转换成除法即 x/2k,从结果我们可以看出逻辑移位出现小数,总是舍入到零,比如 7/2应该是 3,而不是4

  ②、算术右移是在左端补 k 个最高有效位的值。对于一个正整数,由于最高有效位是 0 ,所以效果和逻辑右移是一样的;对于非负数,算术右移 k 位与除以 2k 是一样的。

    对于结果不需要舍入的情况结果是正确的。但是对于结果需要舍入的时候,算术右移导致的结果是向下舍入,比如 -7/2应该是 -3,而不是 -4。这是错误的。

8、总结

  那么本篇博客结束我们对于整数的表示以及运算都已经了解了。注意整数的运算我没有将减法,其实减法也就是转换为补码相加。而且计算机中也只有加法器,是没有减法器的。我们只需要将减法转换为加法运算即可。

  整数的表示和运算结束了,下一篇博客我们将会讲解浮点数,也就是有小数的数。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张泽旭的专栏

java计算奇数阶魔方阵

所谓“奇数阶魔方阵”是指n为不小于3的奇数的魔方阵。这类魔方阵的形式多样,这里我们仅讨论其中的一种形式的正规魔方阵。例如:3阶、5阶和7阶的魔方阵如图3 – 4...

632
来自专栏King_3的技术专栏

leetcode-598-Range Addition II

871
来自专栏武培轩的专栏

剑指Offer-和为S的连续正数序列

题目描述 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的...

3615
来自专栏IT可乐

由HashMap哈希算法引出的求余%和与运算&转换问题

1113
来自专栏小樱的经验随笔

2017 Multi-University Training Contest - Team 1 1006&&HDU 6038 Function【DFS+数论】

Function Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K...

2715
来自专栏来自地球男人的部落格

[LeetCode] 523. Continuous Subarray Sum

【原题】 Given a list of non-negative numbers and a target integer k, write a fun...

2118
来自专栏用户2442861的专栏

异或的应用 及剑指offer 面试 40 数组中只出现一次的数字

转载请注明出处:http://blog.csdn.net/ns_code/article/details/27568975

982
来自专栏mathor

回文自动机、AC自动机和后缀自动机介绍(1)

 我们还从一个非常经典的题目出发,最长公共子串问题。给定两个字符串S和T,求S和T的最长公共子串的长度。比如abcdefg和abacabca的最长公共子串是ab...

1253
来自专栏King_3的技术专栏

leetcode-74-搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

891
来自专栏IT可乐

深入理解计算机系统(2.4)------整数的表示(无符号编码和补码编码)

  上一篇博客我们主要介绍了布尔代数和C语言当中的几个运算符。那么这一篇博客我们主要介绍在计算机中整数是如何表示的,诸如我们在编码过程中遇到的对数据类型进行强制...

2676

扫码关注云+社区