[ Binary ] JAVA | 371. Sum of Two Integers (Medium)

< 리트코드 자바로 풀어보기 >

 

371번 Sum of Two Integers

Given two integers a and b, return the sum of the two integers without using the operators + and -.

=> int인 a와 b가 주어진다. 이 두 수의 합을 +와 - 연산자를 사용하지 않고 구하라.

 

Constraints:

• -1000 <= a, b <= 1000

 

예시 1)

Input: a = 1, b = 2
Output: 3

 

예시 2)

Input: a = 2, b = 3
Output: 5

 

---

 

< 내 풀이 >

• 첫 시도
  → +, - 연산자 쓰지 말라는 것을 못 보고 냅다 submit 해버림
  → Accepted 됨;;

class Solution {
    public int getSum(int a, int b) {
        if(a == 0){
            return b;
        }

        if(b == 0){
            return a;
        }

        return (a*b/b)+(a*b/a);
    }
}

 

• 두 번째 시도
  → +와 -를 사용하지 못한다면 이제 비트연산자만 남는다
  → and와 xor를 사용하여 풀어보자

 

 

• 비트 연산자란?
  → 컴퓨터는 사실 0과 1만 인식할 수 있다.
  → 십진수 연산기호 대신 비트연산자를 사용하여 이진수로 계산

 

 

• 0부터 10까지 이진수로 표현해보면?
  → 이진수로 표현 = 0과 1로만 표현

 

 

• 이진수를 비트연산자를 사용해 계산해 보도록 하겠다.
• 순서 : 1차 연산(두 수를 xor, and 각 각 계산), 2차 연산(and의 결과값을 << 1 쉬프트), 3차 연산(결과값을 다시 xor, and 계산) →이때 and의 결과가 0이면 xor을 반환, 아니라면 다시 2차 연산으로 돌아가 순서 진행

2+3 = 5
2는 10, 3은 11이며 5는 101이다.

1차 연산
→ 2^3 = 01
→ 2&3 = 10이다.

후에 and의 결과값을 << 1 쉬프트 하여 다시 xor과 and로 계산(2차 연산)한다.

→ 01^100 = 101, 01&100=000이 나온다.
and의 결과값이 0이 되면 xor를 리턴.

 

• 2+4와 5+5도 같은 방식으로 계산해 본다.

 

 

• 위와 같은 방식으로 코드를 작성

class Solution {
    public int getSum(int a, int b) {
    	int xor = a^b;
        int and = a&b;

        if(and == 0){
            return xor;
        }else{
            and = and << 1;
            return getSum(xor, and);
        }
    }
}

→ 재귀 방법으로 2차 연산부터 진행할 수 있게 작성했으나 중복인 부분이 보인다.

 

→ 다시 정리해 주자.

class Solution {
    public int getSum(int a, int b) {
        int and = a&b;

        if(and == 0){
            return a^b;
        }else{
            and = and << 1;
            return getSum(a^b, and);
        }
    }
}

→ xor 변수를 따로 만들지 않고 바로 return 혹은 바로 매개변수로 전달

• Runtime : 0ms
• Memory : 39.6MB