劍指offer-47：不用加減乘除做加法-有解無憂

參考：https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html 《原碼，反碼，補碼詳解》

題目描述

寫一個函式，求兩個整數之和，要求在函式體內不得使用+、-、*、/四則運算子號，

解題思路

不能使用加減乘除，我的第一反應就是使用 位運算 和 二進制字串判斷 ，二進制字串從末尾到首位一位位判斷，也是能得出結果的，但是代碼太長，判斷多種情況，太麻煩了，這并不是一個聰明的方法，舍棄了，

另一種方法是位運算，一個數在計算機中會先轉成二進制，正數使用原碼，負數使用補碼，然后進行加減操作，例如計算機中有兩個正整數 a 和 b，a + b 則是 a 的原碼加上 b 的原碼；a - b = a + (-b)，即 a 的原碼加上 (-b) 的補碼，具體的計算程序，請看第一行的參考鏈接，講的很詳細，在Java中，負數的二進制也是使用補碼表示的，所以，只需要考慮如何完成加法便能解決問題，

首先看兩個例子，二進制是如何進行加法的，從兩個例子中可以發現，在沒有進位的情況下，兩個二進制相加，實際上進行了異或操作，在有進位的情況下，先進行異或，得到的是不包含進位的結果 (A)，然后兩個二進制再進行位與，得到只帶進位的結果 (B)，然后重復以上兩個操作，將 (A) 與左移一位的進位 (B) 異或，得到結果 (C)；將 (A) 與左移一位的進位 (B) 位與，得到結果 (D)；一直到最后位與的結果為0，即沒有進位，終止回圈，那么在最后位與之前的一步異或就是最終的結果，

例子1: 10 + 5 = 15

    1 0 1 0
+   0 1 0 1
--------------
    1 1 1 1

例子2: 9 + 5 = 14

　　 1 0 0 1              1 0 0 1            1 0 0 1               1 1 0 0                       1 1 0 0
+　　0 1 0 1        異或 　0 1 0 1　　　　位與  0 1 0 1       異或   0 0 0 1 0 (左移一位)    位與    0 0 0 1 0
--------------     ---------------     --------------     -----------------            -------------------
　　 1 1 1 0        (A)   1 1 0 0       (B)  0 0 0 1       (C)     1 1 1 0               (D)     0 0 0 0

代碼如下：

1 public int Add(int num1,int num2) {
2     while (num2 != 0) {
3         int tmp = num1 ^ num2;
4         int carry = (num1 & num2) << 1;
5         num1 = tmp;
6         num2 = carry;
7     }
8     return num1;
9 }

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/115743.html

標籤：其他

上一篇：實作斐波那契數列演算法-遞回和非遞回

下一篇：排序-雙冒泡排序和冒泡排序（采用結構體）