不使用 ＋－×÷ 運(yùn)算符來實(shí)現(xiàn) 加減乘除 四項(xiàng)運(yùn)算

最近，在看《劍指Offer——名企面試官精講典型編程題》一書，當(dāng)看到“面試題47：不用加減乘除做加法”時(shí)，經(jīng)過一分鐘左右思考后，得出了思路，跟書上一對(duì)照，基本一致，呵呵O(∩_∩)O~。于是，隨即又開始思考：加法是實(shí)現(xiàn)了，那么減法、乘法還有除法又該怎么實(shí)現(xiàn)呢？一番思考與分析后，得出算法，寫出代碼，測(cè)試通過，Happy！！\(^o^)/~

 接下來，就將我的算法與代碼展示如下，還請(qǐng)有更好算法的牛人不吝賜教！！

【1. 加法】

 因本人的算法與《劍指Offer——名企面試官精講典型編程題》中一致，就不做贅述，而只貼出代碼。

代碼1.1 加法：計(jì)算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函數(shù)的實(shí)現(xiàn)

按常規(guī)思路，根據(jù)加減運(yùn)算的互反性（即，減去一個(gè)數(shù)等于加上這個(gè)數(shù)的相反數(shù)），然后利用前面已實(shí)現(xiàn)的Add函數(shù)來進(jìn)行實(shí)現(xiàn)。

按這個(gè)思路，我們首先要做到對(duì)一個(gè)整數(shù)取相反數(shù)，不能使用運(yùn)算符“-”，那么就只能根據(jù)C++上兩個(gè)互為相反數(shù)的int型數(shù)據(jù)的二進(jìn)制結(jié)構(gòu)關(guān)系——整數(shù)的相反數(shù)等于該數(shù)按位取反再加1，來設(shè)計(jì)如下的函數(shù)了。

代碼2.1 取整數(shù)n的相反數(shù)

int OppositeNumber(int n)
{
    return Add(~n, 1);
}

然后就可以通過Add函數(shù)來實(shí)現(xiàn)減法了。

代碼2.2 減法一：計(jì)算a-b

int Subtract(int a, int b)
{
    return Add(a, OppositeNumber(b));
}

畢竟是作為對(duì)思維開放的一個(gè)鍛煉，所以對(duì)于直接的減法算法的思考還是值得的。于是就有了下面的方案二。

方案二：直接通過位操作實(shí)現(xiàn)減法

算法是得通過二進(jìn)制位計(jì)算來實(shí)現(xiàn)的，所以在分析減法時(shí)從二進(jìn)制減法計(jì)算的角度去考慮將更合適。那么，兩個(gè)二進(jìn)制形式整數(shù)的減法操作又是怎樣進(jìn)行的呢？

1. 首先，如果減數(shù)為0，則被減數(shù)即為減法的結(jié)果，運(yùn)算結(jié)束。
   但如果減數(shù)不為0，我們可以先把被減數(shù)和減數(shù)上同為1的位從兩個(gè)數(shù)上去除。至于如何分離出值同為1的位，則可以通過求位與操作來做到；而把這些1分別中被減數(shù)和減數(shù)中去除，則可以通過按位異或來的操作來實(shí)現(xiàn)。
2. 經(jīng)步驟1處理后，被減數(shù)和減數(shù)在對(duì)應(yīng)的位上，將或者通為0，或者分別為0和1，卻不會(huì)同為1。此時(shí)：
   如果對(duì)應(yīng)位被減數(shù)=1，而減數(shù)=0，則所得結(jié)果對(duì)應(yīng)位也為1；
   如果對(duì)應(yīng)位被減數(shù)=0，而減數(shù)=1，則所得結(jié)果對(duì)應(yīng)位還是1，但此時(shí)須向前一位借1；
   即，通過被減數(shù)與減數(shù)作位異或的操作得到臨時(shí)結(jié)果，和通過對(duì)減數(shù)左移一位得到需從臨時(shí)結(jié)果中減去的借數(shù)。
3. 于是，經(jīng)過步驟2后，原來的減法變成了要求：臨時(shí)結(jié)果 - 借數(shù)
   很明顯，只要以臨時(shí)結(jié)果為被減數(shù)，借數(shù)為減數(shù)，重復(fù)步驟1~3即可。

上述步驟中，如果被減數(shù)或減數(shù)為負(fù)數(shù)，由負(fù)數(shù)的二進(jìn)制位結(jié)構(gòu)，可以保證上述步驟的處理仍適用，證明過程就請(qǐng)恕我在這里略去了。具體的實(shí)現(xiàn)代碼如下。

代碼2.3 減法二：計(jì)算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;
}

※注：上述加法和減法中，按代碼安全性，其實(shí)還應(yīng)考慮計(jì)算后數(shù)據(jù)溢出的情況，這里我偷了下懶，省去了。不過下面的乘除法，我會(huì)提供包含了異常處理的代碼。異常處理的方式，我采用了throw拋出的方式。

 【3. 乘法】

為了方便對(duì)數(shù)據(jù)溢出的統(tǒng)一處理，在進(jìn)行計(jì)算前，我先保存了被乘數(shù)與乘數(shù)的符號(hào)信息，并當(dāng)被乘數(shù)或乘數(shù)為負(fù)時(shí)，利用上面的OppositeNumber函數(shù)，統(tǒng)一的轉(zhuǎn)換為正整數(shù)（或0），然后再來進(jìn)行乘法的運(yùn)算。為了能同時(shí)適應(yīng)32位和64位的整形數(shù)，在取符號(hào)信息與設(shè)置溢出判斷位時(shí)，使用了以下的輔助宏和函數(shù)。

代碼3.1 輔助宏與輔助函數(shù)

#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;
}

乘法的算法。考慮到：

1. 整數(shù)n乘以2^k == n << k
2. C++中的任何一個(gè)非負(fù)int型數(shù)據(jù)都可以表示為如下的形式：
   k₀×2⁰+k₁×2¹+...+k_m×2^m
   的形式。（其中：k_i∈{0, 1}, i∈{0, 1, ... , m}, 32位int型m = 30, 64位int型m = 62）

于是，就可以利用乘法分配率，通過循環(huán)累加，進(jìn)行乘法的運(yùn)算了。參考代碼3.2。

代碼3.2 乘法：計(jì)算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. 除法】

整數(shù)的除法，不同于乘法，除法所得的商的絕對(duì)值必然不大于被除數(shù)的絕對(duì)值，而所得余數(shù)的絕對(duì)值則必然小于除數(shù)的絕對(duì)值。所以，在設(shè)計(jì)除法函數(shù)的時(shí)候，無需考慮數(shù)據(jù)溢出的問題。但對(duì)于除法，卻也有它自己的禁忌——除數(shù)不能為“0”。

為了處理的方便，準(zhǔn)備工作同乘法一樣，記錄下被除數(shù)與除數(shù)的符號(hào)狀態(tài)（比便在計(jì)算出結(jié)果后進(jìn)行符號(hào)的調(diào)整），并當(dāng)被除數(shù)或除數(shù)為負(fù)時(shí)，通過函數(shù)OppositeNumber將其轉(zhuǎn)換為相反數(shù)。于是，接下來，我就只需考慮“非負(fù)整數(shù)（>=0）÷正整數(shù)（>0）”的情況了。對(duì)這種情況，計(jì)算過程如下：

1. 預(yù)備工作：置商為0；
2. 判斷“被除數(shù)>=除數(shù) ”是否成立：
   成立，繼續(xù)步驟3；
   不成立，被除數(shù)的值賦給余數(shù)，計(jì)算結(jié)束。
3. 備份除數(shù)，并設(shè)置商分子（一個(gè)臨時(shí)變量，最終需加到商上面，故暫且如此命名）為1；
   對(duì)商分子和除數(shù)同步向左移位，直到繼續(xù)移位將大于被除數(shù)時(shí)為止；
4. 從被除數(shù)上減去除數(shù)，并將商加上商分子。
5. 通過備份的除數(shù)值還原除數(shù)，跳轉(zhuǎn)到步驟2繼續(xù)執(zhí)行。

對(duì)應(yīng)的代碼參加代碼4.1。

代碼4.1 除法：計(jì)算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);
}

※注：函數(shù)的返回值即為所求的商；
       參數(shù)pRem為余數(shù)的傳出參數(shù)，其默認(rèn)值NULL，表示當(dāng)前無需關(guān)注余數(shù)。

posted on 2012-03-30 01:30 青碧竹 閱讀(5009) 評(píng)論(7)  編輯 收藏 引用 所屬分類: 算法相關(guān)