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ǔ)句多一些...也可以理解為遞歸需要在棧上開辟空間