用位運算實現(xiàn)加法也就是計算機用二進制進行運算，32位的CPU只能表示32位內(nèi)的數(shù)，這里先用1位數(shù)的加法來進行，在不考慮進位的基礎上，如下
1 + 1 = 0
1 + 0 = 1
0 + 1 = 1
0 + 0 = 0
很明顯這幾個表達式可以用位運算的“^”(按位異或)來代替，如下
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
要獲取進位我們可以如下思考：
0 + 0 = 0
1 + 0 = 0
0 + 1 = 0
1 + 1 = 1
//換個角度看就是這樣
0 & 0 = 不進位
1 & 0 = 不進位
0 & 1 = 不進位
1 & 1 = 進位
正好，在位運算中，我們用“<<”表示向左移動一位，也就是“進位”。那么我們就可以得到如下的表達式：//進位可以用如下表示：(x&y)<<1
到這里，我們基本上擁有了這樣兩個表達式
x^y //執(zhí)行加法
(x&y)<<1 //進位操作
我們來做個2位數(shù)的加法，在不考慮進位的情況下
11+01 = 100 // 本來的算法
// 用推算的表達式計算
11 ^ 01 = 10
(11 & 01) << 1 = 10
//到這里 我們用普通的加法去運算這兩個數(shù)的時候就可以得到 10 + 10 = 100
//但是我們不需要加法，所以要想別的方法，如果讓兩個數(shù)再按剛才的算法計算一次呢
10 ^ 10 = 00
(10 & 10) << 1 = 100
到這里基本上就得出結(jié)論了，其實后面的那個 “00” 已經(jīng)不用再去計算了，因為第一個表達式就已經(jīng)算出了結(jié)果。
繼續(xù)推理可以得出三位數(shù)的加法只需重復的計算三次得到第一個表達式的值就是計算出來的結(jié)果。
現(xiàn)總結(jié)如下：
定理1：設a，b為兩個二進制數(shù)，則a+b = a^b + (a&b)<<1。
證明：a^b是不考慮進位時加法結(jié)果。當二進制位同時為1時，才有進位，因此 (a&b)<<1是進位產(chǎn)生的值，稱為進位補償。將兩者相加便是完整加法結(jié)果。
定理2：使用定理1可以實現(xiàn)只用位運算進行加法運算。
證明：利用定理1中的等式不停對自身進行迭代。每迭代一次，進位補償右邊就多一位0，因此最多需要加數(shù)二進制位長度次迭代，進位補償就變?yōu)?，這時運算結(jié)束。
加法的C代碼如下：
int add(int a, int b)
{
if (b == 0)
return a;
int sum = a ^ b;
int carry = (a & b) << 1;
return add(sum, carry);
}
減法只是將減數(shù)取補碼（按位取反，加1），然后相加。
減法的C代碼如下：
int sub(int a, int b)
{
return add(a, add(~b, 1));
}
乘法就是將乘數(shù)寫成(2^0)*k0 + (2^1)*k1 + (2 ^2)*k2 + ... + (2^31)*k31，其中ki為0或1，然后利用位運算和加法就可以了。
乘法的C代碼如下：
int mul(int a, int b)
{
int res = 0;
for (int i = 1; i; i <<= 1, a <<= 1)
if (b & i)
res = add(res, a);
return res;
}
除法就是由乘法的過程逆推，依次減掉（如果夠減的話）divisor << 31、divisor << 30、... 、divisor << 2、divisor << 1、divisor（要保證不能溢出）減掉相應數(shù)量的除數(shù)就在結(jié)果加上相應的數(shù)量。
除法的C代碼如下：
int div(int a, int b)
{
int sign = 1;
if (a & (1 << 31))
{
a = ~sub(a, 1);
sign ^= 1;
}
if (b & (1 << 31))
{
b = ~sub(b, 1);
sign ^= 1;
}
int res = 0;
for (int i = 0x8000; i; i >>= 1)
if ((a >> i & 0xFFFF) >= b)
{
res = add(res, 1 << i & 0xFFFF);
a = sub(a, b << i & 0xFFFF);
}
if (!sign)
res = ~sub(res, 1);
return res;
}
另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
重慶分公司
重慶分公司
