?

首先介紹計算機的二進制碼

二進制常用的有原碼，反碼和補碼，他們都是由最左邊的一個符號位和右邊的數值位構成。在計算機中為了更低成本的計算，數據都是用補碼來存儲和運算的。

原碼

最高位表示符號位（0代表正數，1代表負數）。剩下的位數，是這個數的絕對值的二進制。

比如 一個int變量大小為4字節，在32位的編譯器中的二進制表示就是00000000 00000000 00000000 00000000
那么10 的原碼就是00000000 00000000 00000000 00001010
?10的原碼就是 10000000 00000000 00000000 00001010

反碼

正數的反碼和其原碼是一樣的
負數的反碼就是在其原碼的基礎上 符號位不變 其他位取反。

10的反碼就是00000000 00000000 00000000 00001010 和原碼一樣
?10的反碼就是11111111 11111111 11111111 11110101

補碼

正數的補碼就是其原碼
負數的補碼就是在其反碼的基礎上+1

10的補碼就是00000000 00000000 00000000 00001010
?10的補碼就是 11111111 11111111 11111111 11111011

總結一下

計算機系統中，數值一律用補碼來表示：因為補碼可以使符號位和數值位統一處理，同時可以使減法按照加法來處理。
二進制編碼：數值編碼分為原碼，反碼，補碼，符號位均為0正1負。

原碼 -> 補碼： 數值位取反加1

補碼 -> 原碼： 對該補碼的數值位繼續 取反加1

補碼 的絕對值（稱為真值）：正數的真值就是本身，負數的真值是各位（包括符號位）取反加1（即變成原碼并把符號位取反）.

介紹基本的位操作

^：按位異或；&：按位與； | :按位或
b -> -b ： 各位（包括符號位）取反加1

用位操作實現加法運算

我們先不考慮進位，在1位數的加法上，如下
1. 1+1=0
2. 1+0=1
3. 0+1=1
4. 0+0=0
很明顯上面幾個表達式我們可以用異或進行統一
1. 1^1=0
2. 1^0=1
3. 0^1=1
4. 0^0=0
這樣我們就完成了最基礎的一位數的加法，但是怎么計算二位以上的加法呢？我們發現現在方法的問題在于不能夠獲取進位，于是我們通過觀察一位數的加法的式子，發現只有兩個數位都是1的時候才會有進位，其他都不進位，這不是和&很像嗎？ 我們通過把+換成&得到下式
1. 1&1=0 不進位
2. 1&0=1 不進位
3. 0&1=1 不進位
4. 0&0=0 進位
那么我們把所有位進行&操作，然后<<左移一位，不就可以當作加數當前的進位嗎？
到這里我們就完整解決了二進制相加問題中，對應位的相加和進位的問題
1. x^y 加法
2. (x&y)<<1 進位操作
那么總結一下：

定理1：設a，b為兩個二進制數，則a+b=a^b+(a&b)<<1。

證明：

a^b是不考慮進位時加法結果。當二進制位同時為1時，才有進位，因此 (a&b)<<1是進位產生的值，稱為進位補償。將兩者相加便是完整加法結果。

定理2：使用定理1可以實現只用位運算進行加法運算。

證明：

利用定理1中的等式不停對自身進行迭代。每迭代一次，進位補償右邊就多一位0，因此最多需要加數二進制位長度次迭代，進位補償就變為0，這時運算結束。

那么我們可以根據上面的定理得到實際的C++代碼如下

int add(int a, int b){int re = a;while(b){int tmp = a;a = a^b;b = (tmp&b)<<1;re = a;}return re;
}

用位操作實現減法

減法和加法原理相同，減去一個數相當于加上這個數的相反數，所以完全可以利用加法操作，唯一需要做的就是求出被減數的相反數。
求相反數的方法：每一位取反，末位加一。
代碼如下：

int subtraction(int a, int b)
{b = add(~b,1); // 求b的相反數return add(a, b);
}

用位操作實現乘法

二進制的乘法同十進制的乘法并無什么不一樣，對于a?b每次只需要將a左移對應的位，然后同上一次的結果相加即可
當b的對應位為1的時候，對a左移一位相加即可
當b的對應位位0的時候，對a左移一位，但是不相加
注意到我們上面的操作都是不包括符號位的，因此我們單獨考慮符號位。
代碼如下

int getSign(int n)
{unsigned count = 0;//計算n的位數do{++count;}while(n >> count)//得到n的最左邊的位return n >> (count-1);
}int mul(int a, int b){bool isNegative = false;if(getSign(a) ^ getSigned(b))isNegative = true;if(a < 0) a = add(~a,1);//求出a的絕對值if(b < 0) b = add(~b,1);//求出b的絕對值int res = 0;while(b){               //當b不為0，繼續循環if(b & 1)           //當b當前位為1 才需要加ares = add(res,a);a = a << 1;b = b >> 1;}if(isNegative)add(~res,1);return res;
}

二進制除法

同乘法一樣，除法一樣可以用減法來代替，當a≥b才可以上商，在每次上一個商（也就是商值加1）之后，a=a?b
代碼如下

int divide(int a, int b){if(!b)throw std::runtime_error("Divided can't be zero...");bool isNegative = false;bool isNegtive = false;if(getSign(a) ^ getSign(b))isNegtive = true;if(a < 0) a = add(~a,1);//求出a的絕對值if(b < 0) b = add(~b,1);//求出b的絕對值int res = 0;while(a >= b){res = add(res,1);a = subtraction(a,b);}if(isNegative)add(~res,1);return res;
}

---------------------
作者：harry_128
來源：CSDN
原文：https://blog.csdn.net/harry_128/article/details/80150502
版權聲明：本文為作者原創文章，轉載請附上博文鏈接！
內容解析By：CSDN,CNBLOG博客文章一鍵轉載插件