Celenort
Conciencia
게시물 253
오늘 0
전체 0
A site about logging consciousness

[LeetCode] Sum of Two Integers

Sum of Two Integers

Category: Binary

Deadline: 2nd week (1/7 - 1/15)

Difficulty: Medium

Github: https://github.com/iamseokhyun/2022-algorithm-study/tree/master/binary/SumofTwoIntegers/

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

Problem

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

Solution

public class Solution
{
    public int GetSum(int e, int d)
    {
        int c = 0;
        uint ans = 0;
        int i = 1;
        uint a = (uint)e;
        uint b = (uint)d;
        bool first = true;

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

        while (a != 0 || b != 0)
        {
            if (c == 0)
            {
                if (Convert.ToBoolean((a % 2) & (b % 2)))
                {
                    c = 1;
                }
                else
                {
                    c = 0;
                }

                if (first)
                {
                    ans = ans | ((a % 2) ^ (b % 2));
                    first = false;
                    i = i << 1;
                }
                else
                {
                    ans = (uint)(ans | ((a % 2) ^ (b % 2)) * i);
                    i = i << 1;
                }
            }
            else
            {
                ans = (uint)(ans | ((a % 2) ^ (b % 2) ^ c) * i);
                i = i << 1;

                if (Convert.ToBoolean(((a % 2) & (b % 2)) | ((c) & (b % 2)) | ((a % 2) & (c))))
                {
                    c = 1;
                }
                else
                {
                    c = 0;
                }
            }

            a = a >> 1;
            b = b >> 1;
        }

        if (c == 1)
        {
            ans = (uint)(ans | i);
        }

        return (int)ans;
    }
}

Comment

  • Line 10 - 17 : 입력값중 0이 있다면 그 반댓값을 반환.
  • Line 05 - 10 : 입력값을 uint(unsigned int)로 하여 a, b에 저장. 받아올림값 c = 0으로 지정, i는 자릿수 연산자 2^x만 들어감.
  • Line 18 - 41 : a, b 모두가 0이 될 때까지 다음을 실행.
  • c가 0이라면(직전 자릿수 받아올림이 0이라면), a, b를 2로 나눈 나머지 (마지막 자릿수)의 &가 1이면 받아올림은 1이며, 그렇지 않은 경우 받아올림을 0으로 설정함.
  • 각 수의 마지막 자릿수의 xor값을 i(자릿수 연산자)와 곱하여 ans에 and(&)로 연결함. 각 연산에서 각각 서로 다른 자릿수 하나에만 접근하므로 and로 연결하는 것이 옳음.
  • 단, 첫 번째로 while문을 돌 때에는 i의 기본값이 1이기 때문에 이를 곱하여주면 안됨. 즉 첫번째만 bool first로 설정하여 따로 해결.
  • Line 42 - 53 : 앞선 while 문에 이어 a, b의 마지막 자릿수 뿐만이 아닌 받아올림까지 xor 연산하여 ans에 대입.
  • a, b, c 의 순서쌍이 (1,1,0) 일 때만 받아올림이 일어나므로 이를 적용하여 받아올림 계산.
  • Line 54 - 55 : 다시 while문을 돌기 위해 연산이 끝난 a와 b를 2로 나누어 줌.
  • Line 57 - 60 : 모두 계산한 이후 마지막 받아올림이 남아있다면 이를 ans에 더해주어야 함.
  • Line 61 : 다시 계산한 값을 int로 바꾸어 출력해줌.
  • int가 아닌 uint로 바꾸어 계산한 이유 : int의 경우 8비트에 첫번째 0과 1로 부호를 표시하는데, 이로 인해 계산이 꼬일 수 있음. uint로 계산할 경우 부호비트라는 생각을 안하고 일반 비트로 생각하고 계산하는데, 이렇게 해야지만 (음수)+(음수), (음수)+(양수)의 계산을 할 때 오류가 생기지 않음.
댓글을 불러오는 중입니다.