리트코드 a+b c++ // 비트연산 덧셈구현방법

https://leetcode.com/problems/sum-of-two-integers/

1. 의사코드

sum(합, 캐리) :

기저사례 캐리가0

캐리가없는경우, a^b가 a+b이다.

캐리가있는경우 (a&b)가 0이아닌경우, 캐리는 (a&b) <<1 이다.

 합(a^b)에 캐리를 더해줘야한다.

캐리가 없을때까지

11(2진수)+11(2진수)을 코드로 돌려보면 이해가 쉬울것이다.

 

2. 전체코드

class Solution {
public:
    int getSum(int a, int b) {
        if(b==0) return a; //기저사례 : carry가 0

        int sum=a^b; //10 ^ 01 == 11, 둘다1인경우를 제외하고 덧셈완성 

        int carry=(a&b)<<1; //둘다1인경우 비트가있는경우, carry 계산해줘야함
        //ex) 11 + 10 -> 10<<1 == 100(carry)
        //하나라도 0이면, carry는 자동으로 0이됨.

        return getSum(sum,carry); //sum과 carry를 더해주면됨.
    }
};