[LeetCode] 371. Sum of Two Integers (비트 연산자)

371. Sum of Two Integers

LeetCode

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

두 정수 a와 b가 주어졌을 때, +와 - 연산자를 사용하지 않고 두 정수의 합을 반환하세요.

 

Example

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

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

---

 

1. 문제 요구사항 분석

+ 연산자와 - 연산자를 사용하지 않고 두 정수의 합 계산하기

 

2. 접근 전략

되게 쉽다고 생각하고 왜 medium 문제이지? 하고 문제를 다시 봤더니... + 와 - 연산자를 사용하지 않고라니...

곱하기, 나누기로는 절대 안 되고 ... 컴퓨터적으로 생각하고 봤더니 비트연산자가 있구나!!!

비트 연산자 다 까먹어서.. 다시 정리하기 !!!!

 

😁 비트 연산으로 계산하기

 

3. 비트 연산자

3.1 비트 논리 연산자

기호	이름	동작 원리 (핵심)	예시 (A=1010, B=1100)	결과
&	AND	둘 다 1이어야만 1	1010 & 1100	1000 (8)
|	OR	하나라도 1이면 1	1010 | 1100	1110 (14)
^	XOR	두 비트가 서로 달라야 1	1010 ^ 1100	0110 (6)
~	NOT	비트 반전 (0은 1, 1은 0)	~1010	0101 (5)

 

3.2 비트 시프트(이동) 연산자

기호	이름	동작 원리 (빈자리 채우기)	수학적 효과	예시	결과
<<	Left Shift	지정한 수만큼 왼쪽으로 밀기 (빈자리는 0으로 채우기)	밀 때마다 곱하기 2	0011 (3) << 1	0110 (6)
>>	Right Shift	지정한 수만큼 오른쪽으로 밀기 (빈자리는 원래 부호로 채우기)	밀 때마다 나누기 2	0110 (6) >> 1	0011 (3)
>>>	Unsigned Right Shift	지정한 수만큼 오른쪽으로 밀기 (부호 상관없이 무조건 0으로 채우기)	양수 취급 (자바 전용)	-2 >>> 1	01111111 11111111 11111111 11111111 (2,147,483,647)

 

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) { // 받아올림(b)이 더 이상 없을 때까지 반복
            int sum = a ^ b; // 서로 달라야 1. 둘다 1일 경우에는 올려야해서 0이 됨
            int carry = (a & b) << 1; // 둘다 1일 경우에 하나 올림

            a = sum;
            b = carry;
        }

        return a;
    }
}

 

근본 코드도 기억해두기 :)

class Solution {
    public int getSum(int a, int b) {
        while(b != 0) { 
            int temp = a; // a 임시 저장해두기
            a = a ^ b; // a에는 합계 저장
            b = (temp & b) << 1; // b에는 받아올림 저장 
        }
        return a;
    }
}