這種面試題...能想到的就是用位運算代替
在講解之前，首先普及一點知識
與運算（全一才是一）：
0 & 0 = 0
1 & 0 = 0
0 & 1 = 0
1 & 1 = 1
或運算（有一就是一）：
0 | 0 = 0
1 | 0 = 1
0 | 1 = 1
1 | 1 = 1
非運算（就是唱反調）：
~1 = 0
~0 = 1
異或運算（不同才是一）：
0 | 0 = 0
1 | 0 = 1
0 | 1 = 1
1 | 1 = 0
移位運算：
左移末尾自動補0
000010 << 1 = 000100
右移，含符號，首部補符號位
1110110 >> 1 = 11110111
右移，無符號，首部自動補零
1110110 >>> 1 = 01111011
好了，普及就到這了，接著往下看吧
-----------------------可愛的分割線---------------------------------
加法：
因為位運算都是針對二進制的，我們不太好理解，那我們看一下十進制的時候咱是怎么算的：
12+19 = 31
首先，從末尾開始相加，加完后溢出的部分放到前面與下一位相加，這是幼兒園的做法；
那我們換個思路，首先不考慮進位，首先逐位相加，得到的結果與進位結果相加，不斷迭代直到?jīng)]有進位；
那上面那個題
12+19，逐位相加，
得到21，進位10，逐位相加，
31，進位0，得到結果。
其實二進制也是一樣的，加法問題就轉化成了：
1.獲取逐位相加的結果
2.獲取進位的值
不斷將這兩個結果在此相加，直到?jīng)]有進位，那不就是最終的結果了嘛（笑）
單個位的加法規(guī)則：
0 + 0 = 0 （進位 0）
1 + 0 = 1 （進位 0）
0 + 1 = 1 （進位 0）
1 + 1 = 0 （進位 1）
發(fā)現(xiàn)沒，逐位加法和異或操作結果一樣，獲取進位和與操作后左移一位結果一樣；
解決了，代碼如下：
public int add(int a, int b){
while(b != 0){
int sum = a ^ b;
int pos = (a & b) << 1;
a = sum;
b = pos;
}
return a;
}
-----------------------可愛的分割線---------------------------------
減法：
emmmmmmmmmmmm，起初我還想了很久，后來真是被自己蠢到了
a - b 不就是 a + (-b) 么......
那問題就變成了怎么用位運算取到 -b
這個..就很簡單了 -n = ~n+1
代碼如下：
public int minus(int a,int b) {
return add(a, ~b+1) ;
}
對了，我們不是不讓用加減乘除符號嘛，好好好，我改...
public int minus(int a,int b) {
return add(a, add(~b, 1));
}
-----------------------可愛的分割線---------------------------------
乘法：
符號問題的話，不考慮，全按整數(shù)算，大不了最后取反就是了。
最簡單的，乘法不就是多個加法嘛，
對，引用我高中數(shù)學老師的話，我不能說你錯，但你這也不對
因為太--------慢--------了--------
我們的算法最差也會在32次循環(huán)內(nèi)結束，如果累加的話，就會導致計算規(guī)模隨b絕對值的增大而增大，這不是我們希望看到的。
還是那個思路，正常十進制是怎么算的
12*56，首先個位相乘，十位相乘后乘十，百位乘十后乘百....最后結果相加
沿著這個思路，到了二進制反而簡單了，為什么呢
首先，乘數(shù)只有0和1啊，即全清空和全保留，好像.. 啥也不用做誒
乘十，到了這里就變成了乘2，那....左移就可以了
至于結果累加.....我們上面不是做過了嘛~
看代碼吧：
public int multi(int a, int b){
int ans = 0;
int index = 0;
while(b != 0){
if( (b&1) == 1){// 判斷最后一位是不是1
ans = add(ans, a << index);
}
index = add(index, 1);
b = b >> 1;
}
return ans;
}
-----------------------可愛的分割線---------------------------------
emmmmmmmmmmmm，我早就想吐槽樓上了，一點都不可愛好嗎！
呼，終于到最后一個了，還是最簡單的思路，反復的減去除數(shù)直至被除數(shù)小于除數(shù)就行了
但又回到了問題規(guī)模的問題，如果被除數(shù)過大，除數(shù)過小，就會出現(xiàn)循環(huán)次數(shù)過多的問題
這次我們就用乘法的逆運算，先找結果中第一個一的位置，即滿足被除數(shù)>=除數(shù)<<x中x的最大值
然后相減，即貪心算法
代碼如下：
public int divide(int a, int b) {
int flag = 1;
// 處理符號問題
if(a >> 31 == 1){
a = add(~a, 1);
flg = add(~flg, 1);
}
if(b >> 31 == 1){
b = add(~b, 1);
flg = add(~flg, 1);
}
int re = 0;
while (a >= b){
int aa = 1, temp = b;
while (temp < (a>>1)){
temp <<= 1;
aa <<= 1;
}
a -= temp;
re += aa;
}
return re*flag;
}
-----------------------可愛的分割線---------------------------------
（我丟~樓上砍你哦！）
總結，
上面的操作有一些位運算的技巧在這里說一下：
b & 1 :取一個數(shù)的最后一位
~n+1 :對n取反
-n &n :整數(shù)二進制串中最后一個1
n&(n-1) :去掉整數(shù)二進制串中最后一個1
n ^ n = 0
其實，這篇文章還是不太專業(yè)的，比如，舉例時用的都是整數(shù)，細心的同學可能發(fā)現(xiàn)我沒有加判定條件，那負數(shù)為什么也適用呢？這就涉及到計算機編碼的知識了，其實就是補碼和反碼，有興趣的同學合一自行百度；
還有就是沒有考慮到整數(shù)溢出的問題，int型變量的取值范圍是[-2^31, 2^31-1]，對于
（2^31-1）+1這樣的操作是會造成溢出的，但如何處理不在我們今天的討論范圍，有興趣的同學可以自行百度
好啦，就這么多吧，這里只是一個位運算的引子，其實計算機還是蠻有趣的，共勉。
