信息的表示与存储 - 整数的运算

用户头像
引花眠
关注
发布于: 2020 年 06 月 21 日

一般而言,计算机中整数的运算与实际数学中的运算是有差别的,大部分编程语言(比如C语言、Java等)对于整数的运算都是有限制的,它只支持固定精度的运算。

无符号整数加法与乘法

无符号整数加法

对于两个由w位表示的无符号数x、y,其取值范围是在,则x+y的范围在,所以x+y的实际值可能大于2^w-1,超过了w位能表示的范围,所以必须对x+y的值进行截断,使其能够被w位所表示,截断方法为x+y mod 2^wx+y-2^w。所以有可能出现x+y<x,x+y<y的情况。比如在Java中,char是16位无符号整数,则其最大值是65535,

public class CharNumberTest(){
@Test
public void test(){
//'\uFFFE'=65534,x+y=65535+65535=131070,x+y-2^w=131070-65536=65534
assertEquals('\uFFFE', (char) (Character.MAX_VALUE + Character.MAX_VALUE));
}
}

无符号整数乘法

同样,取值范围是在,则x*y的取值范围是,最高可能需要2w位表示,超过了w位能表示的范围,所以必须对x*y的值进行截断,使其能够被w位所表示,截断方法为x*y mod 2^w

public class CharNumberTest(){
@Test
public void testMul(){
//x*y=65535*65535=4294836225 , 4294836225%65536=1
assertEquals((char) 1, (char) (Character.MAX_VALUE * Character.MAX_VALUE));
}
}

补码加法与乘法

补码加法

因为有符号整数的负数通常采用补码形式表示,所以减法可以表示为补码加法。对于两个由w位表示的有符号数x、y,其取值范围是在,则x+y的范围在,所以x+y的实际值可能超过了w位能表示的范围,所以必须对x+y的值进行截断,使其能够被w位所表示,因为x+y的值可能大于也可能小于,所以要根据不同的情况进行区分:

  1. 时,则x、y都是正数,产生了进位,符号位变为了1,所以其表示的实际数字为

  2. 时,则x、y都是负数,其符号位都是1,相加进位[1]0,符号位变为了0,所以其表示的实际数字为

  3. 时,在w位有符号整数表示范围之内,所以其表示的实际数字为



public class ShortNumberTest(){
@Test
public void test(){
//x+y=32767+32767=65534,x+y-2^w=65534-65536=-2
assertEquals((short) -2, (short) (Short.MAX_VALUE + Short.MAX_VALUE));
//
assertEquals((short) 50, (short) (12 + 38));
//x+y=-32768+-32768=-65536,x+y+2^w=-65536+65536=0
assertEquals((short) 0, (short) (Short.MIN_VALUE + Short.MIN_VALUE));
}
}

补码乘法

取值范围是在,则x*y的最小值是,其最大值是,同样如果要用补码来表示这个值,可能需要2w位,也需要截断。在计算补码乘法时,一般会将数据当作无符号数,计算好结果之后,将结果mod 2^w,将这个值转换为有符号数,就是所求的结果。比如-127用8为补码表示为[10000001]补,将该二进制对应的无符号数是129,所以,将其截断为8位后[0111110]=126。

public class IntegerOperationTest {
@Test
public void short_mult_short() {
//x*y=32767*32767=16129 , 1073676289%32768=1
assertEquals((short) 1, (short) (Short.MAX_VALUE * Short.MAX_VALUE));
//二进制表示相同的两个数,其无符号数与有符号数的值是不同的
assertEquals(32768, (char) Short.MIN_VALUE);
//x*y=32768*32768=1073741824 , 1073741824%32768=0
assertEquals((short) 0, (short) (Short.MIN_VALUE * Short.MIN_VALUE));
assertEquals((short) 0, (short) (1073741824));
assertEquals(32769, (char) -32767);
//x*y=32769*(126)=16384 , 4128894%128=126
assertEquals((short) 126, (short) ((short) -32767 * (byte) 126));
assertEquals((short) 126, (short) (4128894));
}
}

移位运算

在计算机中乘法与除法的运算相对加法耗时更长,如果能够将其转换为移位运算,则会大幅度减少运算时间。在移位运算时,byte、short和char类型移位后的结果会变成int类型,对于byte、short、char和int进行移位时,规定实际移动的次数是移动次数和32的余数,也就是移位33次和移位1次得到的结果相同。移动long型的数值时,规定实际移动的次数是移动次数和64的余数,也就是移动66次和移动2次得到的结果相同。

左移

左移就是在二进制位左边补0,高位抛弃,在数据没有溢出的情况下,左移k位意味着将数乘以2^w。如果有溢出,则根据无符号或有符号的规则,进行截断。

public class IntegerOperationTest {
@Test
public void left() {
//x*y=32767*4=131068 , 1 1111 1111 1111 1100
assertEquals((short) -4, (short) (Short.MAX_VALUE << 2));
assertEquals((short) -4, (short) (131068));
//x*y=65535*4=262140 , 11 1111 1111 1111 1100
assertEquals((char) 65532, (char) (Character.MAX_VALUE << 2));
assertEquals((char) 65532, (char) (262140));
}
}

逻辑右移

逻辑右移就是在二进制位右边补0,低位抛弃。对于无符号数x,逻辑右移k位意味着x/2^k,而对于有符号数逻辑右移,右移一位则变成了正数。

public class IntegerOperationTest {
@Test
public void logic_right() {
assertEquals(1073741824, (Integer.MIN_VALUE >>> 1));
assertEquals(2147483647, -1 >>> 1);
assertEquals(7, 15 >>> 1);
}
}

算术右移

算术右移就是在二进制位右边补符号位(正数补0,负数补1),低位抛弃。右移一位相当于除2,右移k位相当于除以2的k次方。对于无符号数算术右移,结果是向0舍入;而对于有符号数,如果x>=0时,与无符号数相同,对于x<0,结果是向下舍入,比如-1>>1,结果还是-1

public class IntegerOperationTest {
@Test
public void right() {
assertEquals(-1073741824, (Integer.MIN_VALUE >> 1));
assertEquals(-1, -1 >> 1);
assertEquals(7, 15 >> 1);
}
}

参考资料

  1. 百度百科-左移运算符

  2. 豆瓣-深入理解计算机系统(原书第3版)



发布于: 2020 年 06 月 21 日 阅读数: 11
用户头像

引花眠

关注

还未添加个人签名 2018.06.11 加入

还未添加个人简介

评论

发布
暂无评论
信息的表示与存储-整数的运算