最近，在看《劍指Offer——名企面試官精講典型編程題》一書，當看到“面試題47：不用加減乘除做加法”時，經過一分鐘左右思考后，得出了思路，跟書上一對照，基本一致，呵呵O(∩_∩)O~。于是，隨即又開始思考：加法是實現了，那么減法、乘法還有除法又該怎么實現呢？一番思考與分析后，得出算法，寫出代碼，測試通過，Happy！！\(^o^)/~
接下來，就將我的算法與代碼展示如下，還請有更好算法的牛人不吝賜教！！
【1. 加法】
因本人的算法與《劍指Offer——名企面試官精講典型編程題》中一致，就不做贅述，而只貼出代碼。
代碼1.1 加法：計算a+b
int Add(int a, int b)
{
int sum = a ^ b;
int carry = a & b;
while (carry != 0) {
a = sum;
b = carry << 1;
sum = a ^ b;
carry = a & b;
}
return sum;
}【2. 減法】
方案一：通過Add函數的實現
按常規思路，根據加減運算的互反性（即，減去一個數等于加上這個數的相反數），然后利用前面已實現的Add函數來進行實現。
按這個思路，我們首先要做到對一個整數取相反數，不能使用運算符“-”，那么就只能根據C++上兩個互為相反數的int型數據的二進制結構關系——整數的相反數等于該數按位取反再加1，來設計如下的函數了。
代碼2.1 取整數n的相反數
int OppositeNumber(int n)
{
return Add(~n, 1);
}
然后就可以通過Add函數來實現減法了。
代碼2.2 減法一：計算a-b
int Subtract(int a, int b)
{
return Add(a, OppositeNumber(b));
}
畢竟是作為對思維開放的一個鍛煉，所以對于直接的減法算法的思考還是值得的。于是就有了下面的方案二。
方案二：直接通過位操作實現減法
算法是得通過二進制位計算來實現的，所以在分析減法時從二進制減法計算的角度去考慮將更合適。那么，兩個二進制形式整數的減法操作又是怎樣進行的呢？
- 首先，如果減數為0，則被減數即為減法的結果，運算結束。
但如果減數不為0，我們可以先把被減數和減數上同為1的位從兩個數上去除。至于如何分離出值同為1的位，則可以通過求位與操作來做到；而把這些1分別中被減數和減數中去除，則可以通過按位異或來的操作來實現。 - 經步驟1處理后，被減數和減數在對應的位上，將或者通為0，或者分別為0和1，卻不會同為1。此時：
如果對應位被減數=1，而減數=0，則所得結果對應位也為1；
如果對應位被減數=0，而減數=1，則所得結果對應位還是1，但此時須向前一位借1；
即，通過被減數與減數作位異或的操作得到臨時結果，和通過對減數左移一位得到需從臨時結果中減去的借數。 - 于是，經過步驟2后，原來的減法變成了要求：臨時結果 - 借數
很明顯，只要以臨時結果為被減數，借數為減數，重復步驟1~3即可。
上述步驟中，如果被減數或減數為負數，由負數的二進制位結構，可以保證上述步驟的處理仍適用，證明過程就請恕我在這里略去了。具體的實現代碼如下。
代碼2.3 減法二：計算a-b
int Subtract(int a, int b)
{
while (b != 0)
{
int sameBits = a & b;
a ^= sameBits;
b ^= sameBits;
a |= b;
b <<= 1;
}
return a;
}
※注：上述加法和減法中，按代碼安全性，其實還應考慮計算后數據溢出的情況，這里我偷了下懶，省去了。不過下面的乘除法，我會提供包含了異常處理的代碼。異常處理的方式，我采用了throw拋出的方式。
【3. 乘法】
為了方便對數據溢出的統一處理，在進行計算前，我先保存了被乘數與乘數的符號信息，并當被乘數或乘數為負時，利用上面的OppositeNumber函數，統一的轉換為正整數（或0），然后再來進行乘法的運算。為了能同時適應32位和64位的整形數，在取符號信息與設置溢出判斷位時，使用了以下的輔助宏和函數。
代碼3.1 輔助宏與輔助函數
#define BITS_OF_ONE_BYTE 8
#define SIGN_BIT_FLAG_FOR_BYTE 0x80 // for signed byte/char
int SignBitFlagOfInt()
{
static int signBitFlag = 0;
static bool bIs1stCalled = true;
if (bIs1stCalled)
{
int temp = SIGN_BIT_FLAG_FOR_BYTE;
while (temp != 0)
{
signBitFlag = temp;
temp <<= BITS_OF_ONE_BYTE;
}
bIs1stCalled = false;
}
return signBitFlag;
}
乘法的算法。考慮到：
- 整數n乘以2k == n << k
- C++中的任何一個非負int型數據都可以表示為如下的形式：
k0×20+k1×21+...+km×2m
的形式。（其中：ki∈{0, 1}, i∈{0, 1, ... , m}, 32位int型m = 30, 64位int型m = 62）
于是，就可以利用乘法分配率，通過循環累加，進行乘法的運算了。參考代碼3.2。
代碼3.2 乘法：計算a×b
int Multiply(int a, int b)
{
int signStatA = a & SignBitFlagOfInt();
if (signStatA != 0)
{
a = OppositeNumber(a);
}
int signStatB = b & SignBitFlagOfInt();
if (signStatB != 0)
{
b = OppositeNumber(b);
}
int overFlowFlag = SignBitFlagOfInt(); // used for checking if the signed int data overflowed.
int product = 0; // the result of |a| * |b|
for (int curBitPos = 1; curBitPos != 0; curBitPos <<= 1)
{
if ((b & curBitPos) != 0)
{
product = Add(product, a);
if (((a & overFlowFlag) != 0)
|| ((product & overFlowFlag) != 0))
{
throw std::exception("The result data war overflowed.");
}
}
a <<= 1;
}
return ((signStatA ^ signStatB) == 0) ? product : OppositeNumber(product);
}
【4. 除法】
整數的除法，不同于乘法，除法所得的商的絕對值必然不大于被除數的絕對值，而所得余數的絕對值則必然小于除數的絕對值。所以，在設計除法函數的時候，無需考慮數據溢出的問題。但對于除法，卻也有它自己的禁忌——除數不能為“0”。
為了處理的方便，準備工作同乘法一樣，記錄下被除數與除數的符號狀態（比便在計算出結果后進行符號的調整），并當被除數或除數為負時，通過函數OppositeNumber將其轉換為相反數。于是，接下來，我就只需考慮“非負整數（>=0）÷正整數（>0）”的情況了。對這種情況，計算過程如下：
- 預備工作：置商為0；
- 判斷“被除數>=除數 ”是否成立：
成立，繼續步驟3；
不成立，被除數的值賦給余數，計算結束。 - 備份除數，并設置商分子（一個臨時變量，最終需加到商上面，故暫且如此命名）為1；
對商分子和除數同步向左移位，直到繼續移位將大于被除數時為止； - 從被除數上減去除數，并將商加上商分子。
- 通過備份的除數值還原除數，跳轉到步驟2繼續執行。
對應的代碼參加代碼4.1。
代碼4.1 除法：計算a÷b
int Divide(int a, int b, int * pRem /**//*= NULL*/)
{
if (b == 0)
{
throw std::exception("Invalid divisor!! (The divisor can't be 0!)");
}
int signStatA = a & SignBitFlagOfInt();
if (signStatA != 0)
{
a = OppositeNumber(a);
}
int signStatB = b & SignBitFlagOfInt();
if (signStatB != 0)
{
b = OppositeNumber(b);
}
int quotient = 0;
int backupB = b;
while (a >= b)
{
int tempB = b << 1;
int tempQ = 1;
while ((tempB <= a) && ((tempB & SignBitFlagOfInt()) == 0))
{
b = tempB;
tempQ <<= 1;
tempB <<= 1;
}
a = Subtract(a, b);
quotient |= tempQ;
b = backupB;
}
if (pRem != NULL)
{
*pRem = a;
}
if ((signStatA != 0) && (a != 0))
{
quotient = Add(quotient, 1);
if (pRem != NULL)
{
*pRem = Subtract(b, *pRem);
}
}
return ((signStatA ^ signStatB) == 0) ? quotient : OppositeNumber(quotient);
}
※注：函數的返回值即為所求的商；
參數pRem為余數的傳出參數，其默認值NULL，表示當前無需關注余數。