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

关注
发布于: 2020 年 06 月 21 日
一般而言，计算机中整数的运算与实际数学中的运算是有差别的，大部分编程语言（比如C语言、Java等）对于整数的运算都是有限制的，它只支持固定精度的运算。
无符号整数加法与乘法无符号整数加法对于两个由w位表示的无符号数x、y，其取值范围是在0≤x,y≤2w−1，则x+y的范围在0≤x+y≤2w+1−2，所以x+y的实际值可能大于2^w-1，超过了w位能表示的范围，所以必须对x+y的值进行截断，使其能够被w位所表示，截断方法为x+y mod 2^w或x+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));  
    }
}
无符号整数乘法同样，取值范围是在0≤x,y≤2w−1，则x*y的取值范围是0≤x∗y≤(2w−1)2=22w−2w+1+1，最高可能需要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，其取值范围是在−2w−1≤x,y≤2w−1−1，则x+y的范围在2w≤x,y≤2w−2，所以x+y的实际值可能超过了w位能表示的范围，所以必须对x+y的值进行截断，使其能够被w位所表示，因为x+y的值可能大于也可能小于，所以要根据不同的情况进行区分：
x+y≥2w−1时，则x、y都是正数，产生了进位，符号位变为了1，所以其表示的实际数字为x+y−2w
x+y≤−2w−1时，则x、y都是负数，其符号位都是1,相加进位[1]0，符号位变为了0，所以其表示的实际数字为x+y+2w
−2w−1≤x+y<2w−1时，在w位有符号整数表示范围之内，所以其表示的实际数字为x+y
﻿
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)); 
    }
}
补码乘法取值范围是在−2w−1≤x,y≤2w−1−1，则x*y的最小值是−2w−1∗(2w−1−1)=−22w−2+2w−1，其最大值是−2w−1∗(−2w−1)=22w−2，同样如果要用补码来表示这个值，可能需要2w位，也需要截断。在计算补码乘法时，一般会将数据当作无符号数，计算好结果之后，将结果mod 2^w，将这个值转换为有符号数，就是所求的结果。比如-127用8为补码表示为[10000001]补，将该二进制对应的无符号数是129，所以−127补​∗126=[10000001]∗[0111110]=[1111100111110]，将其截断为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);
    }
}
参考资料百度百科-左移运算符
豆瓣-深入理解计算机系统（原书第3版）
﻿
发布于: 2020 年 06 月 21 日阅读数: 45
原文链接:【http://xie.infoq.cn/article/52656e0d173635ed88d640387】。
引花眠

关注
还未添加个人签名 2018.06.11 加入
还未添加个人简介
发布
暂无评论
创作场景

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

无符号整数加法与乘法

无符号整数加法

无符号整数乘法

补码加法与乘法

补码加法

补码乘法

移位运算

左移

逻辑右移

算术右移

参考资料

引花眠

评论
