您好,登錄后才能下訂單哦!
用位運(yùn)算實(shí)現(xiàn)加法也就是計(jì)算機(jī)用二進(jìn)制進(jìn)行運(yùn)算,32位的CPU只能表示32位內(nèi)的數(shù),這里先用1位數(shù)的加法來進(jìn)行,在不考慮進(jìn)位的基礎(chǔ)上,如下
1 + 1 = 0
1 + 0 = 1
0 + 1 = 1
0 + 0 = 0
很明顯這幾個(gè)表達(dá)式可以用位運(yùn)算的“^”(按位異或)來代替,如下
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
要獲取進(jìn)位我們可以如下思考:
0 + 0 = 0
1 + 0 = 0
0 + 1 = 0
1 + 1 = 1
//換個(gè)角度看就是這樣
0 & 0 = 不進(jìn)位
1 & 0 = 不進(jìn)位
0 & 1 = 不進(jìn)位
1 & 1 = 進(jìn)位
正好,在位運(yùn)算中,我們用“<<”表示向左移動(dòng)一位,也就是“進(jìn)位”。那么我們就可以得到如下的表達(dá)式://進(jìn)位可以用如下表示:(x&y)<<1
到這里,我們基本上擁有了這樣兩個(gè)表達(dá)式
x^y //執(zhí)行加法
(x&y)<<1 //進(jìn)位操作
我們來做個(gè)2位數(shù)的加法,在不考慮進(jìn)位的情況下
11+01 = 100 // 本來的算法
// 用推算的表達(dá)式計(jì)算
11 ^ 01 = 10
(11 & 01) << 1 = 10
//到這里 我們用普通的加法去運(yùn)算這兩個(gè)數(shù)的時(shí)候就可以得到 10 + 10 = 100
//但是我們不需要加法,所以要想別的方法,如果讓兩個(gè)數(shù)再按剛才的算法計(jì)算一次呢
10 ^ 10 = 00
(10 & 10) << 1 = 100
到這里基本上就得出結(jié)論了,其實(shí)后面的那個(gè) “00” 已經(jīng)不用再去計(jì)算了,因?yàn)榈谝粋€(gè)表達(dá)式就已經(jīng)算出了結(jié)果。
繼續(xù)推理可以得出三位數(shù)的加法只需重復(fù)的計(jì)算三次得到第一個(gè)表達(dá)式的值就是計(jì)算出來的結(jié)果。
現(xiàn)總結(jié)如下:
定理1:設(shè)a,b為兩個(gè)二進(jìn)制數(shù),則a+b = a^b + (a&b)<<1。
證明:a^b是不考慮進(jìn)位時(shí)加法結(jié)果。當(dāng)二進(jìn)制位同時(shí)為1時(shí),才有進(jìn)位,因此 (a&b)<<1是進(jìn)位產(chǎn)生的值,稱為進(jìn)位補(bǔ)償。將兩者相加便是完整加法結(jié)果。
定理2:使用定理1可以實(shí)現(xiàn)只用位運(yùn)算進(jìn)行加法運(yùn)算。
證明:利用定理1中的等式不停對(duì)自身進(jìn)行迭代。每迭代一次,進(jìn)位補(bǔ)償右邊就多一位0,因此最多需要加數(shù)二進(jìn)制位長(zhǎng)度次迭代,進(jìn)位補(bǔ)償就變?yōu)?,這時(shí)運(yùn)算結(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ù)取補(bǔ)碼(按位取反,加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,然后利用位運(yùn)算和加法就可以了。
乘法的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(要保證不能溢出)減掉相應(yīng)數(shù)量的除數(shù)就在結(jié)果加上相應(yīng)的數(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;
}
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。