位運(yùn)算算法篇：位運(yùn)算實(shí)現(xiàn)加減乘除

那么我們想必對(duì)加減乘除這些數(shù)學(xué)計(jì)算并不陌生，但是對(duì)于我們的計(jì)算機(jī)來(lái)說(shuō)，由于機(jī)器只能識(shí)別二進(jìn)制的語(yǔ)言，那么我們底層的數(shù)據(jù)都是以二進(jìn)制的形式存在，那么我們CPU的計(jì)算器的加減乘除運(yùn)算肯定都是通過(guò)位運(yùn)算的方式來(lái)實(shí)現(xiàn)的，那么本篇文章就是用位運(yùn)算來(lái)實(shí)現(xiàn)我們的加減乘除運(yùn)算，那么廢話不多說(shuō)，我們進(jìn)入正文

1.加法運(yùn)算

那么在我們的現(xiàn)實(shí)生活中我們熟悉我們十進(jìn)制的加法運(yùn)算，運(yùn)算規(guī)則就是對(duì)應(yīng)的十進(jìn)制位進(jìn)行相加，然后逢十進(jìn)一，進(jìn)位到下一位上去，而由于我們計(jì)算機(jī)的各種數(shù)據(jù)都是以二進(jìn)制序列的形式存在，所以我們的加法運(yùn)算實(shí)際上就是要實(shí)現(xiàn)二進(jìn)制的加法運(yùn)算。

那么要實(shí)現(xiàn)二進(jìn)制的加法運(yùn)算的話，我們首先得知道二進(jìn)制加法運(yùn)算的規(guī)則，那么二進(jìn)制加法運(yùn)算的規(guī)則就是對(duì)應(yīng)二進(jìn)制位相加，逢二進(jìn)一，那么這里我們只能通過(guò)我們的位運(yùn)算來(lái)實(shí)現(xiàn)，那么我們的位運(yùn)算無(wú)非就是與，或，非以及異或運(yùn)算等等，那么我們?cè)趺赐ㄟ^(guò)這些位運(yùn)算來(lái)實(shí)現(xiàn)我們加法運(yùn)算的一個(gè)邏輯呢。

其中異或運(yùn)算我專門花了一片文章來(lái)講解異或運(yùn)算的原理以及應(yīng)用，那么我們知道異或運(yùn)算的本質(zhì)就是無(wú)進(jìn)位相加，那么對(duì)于實(shí)現(xiàn)我們二進(jìn)制的加法運(yùn)算，那么我們可以采取這樣的一個(gè)思路，那么我們知道我們兩個(gè)數(shù)進(jìn)行異或運(yùn)算就相當(dāng)于兩個(gè)數(shù)進(jìn)行一個(gè)無(wú)進(jìn)位相加的加法運(yùn)算，那么此時(shí)我們這里進(jìn)行完一次異或運(yùn)算，我們相當(dāng)于得到了每個(gè)對(duì)應(yīng)二進(jìn)制位相加的結(jié)果，但是唯獨(dú)每一個(gè)二進(jìn)制位沒(méi)有加上進(jìn)位信息，那么也就意味著只要我們將我們異或運(yùn)算的結(jié)果得到的二進(jìn)制序列的每一位再對(duì)應(yīng)加上進(jìn)位信息，那么就是我們的正確結(jié)果。

那么這里的進(jìn)位信息，我們知道只有兩個(gè)二進(jìn)制位都為1那么會(huì)產(chǎn)生進(jìn)位，所以這里我們假設(shè)我們a和b兩個(gè)數(shù)做加法運(yùn)算，那么我們要得到a+b的進(jìn)位信息的話，我們可以a & b，那么與運(yùn)算的規(guī)則是對(duì)應(yīng)二進(jìn)制位都為1結(jié)果才能為1，只要有一個(gè)二進(jìn)制位為0結(jié)果就為0，那么我們a&b的結(jié)果會(huì)得到一個(gè)二進(jìn)制序列，那么這個(gè)二進(jìn)制序列的每一位的0和1就表示該二進(jìn)制位相加如果有進(jìn)位，那么該二進(jìn)制位就是1,反之為0,。

那么我們實(shí)現(xiàn)加法運(yùn)算的最后關(guān)鍵一步就是剛才異或運(yùn)算無(wú)進(jìn)位相加的結(jié)果再異或上與運(yùn)算的進(jìn)位信息即可，但是與運(yùn)算得到的二進(jìn)制序列中的0和1表示是該二進(jìn)制位是否有進(jìn)位，但是實(shí)際要相加的話，因?yàn)檫M(jìn)位是要進(jìn)到下一位，所以我們就得將與運(yùn)算的二進(jìn)制序列給左移一位，然后加上異或運(yùn)算的序列。

那么可能有的讀者就有疑問(wèn)，那么我們加完萬(wàn)一還會(huì)有進(jìn)位怎么辦，比如：假設(shè)是4個(gè)二進(jìn)制位的兩個(gè)數(shù)相加

1011+0001，這里我們最低位會(huì)產(chǎn)生一個(gè)進(jìn)位到第二位，那么第二位加上我們的進(jìn)位又會(huì)產(chǎn)生一個(gè)進(jìn)位，而我們剛才的思路的話，我們將1011與0001先異或運(yùn)算得到1010，然后將1011與0001在與運(yùn)算得到0001，然后左移一位得到0010，那么我們將剛才得到的異或運(yùn)算的結(jié)果1010在與我們與運(yùn)算右移的結(jié)果再進(jìn)行異或：1010 ^ 0010 = 1000,但是我們知道1011+0001的答案實(shí)際上是1100.

所以此時(shí)將我們的剛才計(jì)算的結(jié)果1000與之前的與運(yùn)算右移的結(jié)果0010重新作為新的兩個(gè)加數(shù)，異或完后得再一次與運(yùn)算一下，確定運(yùn)算的結(jié)果是否為0，如果不為0，說(shuō)明還有進(jìn)位，那么就得在加上之前的進(jìn)位信息，所以重復(fù)之前的步驟，先異或，再與運(yùn)算然后左移，再異或：

1000 ^ 0010 =1010

(1000 & 0010)<<1=0000

1010 ^ 0000 =1010

那么我們此時(shí)將我們的結(jié)果1010和0000重新作為加數(shù)，但是我們?nèi)绻玫竭M(jìn)位信息為0，也就是沒(méi)有進(jìn)位，那么我們計(jì)算就結(jié)束，那么這里就是我們代碼設(shè)計(jì)循環(huán)的一個(gè)終止條件。

代碼實(shí)現(xiàn)：

#include<iostream>
using namespace std;
int add(int a,int b)
{while(b!=0){a=a^b;b=(a&b)<<1;}return a;
}
int main()
{int a=10,b=30;cout<<a<<"+"<<b<<"="<<endl;int res=add(a,b);cout<<res<<endl;	
}

2.減法運(yùn)算

那么我們?cè)谖贿\(yùn)算的第一篇就講到過(guò)，由于負(fù)數(shù)的補(bǔ)碼專門進(jìn)行了處理，所以一個(gè)數(shù)減去一個(gè)數(shù)，可以看成一個(gè)數(shù)加上該數(shù)的負(fù)數(shù)，那么我們減法運(yùn)算就可以應(yīng)用我們加法運(yùn)算的邏輯，這里注意一個(gè)正數(shù)得到負(fù)數(shù)我們就取反加一即可：

#include<iostream>
using namespace std;
int add(int a,int b)
{while(b!=0){int carry=(a&b)<<1;a=a^b;b=carry;}return a;
}
int main()
{int a=10,b=30;cout<<a<<"-"<<b<<"="<<endl;int res=add(a,(~b)+1);cout<<res<<endl;	
}

3.乘法運(yùn)算

那么我們對(duì)于十進(jìn)制的乘法運(yùn)算我們十分熟悉，那么可能對(duì)于二進(jìn)制的乘法運(yùn)算的話我們就顯得稍微有點(diǎn)陌生，那么我們二進(jìn)制的乘法運(yùn)算和我們十進(jìn)制的乘法運(yùn)算的運(yùn)算規(guī)則是一樣的，也就是每一個(gè)二進(jìn)制位來(lái)與另一個(gè)數(shù)相乘。

以四位二進(jìn)制數(shù)為例

1001

0110

————

? 0

1001

1001

? 0

————

? 011 0

那么我們則如何實(shí)現(xiàn)我們乘法運(yùn)算的這套邏輯呢，那么我們知道我們乘法運(yùn)算的話，那么如果該二進(jìn)制位是1，那么則是另一個(gè)乘數(shù)本身，反之如果是0，那么則是0，所以我們要現(xiàn)將這個(gè)乘數(shù)的每一個(gè)二進(jìn)制位來(lái)判斷，所以得將其與1進(jìn)行與運(yùn)算判斷該位置是0還是1，然后將下一個(gè)要判斷的二進(jìn)制位移到最低位，然后我們要將另一個(gè)乘數(shù)給左移同樣的步數(shù)，因?yàn)樽笠浦笥疫吺怯?來(lái)補(bǔ)，所以我們左移完的結(jié)果在與之前的數(shù)相加即可

代碼實(shí)現(xiàn)：

#include<iostream>
using namespace std;
int mulpitly(int a,int b)
{int i=0;int res=0;while(a!=0){int ant=a&1;if(ant!=0){res+=(b<<i);}i++;a=a>>1;}return res;
}
int main()
{int a=10,b=30;cout<<a<<"*"<<b<<"="<<endl;int res=mulpitly(a,b);cout<<res<<endl;	
}

4.除法運(yùn)算

那么我們除法運(yùn)算是我們加減乘除這4個(gè)運(yùn)算中最難實(shí)現(xiàn)的一個(gè)運(yùn)算，其中難于實(shí)現(xiàn)的原因就是很多人它不知道我們二進(jìn)制的除法的規(guī)則是什么，那么你要問(wèn)我是具體怎么實(shí)現(xiàn)我們的除法運(yùn)算，那么我的思路不是從我們除法本身的規(guī)則除法，那么我們?cè)趯?shí)現(xiàn)除法運(yùn)算之前，我們前面已經(jīng)有了我們的加法以及減法和乘法運(yùn)算，那么我們誰(shuí)說(shuō)一定就要按照二進(jìn)制本身除法的運(yùn)算規(guī)則去實(shí)現(xiàn)它，我們可以轉(zhuǎn)換為我們的乘法以及加法來(lái)實(shí)現(xiàn)我們的除法。

那么可能讀者看到這還是內(nèi)心里還是有點(diǎn)疑惑，那么我接著將一步闡述我實(shí)現(xiàn)除法的一個(gè)原理：

那么我們假設(shè)我們有兩個(gè)不同的數(shù)比如a和b，那么我們a與b做除法運(yùn)算，那么這里我們假設(shè)a是被除數(shù)，b是除數(shù)，并且a不是整除b的，我們除法運(yùn)算不就是要得到a/b的尚以及余數(shù)嗎？那么我們知道a/b會(huì)得到一個(gè)商和余數(shù)，那么意味著我們a除以b我們可以寫成：a=b*商+余數(shù)

那么現(xiàn)在我們首先求這個(gè)商的值，那么我們知道我們?nèi)魏我粋€(gè)數(shù)本質(zhì)上都是一個(gè)二進(jìn)制序列，那么同理我們的商本質(zhì)也是一個(gè)由0和1組成的二進(jìn)制序列，那么我們假設(shè)我們的數(shù)是8個(gè)二進(jìn)制位，那么如果說(shuō)我們的商是01000111，那么我們知道我們a=b*商+余數(shù)，那么我們可以將我們這個(gè)商根據(jù)它的二進(jìn)制序列將我們的原式轉(zhuǎn)換成這樣的形式：$$a=b?(2^6+2^2+2^1+2^0)+余數(shù)$$
那么我們求這個(gè)商的值是多少，我們知道我們的商本質(zhì)是一個(gè)二進(jìn)制序列，那么我們求商實(shí)際上就是可以轉(zhuǎn)換為確定商的二進(jìn)制序列中哪些位置為1，只要把所有二進(jìn)制位為1的位置確定，那么商的二進(jìn)制序列我們就知道了，那么商的值自然也就知道了，那么我們確定我們二進(jìn)制為1的位置

那么現(xiàn)在的思路就是怎么確定商的二進(jìn)制序列的1會(huì)出現(xiàn)在哪些位置呢，那么我的策略就是先依次確定該二進(jìn)制序列最左側(cè)的1出現(xiàn)的位置是哪里：

假設(shè)被除數(shù)是a，除數(shù)是b，那么對(duì)于一個(gè)有符號(hào)整形的數(shù)來(lái)說(shuō)，最高位是符號(hào)位，那么其余剩下是數(shù)值位，那么對(duì)于一個(gè)int類型含有32個(gè)二進(jìn)制位的數(shù)來(lái)說(shuō)，那么它的最高位就是第31位，因?yàn)榈?2位是符號(hào)位，那么我們就假設(shè)該二進(jìn)制序列中最左側(cè)的1在第31位，那么直到我們a除以b得到商或者余數(shù)，也就意味著除數(shù)b乘以商是一定等于或者小于我們的被除數(shù)的，那么如果滿足該位置是最左側(cè)的1的話，那么我們二進(jìn)制序列的第31位為1的得到數(shù)比如c乘以我們的除數(shù)b，它一定是小于等于我們的被除數(shù)a的，那么如果不滿足，也就是說(shuō)該二進(jìn)制位為1的數(shù)乘以除數(shù)b大于了我們的被除數(shù)a，那么我們知道該二進(jìn)制位肯定不可能為1，只能為0，那么最左側(cè)的1肯定不在第31位，那么我們就依次右移討論，那么直到討論到二進(jìn)制位為1的該數(shù)c乘以b它小于等于我們的被除數(shù)a，那么意味著該最左側(cè)的二進(jìn)制位為1的位置在該位置，那么我們就記錄，然后我們?cè)谟帽怀龜?shù)減去除數(shù)a乘以c，然后這個(gè)數(shù)作為我們的被除數(shù)，因?yàn)槲覀僡/b可以寫成:
$$a=b?(2^6+2^2+2^1+2^0)+余數(shù)$$
也就是
$$a=b?2^6+a?2^2+a?2^1+a?2^0+余數(shù)$$
最后轉(zhuǎn)換成：
$$a?b?2^6=a?2^2+a?2^1+a?2^0+余數(shù)$$
那么確定剩余的為1的二進(jìn)制位，那么重復(fù)剛才的思路，直到最后被除數(shù)如果不為0，那么該被除數(shù)就是余數(shù)。

代碼實(shí)現(xiàn)：

#include<iostream>
using namespace std;
void chufa(int& a,int& b)
{int res=0;for(int i=29;i>=0;i--){if(a==0){break;}long long ant=(long long)b*(1<<i);if(a>=ant){res+=(1<<i);a-=ant;}}b=res;return;
}
int main()
{int a=280,b=25;cout<<a<<"/"<<b<<"="<<endl;chufa(a,b);cout<<b<<" "<<a<<endl;return 0;	
}