Java二進制的加減乘除

    引子

    某天研究 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，加法結果的結果，高位會被省去，這也是為什麼會計算出負數的原因