[LeetCode] 371. Sum of Two Integers (두 숫자의 합)

Sum of Two Integers

371. Sum of Two Integers

Medium

---

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

 

Example 1:

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

Example 2:

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

 

Constraints:

• -1000 <= a, b <= 1000

---

문제 : 두 숫자 를 더한값을 리턴하시오. ( * + , - 기호 사용할수 없음)

처음에 더한값을 리턴까지만 보고 뭐얌? 너무쉽자나! return a+b; 했는데 그렇게 쉬울리가없지..!

이문제 의도는 비트(2진수)연산자를 얼마나 잘 이해하고 있는가 이다.

 

비트 연산자

연산자	의미	사용법	예제	설명
&	AND	x & y	x = 00000011 = 3 y = 00000110 = 6 x & y → 00000010 = 2	두 비트가 모두 1일 경우에만 1
|	OR	x | y	x = 00000011 = 3 y = 00000110 = 6 x | y → 00000111 = 7	두 비트 중에서 하나라도 1이면 1
^	XOR	x ^ y	x = 00000011 = 3 y = 00000110 = 6 x ^ y → 00000101 = 5 (x ^ y) ^ y → 00000011 = 3	두 비트가 같으면 0, 다르면 1
~	NOT	~x	x = 00000010 = 2 ~x = 11111101 = 253	각 비트를 반전, 0이면 1, 1이면 0
<<	Left Shift	x << 2	x = 00000001 = 1 x << 2 = 00000100 = 4	비트를 왼쪽으로 이동 하나 이동할 때마다 곱하기 2
>>	Right Shift	x >> 2	x = 00000100 = 4 x >> 2 = 00000001 = 1	비트를 오른쪽으로 이동 하나 이동할 때마다 나누기 2

class Solution{
	int getSum(int a, int b) {
		while(b != 0) {
			int num = a & b;
			a ^= b;
			b = num << 1;
		}
		return a;
	}
}
public class GetSum {
	
	public static void main(String[]args) {
		// 테스트 코드입니다.
		Solution test = new Solution();
		System.out.println(test.getSum(3,6));
		
	}
}

[RESULT]
9

[설명]

1번째 반복문
a : 3 [2진수] 00000011
b : 6 [2진수] 00000110

1번째 a^b :5 
A : 5 [2진수] 00000101 ( 두 비트가 같으면 0, 다르면 1)

1번째 (a&b)<<1 :4
B : 4 [2진수] 00000100 
(두 비트가 모두 1일 경우에만 1 , 비트를 왼쪽으로 1칸이동 )
여기서 a는 3, b는 6으로 (a&b) = 00000010 , << 1 = 00000100 = 4 가 된다.
아래의 반복문도 과정이 똑같다.

2번째 반복문
a : 5 [2진수] 00000101
b : 4 [2진수] 00000100
2번째 a^b :1
A : 1 [2진수] 00000001
2번째 (a&b)<<1 :8
B : 8 [2진수] 00001000

3번째 반복문
a : 1 [2진수] 00000001
b : 8 [2진수] 00001000
3번째 a^b :9
A : 9 [2진수] 00001001 <- 리턴값 9 (b 가 0이되면 반복문이 종료되고 a의 값이 리턴된다. )
3번째 (a&b)<<1 :0
B : 0 [2진수] 00000000

 

LeetCode 고수님(prashant404)의 한줄풀이👇🏻 와우..

class Solution{
	int getSum(int a, int b) {	
		return (b==0)?a:getSum(a^b, (a&b) << 1);
	}
}