首页 > 代码库 > LintCode-A+B Problem
LintCode-A+B Problem
For given numbers a and b in function aplusb, return the sum of them.
Note
You don‘t need to parse the input and output. Just calculate and return.
Example
If a=1 and b=2 return 3
Challenge
Can you do it with out + operation?
Clarification
Are a and b both 32-bit integers?
- Yes.
Analysis:
Use bit manipulation.
Solution 1:
Caluclate every bit.
1 class Solution { 2 /* 3 * param a: The first integer 4 * param b: The second integer 5 * return: The sum of a and b 6 */ 7 public int aplusb(int a, int b) { 8 int res = 0; 9 int carry = 0;10 for (int i=0;i<32;i++){11 int a1 = a & 1;12 int b1 = b & 1;13 int val = 0;14 if (a1==1 && b1==1 && carry==1){15 val = 1;16 carry = 1;17 } else if ( (a1==1 && b1==1) || (a1==1 && carry==1) || (b1==1 && carry==1) ) {18 val = 0;19 carry = 1;20 } else if (a1==1 || b1==1 || carry==1) {21 val = 1;22 carry = 0;23 } else {24 val = 0;25 carry = 0;26 }27 val = val << i;28 res = res | val;29 a = a >> 1;30 b = b >> 1;31 }32 33 return res;34 35 }36 };
Solution 2:
For a + b in any base, we can treat the plus as two part: 1. a + b without carry; 2. the carry generated by a +b. The a+b then equals to part 1 plus part 2. If part1+part2 generates more carry, we can then repeat this procedure, until there is no carry.
1 class Solution { 2 /* 3 * param a: The first integer 4 * param b: The second integer 5 * return: The sum of a and b 6 */ 7 public int aplusb(int a, int b) { 8 while (b!=0){ 9 int carry = a & b; //their carry (actuall, need to move to right by one bit.10 a = a^b; //their plus result without carry.11 b = carry << 1;12 }13 return a;14 }15 };
LintCode-A+B Problem
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。