欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java二进制的加减乘除

程序员文章站 2022-07-15 09:58:48
...

    引子

    某天研究 fail-fast机制的时候,去看了看hashCode的实现方式,然后发现每个对象的实现都不一样;于是研究一个String的;于是看到公式:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

于是很不解,这个公式很明显会溢出(超过2^32),尝试了几次发现系统会输出hashCode为负数的值,就默默地去回顾一下二进制的加减乘除


准备工作:

-2 = 0xfffffffe
-1 = 0xffffffff
0 = 0x0
1 = 0x1
2 = 0x2
max = 0x7fffffff = 2147483647
min = 0x80000000 = -2147483648
正数与二进制的相互转换,就是简单的二进制与十进制的相互转换
负数与二进制的相互转换:
1)二进制 -> 负数 :0x80000000  取反  0x7fffffff(2147483647)  忽略符号加一 (2147483648)  结果(-2147483648)
2)负数 -> 二进制 :-2147483648 忽略符号减一(-2147483647[0x7fffffff])   取反(0x80000000) 结果(0x80000000)
PS:以上就是专业术语"补码"的含义,而补码存在的意义在于:让所有的加法能够使用同一种电路完成


接下来就是四则运算:加减乘除
1,加法[全加器]
案例一:
3 + 5 = 8
==>
  0 0 1 1  -> 3
+ 0 1 0 1  -> 5
----------
= 1 0 0 0  -> 8
因此可以看出,二进制之间的加法就是,和小学学的十进制的"尾数相加,然后进位

案例二:
1 + -1(0x7fffffff) = 0
==>
 ?_ 0 0 ... 1  -> 1
+?_ 1 1 ... 1  -> -1
--------------
=1_ 0 0 ... 0  -> 0
因此可以看出,二进制之间的加法,最高位表示的不是具体的数值,进位之后应该被舍去

2,减法[全加器]
减法可以实现的方案:1)类似十进制的减法直接去位 2)减法就是另类的加法
而计算机采用的是,方法2,原因:直接可以使用全加器

例如:a - b = a + (-b)
而通过之前的准备可以看出:二进制中,b的负数就是b的补码
因此,0xa - 0xb = 0xa + 0xb(补码[取反,忽略符号加一])

3,乘法[乘法器,芯片]
乘法可以实现方案:1)类似十进制的乘法 2)多个加法
而计算机采用的是,方法1,原因:多个加法的算法复杂度成二次方增长

案例一:
3 * 5 = 15
==>
0 0 1 1 -> 3
* 0 1 0 1 -> 5
-------------
0 1 0 1 -> 5
+ 0 1 0 1 -> 10
-------------
1 1 1 1 -> 15
PS:
1)如果有符号,符号位另算,即:同号得正,不同号得负原则
2)如果有位数移除,则高位直接舍去,然后得出剩下的二进制对应的值

4,除法[芯片]
除法可以实现方案:1)类似十进制的除法 2)多个减法,直到负数
而计算机采用的是,方法1,原因:多个减法的算法复杂的成二次方增长
14 / 3 = 4 余 2
14(1110[被除数])、3(11[除数])、4([结果])、2([余数])
==>
1 0 0 --> 结果[4]
-----------
1 1 / 1 1 1 0
---------------
1 1
---------------
0 1
---------------
1 0
---------------
1 0 --> 余数[2]
PS:
1)如果有符号,符号位另算,即:同号得正,不同号得负原则

回顾之前的问题,公式溢出问题:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

就很容易解释了,

1,31^(n-1)的结果,高位会被省去

2,加法结果的结果,高位会被省去,这也是为什么会计算出负数的原因