LintCode 1. A + B Problem

原題

LintCode 1. A + B Problem

Description

Write a function that add two numbers A and B. You should not use + or any arithmetic operators.

Clarification

Are a and b both 32-bit integers?

  • Yes.

Can I use bit operation?

  • Sure you can.

Example

Given a=1 and b=2 return 3

解題

要求不用算術(shù)運(yùn)算符實(shí)現(xiàn)加法aplusb食磕,可以使用位運(yùn)算尽棕。
主要是用的異或運(yùn)算實(shí)現(xiàn)。

異或 -> 不進(jìn)位加法

Example

  • 不需要進(jìn)位的情況
2 ^ 5
2: 010
5: 101
^ -----
7: 111
  • 需要進(jìn)位
2 ^ 6
2: 010
6: 110
^ -----
5: 101

這里第二位計(jì)算的結(jié)果為0是正確的彬伦,但是并沒有向上一位進(jìn)滔悉。

不進(jìn)位加法結(jié)果:a ^ b

與 -> 進(jìn)位

接下來的問題就是獲取進(jìn)位

首先知道哪些位置需要進(jìn)位,需要進(jìn)位的位置有個(gè)特點(diǎn)就是兩個(gè)數(shù)在該位都為1单绑,因此可以通過與運(yùn)算得出回官。

Example

2 & 6
2: 010
6: 110
& -----
   010

然后只需要把需要進(jìn)位的位置左移一位就可以得到進(jìn)位。

進(jìn)位:a & b << 1

遞歸相加

  • 通過異或運(yùn)算得到了不進(jìn)位加法結(jié)果a ^ b
  • 通過與運(yùn)算得到了進(jìn)位a & b << 1

接下來只需要把這兩個(gè)數(shù)加在一起即可搂橙,這時(shí)候可以選擇遞歸調(diào)用aplusb歉提,問題就變?yōu)檫f歸何時(shí)結(jié)束。

在進(jìn)位的加法過程中,可能產(chǎn)生新的進(jìn)位唯袄,這時(shí)繼續(xù)遞歸需要調(diào)用aplusb弯屈。繼續(xù)這個(gè)過程,最終進(jìn)位會(huì)變?yōu)?code>0恋拷,此時(shí)結(jié)束遞歸。

最終代碼

class Solution {
public:
    /*
    * @param a: An integer
    * @param b: An integer
    * @return: The sum of a and b
    */
    int aplusb(int a, int b) {
        // write your code here
        if (b == 0) return a;
        return aplusb(a ^ b, (a & b) << 1);
    }
};

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末厅缺,一起剝皮案震驚了整個(gè)濱河市蔬顾,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌湘捎,老刑警劉巖诀豁,帶你破解...
    沈念sama閱讀 211,639評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異窥妇,居然都是意外死亡舷胜,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,277評論 3 385
  • 文/潘曉璐 我一進(jìn)店門活翩,熙熙樓的掌柜王于貴愁眉苦臉地迎上來烹骨,“玉大人,你說我怎么就攤上這事材泄【诨溃” “怎么了?”我有些...
    開封第一講書人閱讀 157,221評論 0 348
  • 文/不壞的土叔 我叫張陵拉宗,是天一觀的道長峦树。 經(jīng)常有香客問我,道長旦事,這世上最難降的妖魔是什么魁巩? 我笑而不...
    開封第一講書人閱讀 56,474評論 1 283
  • 正文 為了忘掉前任,我火速辦了婚禮姐浮,結(jié)果婚禮上谷遂,老公的妹妹穿的比我還像新娘。我一直安慰自己单料,他們只是感情好埋凯,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,570評論 6 386
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著扫尖,像睡著了一般白对。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上换怖,一...
    開封第一講書人閱讀 49,816評論 1 290
  • 那天甩恼,我揣著相機(jī)與錄音,去河邊找鬼。 笑死条摸,一個(gè)胖子當(dāng)著我的面吹牛悦污,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播钉蒲,決...
    沈念sama閱讀 38,957評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼切端,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了顷啼?” 一聲冷哼從身側(cè)響起踏枣,我...
    開封第一講書人閱讀 37,718評論 0 266
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎钙蒙,沒想到半個(gè)月后茵瀑,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,176評論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡躬厌,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,511評論 2 327
  • 正文 我和宋清朗相戀三年马昨,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片扛施。...
    茶點(diǎn)故事閱讀 38,646評論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡鸿捧,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出煮嫌,到底是詐尸還是另有隱情笛谦,我是刑警寧澤,帶...
    沈念sama閱讀 34,322評論 4 330
  • 正文 年R本政府宣布昌阿,位于F島的核電站饥脑,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏懦冰。R本人自食惡果不足惜灶轰,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,934評論 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望刷钢。 院中可真熱鬧笋颤,春花似錦、人聲如沸内地。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,755評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽阱缓。三九已至非凌,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間荆针,已是汗流浹背敞嗡。 一陣腳步聲響...
    開封第一講書人閱讀 31,987評論 1 266
  • 我被黑心中介騙來泰國打工颁糟, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人喉悴。 一個(gè)月前我還...
    沈念sama閱讀 46,358評論 2 360
  • 正文 我出身青樓棱貌,卻偏偏與公主長得像,于是被迫代替她去往敵國和親箕肃。 傳聞我的和親對象是個(gè)殘疾皇子婚脱,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,514評論 2 348

推薦閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗(yàn)。 張土汪:刷leetcod...
    土汪閱讀 12,738評論 0 33
  • 我是小小強(qiáng)勺像,這是我的第5篇原創(chuàng)文章起惕,閱讀需要大約10分鐘。 題目 LintCode:A+B問題 描述 給出兩個(gè)整數(shù)...
    我叫小小強(qiáng)閱讀 280評論 0 3
  • 文:冬瓜媽媽 一 過年问词,回娘家拜年督函。很久不見的親戚,大家都聚在一起激挪。你問問我的工作辰狡,我聊聊你的家庭。這是難得機(jī)會(huì)垄分。...
    夢貓人讀書閱讀 1,036評論 48 38
  • 張嘉佳是目前為止我最喜歡的作家宛篇,沒有之一。當(dāng)年的睡前故事風(fēng)靡一時(shí)之時(shí)薄湿,我不知道躲在哪里虛度光陰呢叫倍。第一次知道張嘉佳...
    倩文湘云閱讀 649評論 0 1
  • 寶寶,離開你整整27.5個(gè)小時(shí)豺瘤,聽說你昨晚開門關(guān)門出去十幾趟吆倦,聽說你看見年輕媽媽帶著小寶寶就跑過去看看,乖乖坐求,對不...
    慢半拍的小蝸牛閱讀 147評論 0 0