C語言 解決不用+、-、×、÷數(shù)字運算符做加法的實現(xiàn)方法
更新時間:2013年05月24日 09:09:23 作者:
本篇文章是對在C語言中解決不用+、-、×、÷數(shù)字運算符做加法的方法進行了詳細(xì)的分析介紹,需要的朋友參考下
題目:寫一個函數(shù),求兩個整數(shù)的之和,要求在函數(shù)體內(nèi)不得使用+、-、×、÷。
分析:這又是一道考察發(fā)散思維的很有意思的題目。當(dāng)我們習(xí)以為常的東西被限制使用的時候,如何突破常規(guī)去思考,就是解決這個問題的關(guān)鍵所在。
看到的這個題目,我的第一反應(yīng)是傻眼了,四則運算都不能用,那還能用什么啊?可是問題總是要解決的,只能打開思路去思考各種可能性。首先我們可以分析人們是如何做十進制的加法的,比如是如何得出5+17=22這個結(jié)果的。實際上,我們可以分成三步的:第一步只做各位相加不進位,此時相加的結(jié)果是12(個位數(shù)5和7相加不要進位是2,十位數(shù)0和1相加結(jié)果是1);第二步做進位,5+7中有進位,進位的值是10;第三步把前面兩個結(jié)果加起來,12+10的結(jié)果是22,剛好5+17=22。
前面我們就在想,求兩數(shù)之和四則運算都不能用,那還能用什么?。繉ρ?,還能用什么呢?對數(shù)字做運算,除了四則運算之外,也就只剩下位運算了。位運算是針對二進制的,我們也就以二進制再來分析一下前面的三步走策略對二進制是不是也管用。
5的二進制是101,17的二進制10001。還是試著把計算分成三步:第一步各位相加但不計進位,得到的結(jié)果是10100(最后一位兩個數(shù)都是1,相加的結(jié)果是二進制的10。這一步不計進位,因此結(jié)果仍然是0);第二步記下進位。在這個例子中只在最后一位相加時產(chǎn)生一個進位,結(jié)果是二進制的10;第三步把前兩步的結(jié)果相加,得到的結(jié)果是10110,正好是22。由此可見三步走的策略對二進制也是管用的。
接下來我們試著把二進制上的加法用位運算來替代。第一步不考慮進位,對每一位相加。0加0與 1加1的結(jié)果都0,0加1與1加0的結(jié)果都是1。我們可以注意到,這和異或的結(jié)果是一樣的。對異或而言,0和0、1和1異或的結(jié)果是0,而0和1、1和0的異或結(jié)果是1。接著考慮第二步進位,對0加0、0加1、1加0而言,都不會產(chǎn)生進位,只有1加1時,會向前產(chǎn)生一個進位。此時我們可以想象成是兩個數(shù)先做位與運算,然后再向左移動一位。只有兩個數(shù)都是1的時候,位與得到的結(jié)果是1,其余都是0。第三步把前兩個步驟的結(jié)果相加。如果我們定義一個函數(shù)AddWithoutArithmetic,第三步就相當(dāng)于輸入前兩步驟的結(jié)果來遞歸調(diào)用自己。
有了這些分析之后,就不難寫出如下的代碼了:
int AddWithoutArithmetic(int num1, int num2)
{
if(num2 == 0)
return num1;
int sum = num1 ^ num2; //異或運算
int carry = (num1 & num2) << 1; //對0加0、0加1、1加0而言,都不會產(chǎn)生進位,只有1加1時,會向前產(chǎn)生一個進位。因此兩個數(shù)先做位與運算,然后再向左移動一位。
return AddWithoutArithmetic(sum, carry);
}
分析:這又是一道考察發(fā)散思維的很有意思的題目。當(dāng)我們習(xí)以為常的東西被限制使用的時候,如何突破常規(guī)去思考,就是解決這個問題的關(guān)鍵所在。
看到的這個題目,我的第一反應(yīng)是傻眼了,四則運算都不能用,那還能用什么啊?可是問題總是要解決的,只能打開思路去思考各種可能性。首先我們可以分析人們是如何做十進制的加法的,比如是如何得出5+17=22這個結(jié)果的。實際上,我們可以分成三步的:第一步只做各位相加不進位,此時相加的結(jié)果是12(個位數(shù)5和7相加不要進位是2,十位數(shù)0和1相加結(jié)果是1);第二步做進位,5+7中有進位,進位的值是10;第三步把前面兩個結(jié)果加起來,12+10的結(jié)果是22,剛好5+17=22。
前面我們就在想,求兩數(shù)之和四則運算都不能用,那還能用什么?。繉ρ?,還能用什么呢?對數(shù)字做運算,除了四則運算之外,也就只剩下位運算了。位運算是針對二進制的,我們也就以二進制再來分析一下前面的三步走策略對二進制是不是也管用。
5的二進制是101,17的二進制10001。還是試著把計算分成三步:第一步各位相加但不計進位,得到的結(jié)果是10100(最后一位兩個數(shù)都是1,相加的結(jié)果是二進制的10。這一步不計進位,因此結(jié)果仍然是0);第二步記下進位。在這個例子中只在最后一位相加時產(chǎn)生一個進位,結(jié)果是二進制的10;第三步把前兩步的結(jié)果相加,得到的結(jié)果是10110,正好是22。由此可見三步走的策略對二進制也是管用的。
接下來我們試著把二進制上的加法用位運算來替代。第一步不考慮進位,對每一位相加。0加0與 1加1的結(jié)果都0,0加1與1加0的結(jié)果都是1。我們可以注意到,這和異或的結(jié)果是一樣的。對異或而言,0和0、1和1異或的結(jié)果是0,而0和1、1和0的異或結(jié)果是1。接著考慮第二步進位,對0加0、0加1、1加0而言,都不會產(chǎn)生進位,只有1加1時,會向前產(chǎn)生一個進位。此時我們可以想象成是兩個數(shù)先做位與運算,然后再向左移動一位。只有兩個數(shù)都是1的時候,位與得到的結(jié)果是1,其余都是0。第三步把前兩個步驟的結(jié)果相加。如果我們定義一個函數(shù)AddWithoutArithmetic,第三步就相當(dāng)于輸入前兩步驟的結(jié)果來遞歸調(diào)用自己。
有了這些分析之后,就不難寫出如下的代碼了:
復(fù)制代碼 代碼如下:
int AddWithoutArithmetic(int num1, int num2)
{
if(num2 == 0)
return num1;
int sum = num1 ^ num2; //異或運算
int carry = (num1 & num2) << 1; //對0加0、0加1、1加0而言,都不會產(chǎn)生進位,只有1加1時,會向前產(chǎn)生一個進位。因此兩個數(shù)先做位與運算,然后再向左移動一位。
return AddWithoutArithmetic(sum, carry);
}
相關(guān)文章
C++面試基礎(chǔ)之static關(guān)鍵字詳解
這篇文章主要給大家介紹了關(guān)于C++面試基礎(chǔ)之static關(guān)鍵字的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-02-02
C++中HTTP?代理服務(wù)器的設(shè)計與實現(xiàn)詳解
代理服務(wù)器,即允許一個網(wǎng)絡(luò)終端(一般為客戶端)通過這個服務(wù)與另一?個網(wǎng)絡(luò)終端(一般為服務(wù)器)進行非直接的連接,下面我們就來看看如何使用C++設(shè)計與實現(xiàn)一個HTTP?代理服務(wù)器吧2024-01-01
詳解C語言結(jié)構(gòu)體中的char數(shù)組如何賦值
這篇文章主要給大家介紹了關(guān)于C語言結(jié)構(gòu)體中的char數(shù)組如何賦值的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2022-03-03
函數(shù)指針的強制類型轉(zhuǎn)換實現(xiàn)代碼
函數(shù)指針的強制類型轉(zhuǎn)換實現(xiàn)代碼。需要的朋友可以過來參考下,希望對大家有所幫助2013-10-10

