Q0001:a+b不用計(jì)算運(yùn)算符

Write a function that add two numbers A and B.
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.
Challenge
Of course you can just return a + b to get accepted. But Can you challenge not do it like that?(You should not use + or any arithmetic operators.)

/**
 * @Author: cdwangmengjin
 * @Date: Created in 14:21 2018/6/27
 * @Modified by:
 */
public class Lintcode1 {

    public static void main(String[] args) {
        aplusb(1,2);
    }
    /**
     * @param a: An integer
     * @param b: An integer
     * @return: The sum of a and b
     * @desc: 由于不能使用計(jì)算運(yùn)算符 所以我們需要想到位運(yùn)算符
     *         再分析加法計(jì)算的過(guò)程
     *         如2進(jìn)制的5(101) + 17(10001)
     *         1.忽略進(jìn)位 10100 只有1+0 = 1 用異或來(lái)實(shí)現(xiàn)
     *         2.記錄進(jìn)位 00010 1+1 才進(jìn)位1 所以用 & 然后左移一位
     *         3.再遞歸一哈 直到記錄的進(jìn)位為0或者只有進(jìn)位(忽略進(jìn)位為0)
     */
    public static int aplusb(int a, int b) {
        // write your code here
        // if(a==0) return b;
        // if(b==0) return a;
        // int sum,i;
        // i = a^b;
        // sum = (a&b)<<1;
        // return aplusb(sum,i);
        int sum = 0;
        int carry = 0;
        do{
            sum = a ^ b;
            carry = (a&b) << 1;
            a = sum;
            b =  carry;
        }
        while(carry != 0);

        return sum;
    }
}

第二種實(shí)現(xiàn)比第一種性能好10% 我們現(xiàn)在探討一下為啥(當(dāng)然最佳答案性能要好60%....后續(xù)看看能不能看排名靠前的答案)
初步思路是對(duì)比一下匯編
操作:在/out/production里面 javap -c $FileNameWithoutExtention$


第一種實(shí)現(xiàn)

第二種實(shí)現(xiàn)

iconst是整型入棧指令
https://www.cnblogs.com/luyanliang/p/5498584.html
iload istore
https://segmentfault.com/q/1010000008683475

//第二種實(shí)現(xiàn)指令詳解
int sum = 0;          //iconst_0    常量0壓入操作數(shù)棧
                             //istore_2    彈出操作數(shù)棧頂元素竭业,保存到局部變量表第二個(gè)位置
int carry = 0;         //iconst_0
                             //istore_3
sum = a ^ b;         //iload_0     第0個(gè)變量壓入操作數(shù)棧
                             //iload_1
                             //ixor          操作數(shù)棧前兩個(gè)int異或,并將結(jié)果壓入操作數(shù)棧頂
                             //istore_2   
carry = (a&b) << 1;//iload_0
                              //iload_1
                              //iand
                              //iconst_1
                              //ish_1   左移一位 并將結(jié)果壓入操作數(shù)棧棧頂
                              //istore_3
a =sum;                 //iload_2
                              //istore_0
b = carry;               //iload_3
                              //istore_1
                             

whlie(carry != 0);//這兩條指令是真的皮
                           //iload_3
                           //ifne                4        如果結(jié)果不為0時(shí)(即為true)洁奈,就跳轉(zhuǎn)到第4個(gè)指令繼續(xù)執(zhí)行

所以看起來(lái)性能上的差距也沒(méi)啥...就是第一種實(shí)現(xiàn)中ifne扎扎實(shí)實(shí)語(yǔ)句多一些...也可以理解為遞歸需要在棧上開辟空間

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市抄谐,隨后出現(xiàn)的幾起案子嗅钻,更是在濱河造成了極大的恐慌,老刑警劉巖歇竟,帶你破解...
    沈念sama閱讀 222,378評(píng)論 6 516
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件长窄,死亡現(xiàn)場(chǎng)離奇詭異滔吠,居然都是意外死亡纲菌,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,970評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門疮绷,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)翰舌,“玉大人,你說(shuō)我怎么就攤上這事冬骚∫渭” “怎么了?”我有些...
    開封第一講書人閱讀 168,983評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵只冻,是天一觀的道長(zhǎng)庇麦。 經(jīng)常有香客問(wèn)我,道長(zhǎng)属愤,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 59,938評(píng)論 1 299
  • 正文 為了忘掉前任酸役,我火速辦了婚禮住诸,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘涣澡。我一直安慰自己贱呐,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 68,955評(píng)論 6 398
  • 文/花漫 我一把揭開白布入桂。 她就那樣靜靜地躺著奄薇,像睡著了一般。 火紅的嫁衣襯著肌膚如雪抗愁。 梳的紋絲不亂的頭發(fā)上馁蒂,一...
    開封第一講書人閱讀 52,549評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音蜘腌,去河邊找鬼沫屡。 笑死,一個(gè)胖子當(dāng)著我的面吹牛撮珠,可吹牛的內(nèi)容都是我干的沮脖。 我是一名探鬼主播,決...
    沈念sama閱讀 41,063評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼芯急,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼勺届!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起娶耍,我...
    開封第一講書人閱讀 39,991評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤免姿,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后榕酒,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體养泡,經(jīng)...
    沈念sama閱讀 46,522評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡嗜湃,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,604評(píng)論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了澜掩。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片购披。...
    茶點(diǎn)故事閱讀 40,742評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖肩榕,靈堂內(nèi)的尸體忽然破棺而出刚陡,到底是詐尸還是另有隱情,我是刑警寧澤株汉,帶...
    沈念sama閱讀 36,413評(píng)論 5 351
  • 正文 年R本政府宣布筐乳,位于F島的核電站,受9級(jí)特大地震影響乔妈,放射性物質(zhì)發(fā)生泄漏蝙云。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,094評(píng)論 3 335
  • 文/蒙蒙 一路召、第九天 我趴在偏房一處隱蔽的房頂上張望勃刨。 院中可真熱鬧,春花似錦股淡、人聲如沸身隐。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,572評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)贾铝。三九已至,卻和暖如春埠帕,著一層夾襖步出監(jiān)牢的瞬間垢揩,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,671評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工敛瓷, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留水孩,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,159評(píng)論 3 378
  • 正文 我出身青樓琐驴,卻偏偏與公主長(zhǎng)得像俘种,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子绝淡,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,747評(píng)論 2 361

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

  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi閱讀 7,346評(píng)論 0 10
  • PLEASE READ THE FOLLOWING APPLE DEVELOPER PROGRAM LICENSE...
    念念不忘的閱讀 13,493評(píng)論 5 6
  • [cp]過(guò)完中秋就回家了宙刘,達(dá)州總有很多驚喜。上次回來(lái)的時(shí)候整個(gè)街道很爛牢酵,說(shuō)是要翻新悬包。可是給人很不好的感覺(jué)馍乙,就像是一...
    941c3f80fee8閱讀 289評(píng)論 0 0
  • 80多高齡的老人不吃米飯布近! 從璐:要有邊界感垫释!不帶情緒的表達(dá) 會(huì)計(jì)室生氣出來(lái)的家長(zhǎng):抱怨現(xiàn)金繳費(fèi)太麻煩!接納情緒撑瞧,...
    小樹課堂閱讀 168評(píng)論 0 0