首先講講異或

1^0=1 1^1=0 0^1=1 0^0=0

(1+0)mod2=1 (1+1)mod2=0 (0+1)mod2=1 (0+0)mod2=0

mod是求餘數的運算

於是我們可以把異或看成不帶進位的二進位制加法。（我們經常稱異或是“模2和”）

sum = a ^ b; sum也就是a和b不帶進位的和。

現在考慮進位：

1+1時會產生進位剩下的都不會，正好符合按位與的性質

1^1=1 1^0=0 0^1=0 0^0=0

即a和b按位與後是1的位會進位

而每一位進位的效果就是它左邊的一位加一

所以假設進位的各位是carry,進位的效果就是sum+(carry左移一位）

既然是求和 就可以直接呼叫Add(sum,carry

當不出現進位的時候，遞迴就可以終止了，所以有

if (b == 0) return a;