位运算:减法与补码
1 计算机运算与取模计算
计算机处理器操作的是二进制数,由于有位数限制,相当于数学中的取模计算,即在一定数值范围内进行计算,超出部分会被取模操作抵消。
以8 bit的有符号byte类型为例:最高位(第8位)为符号位,其余7位为数值位。
0000 0000
7位数值位,限定了数值范围,相当于设定模为 27=128,即取值范围为[0, 127]之间。
0 mod 128 = 0
127 mod 128 = 127
128 mod 128 = 0
129 mod 128 = 1
2 数值表示
类比时钟来理解取模运算:每一个数值,对应一个刻度位置,一个刻度位置可对应多个数值。
例如:-64、64、192都对应相同位置,即
-64 mod 128 = 64 mod 128 = 192 mod 128
但由于模值为128,因此,仅-64和64是有效范围内的合法数值。
正数表示顺时针方向移动,负数表示逆时针方向移动。
例如,+16 对应二进制 0001 0000;-16 对应二进制1001 0000。
3 补码
在取模运算中,每个数值对应一个刻度位置,同一个刻度位置对应无限个数值。
例如,-16 mod 128 = 112 mod 128,即,在取模运算中,一个负数可以由一个正数来表示,它们的刻度位置是相等的。
那么,如何通过-16得到112这个数值呢?
在模为128的情况下,
-16 mod 128 = (128 – 16) mod 128 = 112 mod 128
由此发现,对于负数-16,可通过加上一个模值128,得到一个正数112。
暂时不考虑符号位,从二进制角度来观察这个问题:
暂时不考虑符号位,从二进制角度来观察这个问题:
由于7位数值位,最大值为127,因此,我们将128拆分为1+ 127来观察,即
128 – 16 = 1 + 127 – 16 = 1 + (127 - 16)
对应二进制操作如下:
127 | 111 1111 | |
16 | 001 0000 | |
相减等于 | 110 1111 | -16反码的数值部分 |
1 | 000 0001 | |
相加等于 | 111 0000 | -16补码的数值部分 |
由此发现,112就是-16的补码(仅针对数值部分)。
所以,在取模运算中(机器运算中),减去一个数,可转化为加上这个负数的补码。
例如:
96 – 32 mod 128 = 96 + 96 mod 128 = 192 mod 128 = 64 mod 128
4 符号位
但是,最终结果应该是64,还是-64?它们都在有效数值范围内,且对应相同的刻度位置。
所以,还需要考虑如何得到正确的符号位。
先看两个减法转加法示例:
先看两个减法转加法示例:
示例一:正数绝对值 < 负数绝对值
16 – 112 mod 128
= 16 + (-112) mod 128
= 16 mod 128 + (-112 mod 128)
= 16 + 16 mod 128
= 32 mod 128
= 32
对应钟表图:
示例二:正数绝对值 > 负数绝对值
112 – 16 mod 128
= 112 + (-16) mod 128
= 112 mod 128 + (-16 mod 128)
= 112 + 112 mod 128
= 224 mod 128
= 96
对应钟表图:
上述两个示例,都通过减法转加法,得到了正确的刻度位置。
但最终结果,还需要符号位来确定,即示例一应该是32还是-96,示例二应该是96还是-32。
在运算时,将符号位参与运算,可以发现:
示例一:
16 | 0 001 0000 | |
-112 | 1 011 0000 | 负数使用补码(将减法转加法) |
相加等于 | 1 100 0000 | 符号位为负 |
由于数值位相加后,未发生进位情况,符号位不变,即结果为负数,因此,需要从补码转回原码:
1 100 0000(补码)–>1 011 1111(反码)->1 100 0000(原码)
示例二:
112 | 0 101 0000 | |
-16 | 1 111 0000 | 负数使用补码(将减法转加法) |
相加等于 | 0 100 0000 | 符号位为正 |
由于数值位相加后,发生进位情况,符号位改变,即结果为正数,因此,数值位即为原码,得到最终结果:96
至此,已经得到最终的正确结果,即确认示例一应该是-96,而不是32;示例二应该是96,而不是-32。
至此,已经得到最终的正确结果,即确认示例一应该是-96,而不是32;示例二应该是96,而不是-32。
进一步思考,什么情况下才会引发进位,从而导致符号位变化呢?
假设正数绝对值为x,负数绝对值为y,负数补码绝对值为z,模值为m,根据上述内容可知:
z = m - y
因此,
x + z = x + ( m - y ) = x - y + m
x - y < 0
x - y + m < m
在示例二中,当正数绝对值大的时候,必定导致:
x - y > 0
x - y + m > m
5 总结
由于取模计算特性可知,对于减法操作,可以找到一个相应的正数,通过加上这个正数,到达与原减法操作结果相同的刻度位置。而这个正数值,正是原负数的补码的数值部分。
由于一个刻度位置,可对应正负两个数值(仅考虑合法范围内的数值),因此,需要通过符号位来确定最终结果。
根据取模运算特性,以及限制操作数在有效范围内(Java保证了这一点,即保证操作数在其类型有效值范围内,否则抛出异常),发现数值部分的运算结果,会根据不同情况发生进位或不进位,利用该特性,将符号位参与运算,能够得到正确的最终结果符号位。
上述一切,保证了计算机中,将减法转为加法的可行性,从而,通过加法得到最终的正确计算结果。
这也是为什么计算机中,负数以其补码形式保存。负数以其补码形式执行加法运算,就相当于执行其原码的减法运算。
当负数需要输出保存或显示时,才从补码形式转为原码形式,从而保存或显示正确的数值。