Leetcode - 371 . Sum of Two Integers

 

[Must do Easy questions]

How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss

 

Sum of Two Integers - LeetCode

---

문제

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1:

Input: a = 1, b = 2

Output: 3

Example 2:

Input: a = -2, b = 3

Output: 1

---

덧셈 구현이다. 근데 + 랑 - 를 쓰면 안된다. 띠용

 

비트연산을 하라는 건가 싶다.

 

비트연산자

~ : NOT

 →값이 0이면 1을 1이면 0으로 [반전]시킴

& : AND

| : OR

^ : XOR(베타적 논리합)

 

SHIFT

>> <<

비트를 좌측/ 우측으로 이동

XOR 은 올림 수가 없을 때 그러니까 (0, 1) 또는 (1, 0) 에서 결과값이 XOR 의 결과값과 같다.

AND 는 올림 수가 있을 때 그러니까 (1, 1) 또는 (0, 0)에서 결과값이 AND 의 결과값과 같다.

 

그래서 올림이 없는 결과값은 sum 에 올림은 carray 변수를 사용한다.

 

sum은 비트의 올림수를 뺀 나머지를 표시하고 carray는 올림수를 표시하니 

sum = a^b;

carray = a&b << 1;

로 정한다.

 

첫번째 코드

class Solution {
    public int getSum(int a, int b) {
        int sum = 0;
        int carry = 0;
        if(a == 0){
            return b;
        }
        if(b == 0){
            return a;
        }
        
        System.out.println(Integer.toBinaryString(a));
        System.out.println(Integer.toBinaryString(b));
        // XOR 올림수 없을 때 
        sum = a^b; //두 비트 다를 때 1
        // AND 올림수 있을 때
        carry = (a&b) << 1;
        
        sum = sum^carry;
        System.out.println(Integer.toBinaryString(sum));
        System.out.println(Integer.toBinaryString(carry));

        return sum;
        
        
    }
}
/* input 41+52 */
/* output
101001
110100
1011101
1000000
*/

어림도 없지

123123
121

output 122984

expected 1233244

Wrong Answer

 

 

 

그럼 뺄셈은...?

 

-2는 비트로 : 11111111111111111111111111111110(2) 이다.

첫번째 1은 음수를 표현하고 나머지 1111111111111111111111111111110은 0000000000000000000000000000001의 보수이다

int a 의 보수는 ~a+1 로 구할 수 있다.

뺄셈도 덧셈처럼

 

2의보수? ex) A의 2의 보수= Not A + 1
따라서, 다음과 같다.
i-j = i+(~j+1)

 

 

일단 모르겠으니 예제를 잡아서 따라가 보자

12 + 22를 한다고 치면

  1100

 10110

답은 100010 이 되어야 한다.

sum은 11010 

carray    100 

가 된다.

 

그리고 sum = sum^carry를 하면

sum 은 11110 이 된다. 그렇게 틀린다.

carry 가 생겨서 앞자리에 carry 가 또 생기는 것을 반영하지 못하고 있다.

 

슬쩍 힌트를 봤다. 

재귀함수 형태이다.

sum을 따로 선언하지 않고 a에 반영하고 b 를 줄여나가다가 b 가 0이 되면 탈출한다.

 

carray 는 동일하게 a&b로 계산하고

다른 값은 a = a^b로 계산한다.

b 에 계산된 carry 를 왼쪽으로 한칸 쉬프트 한다.

 

언젠간 b 가 0 이되어 a 를 리턴하며 탈출한다.

 

class Solution {
    public int getSum(int a, int b) {
        if (a == 0) {
            return b;
        }
        if (b == 0) {
            return a;
        }
        System.out.println(Integer.toBinaryString(a));
        System.out.println(Integer.toBinaryString(b));

        while (b != 0) {
            //carry 는 올림수가 있을 때 1이다.
            int carry = a & b;
            //a 와 b 를 더한 값을 a에 반영한다. (carry 빼고)
            a = a ^ b;
            //b는 캐리만큼 왼쪽으로 쉬프트 한다.
            b = carry << 1;
            System.out.println("carry : " + Integer.toBinaryString(carry));
            System.out.println("a : " + Integer.toBinaryString(a));
            System.out.println("b : " + Integer.toBinaryString(b));


        }
        return a;

    }

}

Accepted

3 ms

36.3 MB

java

 

Bit shifting 이 이해가 잘안되서 추가적으로 공부했다.