# ZJ k683 - A+B Problem - Revisited 題解

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

### 初步想法

這題就是要你只使用位元運算以及乘除法來計算出 $A+B$ 的值。有學過加法器 (阿其實我沒學過) 的話可能已經大概知道這題怎麼做了。

### 其實不用所有操作都使用 ?

前面提到的加法器，運作原理就是使用位元運算來達成的，所以也許這裡可以不用用到乘除法就可以算出來了。

### 作法

可以觀察兩個數做 $or$ $and$ $xor$ 這些操作時所產生的一些性質 :


如果 $A\ and\ B = 1$，相當於兩個數都是 $1$ ，相加要進位。
如果 $A\ or\ B = 1$，相當於兩個數至少有一個是 $1$。
如果 $A\ xor\ B = 1$，相當於兩個數有 $0$ 或 $2$ 個是 $1$。

發現我們可以先做進位，也就是把 $and$ 出來的結果左移運算，當成新的 $A$ 或 $B$ ，然後一樣做加法運算，而 $xor$ 可以算出那一項是不是運算結束後是 $0$，也就是如果判斷出這個是不是 $0+1$ 或 $1+0$ 。

我們把 $and$ 和 $xor$ 出來的結果當成新的 $A$ 和 $B$，再從頭一開始的操作。

### 分析

那這個操作要做的次數，其實因為每次最低不為 $0$ 位數都一定會變成 $0$，而 $2^{60}$ 的相加運算，只需要做約 $60$ 次就行了。