如何證明 a-b≤ a xor b ?

如何證明 a-b≤a xor b (a≥b) ?

書中還有一個結論是 類似 a xor b =a- b 不知道如何證明。。

求解。。謝謝。。

註解：

看不懂題目的來看這一段。題目前提是a b 都是二進位數字，xor運算符我們都知道左右是1和0怎麼解，那麼對於任意一個多位二進位數，那xor運算符就是對每一位求xor，輸出一個數字，a b參與運算時，高位不夠用0補齊。

---

先證明當 時 ，這個根據定義就能證了。

再證明一般情況，不妨將兩數二進位分解： ， ，其中 。那麼

因為 ，所以 。

---

a xor b=a+b-2（a and b），然後顯然b≥（a and b），所以a-b≤a+b-2（a and b）≤a xor b

---

我記得這是一個UVA的題用到的結論。。？

---

（對所有整數定義 and, or, xor, not ，負數視為有無限個前導 1 的補碼）

假設 b 為非負數，或 a 為負數，則 b and not a 為非負數

因為 a xor b = a - (b and a) + (b and not a)

而 a - b = a - (b and a) - (b and not a)

所以 a - b &<= a xor b

---

我們都考慮二進位下運算，假如我們讓減法不借位

那麼a - b=a xor b

現在既然不借位都一樣，那借了位，豈不是更小。

證畢

---

看到了@好地方bug的回答我想到了差不多的一種思路：XOR就是不帶進位的加法。說是不帶進位其實也沒那麼誇張，只有a，b相同時，所謂的不進位才會出現。也就是你題目中等於的情況。

小白，如有錯誤，歡迎指出

以下內容可以不看

至於第二個結論你自己可以看看二進位加法不進位和減法也沒什麼區別了所以直接等於就行了

---

從高位往低位考慮

---

推薦閱讀：