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.

직접 + 할 말은 없지만 + 를 사용하지 않는 작업이 중요합니다.
Bit Operation을 테스트할 때, 비트별로 혹은 두 개의 조작수로 대응하는 비트와 캐리를 사용할 수 있습니다. 단지 캐리가 1인지 0인지 상황에 따라 토론을 해야 합니다.더 나은 해법을 구하다

 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         // Click submit, you will get Accepted!

 9         int i = 0;

10         int res = 0;

11         int carry = 0;

12         for (; i<32; i++) {

13             int aa = (a >> i) & 1;

14             int bb = (b >> i) & 1;

15             res |= (aa ^ bb ^ carry) << i;

16             if (aa == 1 && bb == 1 || ((aa ==1 || bb == 1) && carry == 1)) {

17                 carry = 1;

18             }

19             else carry = 0;

20         }

21         return res;

22     }

23 };

다른 사람의 간결한 사고방식을 붙이다.
비트 연산이 정수 덧셈을 실현하는 본질은 바로 2진법으로 연산하는 것이다.주로 두 가지 기본 표현식을 사용했습니다: x^y//실행 덧셈, 진위를 고려하지 않습니다.(x&y)<<1//진위 조작령 x=x^y;=(x&y)<<1을 교체하면 매번 한 번 진위 조작할 때마다 오른쪽에 0이 많고 최대'가수 2진위 길이'를 필요로 하는 차례 교체는 진위가 없다. 이때 x^y의 값은 결과이다.
3자리 덧셈: 101+011=1000//정상 덧셈 가산법: (1)101^011=110(101&011)<<1=010(2)110^010=100(110&010)<1=100(3)100^100=000(100&100)<1=1000 이때 덧셈 조작을 하면 진위가 없다. 즉, 000^1000=1000이 마지막 결과다.

 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;

10             a = a ^ b;

11             b = carry << 1;

12         }

13         return a;

14     }

15 }

또는 Recursion으로 쓰기:

1     public int aplusb(int a, int b) {

2         // Click submit, you will get Accepted!

3         if (b == 0) return a;

4         int sum = a^b;

5         int carry = (a&b)<<1;

6         return aplusb(sum, carry);

7     }