分享一波:程序員賺外快-必看的巔峰干貨

前言

接前面一篇博客，這又是某個公司的奇葩面試題（都說了到底是哪家公司才會出這種沒營養的面試題）。不過吐槽歸吐槽，這個題目還是有點學問的，比前面那個不使用比較運算符如何比較兩個數的大小強多了（但是還是能看出面試官是在存心刁難人）。

原題是“只給加法，如何實現減乘除”，我尋思著，既然減乘除都不給了，那就加大點難度，加法也別給了吧，今天就手動去實現加減乘除。這里只實現int類型的加減乘除。

一說到這種“不給xxx如何實現xxx的問題”，那第一個想到的就是位運算，因此本篇博客的各種運算也是基于位運算的。關于位運算的知識點，請閱讀本博客的看官們自行百度學習。。。。
加法

我們先舉個加法的例子：8+9=17，可以轉換成10+7，即：二者相加不考慮進位的值，和二者相加只考慮進位的值相加。我們再通過二進制來直觀的看一下。

0000 1000 (8)
0000 1001 (9)
0001 0001 (17)

[點擊并拖拽以移動]

下面描述一下思路（可能有點繞）。

首先我們看，直接二進制相加的結果，0+0=0,1+0=1,1+1=10。好像能看出點什么。前兩個的運算規則復合“異或運算”，而后者則復合與運算并左移1位。

到現在思路就清楚了：a^b的結果是不考慮進位的結果，而a&b<<1是只考慮進位的結果。把二者相加即可。如果相加后，可能還存在進位，那就讓這兩個數字繼續相加，一直到進位為0為止。這里使用遞歸去實現，感興趣的可以用循環實現，性能比遞歸要高。

public int add(int a, int b) {// 得到原位和int xor = a ^ b;// 得到進位和int forWoad = (a & b) << 1;return forWoad == 0 ? xor : add(xor, forWoad);
}

到這里，加法就實現完畢了
負數

計算機中的負數實現，是將正數按位取反獲取反碼，之后+1獲得補碼，這個結果就是某個正數所對應的負數。（這個在計算機組成原理、操作系統、計算機導論、離散數學等課本中都有，不記得的請翻一下大學課本。）。

負數的實現其實還是比較簡單的，按位取反之后+1即可。

public int negative(int num) {return add(~num, 1);
}

減法

實現了負數之后，我們第一步實現的加法就可以和負數進行運算了，而減法也就變得簡單起來。

減法的實現如4-2等價于4+(-2)，我們直接使用加法和負數就可以實現。

public int minus(int a, int b) {return add(a, negative(b));
}

絕對值

接下來要實現乘法和除法。乘法和除法可能會有正數和負數相互計算的情況，因此我們實現乘除之前，需要先實現絕對值計算的功能，將運算數字轉換成絕對值進行乘除，之后判斷是否需要加上負號即可。

public int abs(int num) {if (num < 0) {num = minus(0, num);}return num;
}

乘法

乘法的實現，如11*10，乘法的流程如下面所示。

0000 1011 （11）
0000 1010 （10）

0001 0110 （1011<<1，相當于乘以0010）
0101 1000 （1011<<3，相當于乘以1000）

可以看到，二進制乘法的原理是：從乘數的低位到高位，遇到1并且這個1在乘數的右邊起第i（i從0開始）位，那么就把被乘數左移i位得到temp_i，直到乘數中的1遍歷完畢后，把根據各位1而得到的被乘數的左移值全部相加即得到乘法結果。

而至于存在負數的運算，可以先獲取負數的個數，再將兩個數字轉換成絕對值計算，最后判斷當負數是1個時，計算結果就是負數，其他情況則是正數。

public int multi(int a, int b) {// 先獲取負數的個數int negativeCount = negativeCount(a, b);// 負數轉正數進行計算a = abs(a);b = abs(b);int i = 0;int res = 0;// 乘數為0則結束while (b != 0) {// 處理乘數當前位if ((b & 1) == 1) {res = add(res, a << i);}b = b >> 1;i = add(i, 1);}if (negativeCount == 1) {// 轉為負數res = negative(res);}return res;
}

negativeCount方法

public int negativeCount(int a, int b) {int count = 0;if (a < 0) {count = add(count, 1);}if (b < 0) {count = add(count, 1);}return count;
}

乘法事實上有個簡單的實現。乘法就是個連加的過程，如5*4就是4個5相加，這個雖然性能比較低，但是操作起來簡單，感興趣的朋友可以自己去實現。
除法

除法沒有什么簡單的二進制實現方案，實際計算機中的除法也是通過連減去計算的。a/b的意義就是求a可以由多少個b組成，因此除法可以求a能減去多少個b。至于負數的情況，和乘法相同，不再介紹。

public int sub(int a, int b) {// 先獲取負數的個數int negativeCount = negativeCount(a, b);// 負數轉正數進行計算a = abs(a);b = abs(b);int res;if (a < b) {return 0;} else {res = add(sub(minus(a, b), b), 1);}if (negativeCount == 1) {// 轉為負數res = negative(res);}return res;
}

取模

取模運算的思路和除法一樣，也是個連減的過程，一直減到我們減不了為止，剩下的值就是我們要的結果。

public int mode(int a, int b) {// 先獲取負數的個數int negativeCount = negativeCount(a, b);// 負數轉正數進行計算a = abs(a);b = abs(b);int res;if (a < b) {res = a;} else {res = sub(minus(a, b), b);}if (negativeCount == 1) {// 轉為負數res = negative(res);}return res;
}

結語

總的來說，加減乘除的實現還是比較簡單的，只是對于初學者來說比較難想。熟悉了這類“不給xxx如何實現xxx”的題目之后，就能第一時間想到位運算了，通過位運算去實現運算符規則，實現起來就沒有什么難度了。

最后還是需要點評一下這道題。這個問題相比上次的問題，稍微的有那么點水平，但是還是不難看出面試官在刁難人。程序員需要懂的原理，應該是開發中的各種框架原理，如HashMap、Spring、Mybatis等，理解了原理才能更好的優化、擴展，以便于提高性能。而所謂的加減乘除原理并沒有這些重要，往往在上大學的時候也就了解過了。加減乘除原理的理解對性能優化幫助并不大，即使位運算性能比減法和除法高，但是這點性能損耗，在我們服務器動輒4g8g的情況下是沒有任何區別的。所以說面試的時候別問這種刁難人的問題啊，你就是造造火箭問問Spring也好！
*************************************優雅的分割線 **********************************