[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로 계산할 경우 부호비트라는 생각을 안하고 일반 비트로 생각하고 계산하는데, 이렇게 해야지만 (음수)+(음수), (음수)+(양수)의 계산을 할 때 오류가 생기지 않음.
댓글을 불러오는 중입니다.