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
+, - 연산자를 사용하지 않고 두 수의 합을 반환하라는 단순한 문제이다.
문제를 보자마자 학부 시절의 논리회로 과목에서 가산기를 만들었던 것이 생각났다. 이번 문제도 비슷하게 비트를 조작해 풀 수 있을 것 같았기 때문에 비슷한 접근 방식을 취해보았다.
먼저, 각 비트를 더했을 때 취해야 하는 동작을 생각해보았다. 비트를 더했을 때는, XOR 연산을 취해야 한다.
| 숫자 | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 (올림) |
그 후, 올림이 들어간 자릿수를 실제로 어떻게 올려주어야할 지 생각해보았는데 실제로 공책에 써보며 생각해보니 금방 감이 잡혔다. 결론은 AND 연산을 사용하고 반복해 결과를 얻어주는 것이었다.
- XOR 연산을 통해 단순히 더해주는 부분을 구한다.
- AND 연산을 통해 올림 연산을 해야하는 부분을 구한다.
- leftShift 연산을 한 번 해서 올려야 하는 자릿수를 맞춰준다.
- (0)번 연산한 부분과 (2)번 연산한 부분을 XOR, AND 연산을 통해 결과 값을 구하고, AND 연산을 통해서 올려주어야 할 값이 추가로 있다면 반복해서 진행해 결과를 구한다.
111(7), 101(5)를 더하는 것으로 예를 들어보겠다. (부호 비트는 제외했습니다)
0111
0101
---
0. XOR 연산 값: 0010
1. AND 연산 값: 0101
2. AND 연산 값 1번 leftShift 취해준 값: 1010
---
0010 // 위의 (0)번 연산 값
1010 // 위의 (2)번 연산 값
---
0. XOR 연산 값: 1000
1. AND 연산 값: 0010
2. AND 연산 값 1번 leftShift 취해준 값: 0100
---
1000 // 위의 (0)번 연산 값
0100 // 위의 (2)번 연산 값
---
0. XOR 연산 값: 1100
1. AND 연산 값: 0000
AND 연산 값이 없으므로 반복문 마무리. 계산 완료 이번 문제는 JavaScript로 풀었고, 구현 한 번만에 풀 수 있었다.
/**
* @param {number} a
* @param {number} b
* @return {number}
*/
var getSum = function(a, b) {
return bitwiseAdd(a, b);
};
var bitwiseAdd = function(a, b) {
while (b != 0) {
const xorSum = a ^ b;
const carry = (a & b) << 1;
a = xorSum;
b = carry;
}
return a;
};
결과는 아래와 같다.
생각해보니 xorSum 변수를 저장하지 않아도 풀 수 있을 것 같아서 조금 더 최적화할 수 있었다. (메모리 사용량 최적화)
/**
* @param {number} a
* @param {number} b
* @return {number}
*/
var getSum = function(a, b) {
return bitwiseAdd(a, b);
};
var bitwiseAdd = function(a, b) {
while (b != 0) {
const carry = (a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
};
문제를 풀며 궁금했던 점
문제를 푼 후 여러 가지 솔루션들을 보고 있었는데 역시 + 연산자를 사용해 푼 사람이 있었다. 그런데 런타임이 45ms 이상으로 분포되어 있길래 '??? 자바스크립트 + 연산자도 최적화를 잘 해놓았을 것 같은데 왜 이 경우에는 런타임이 훨씬 더 걸리는거지?' 라고 생각해 간단히 테스트해보았다.
a와 b를 1천만번씩 더하는 예제 코드를 작성해 확인했고, 결과를 보면 역시 + 연산자를 사용한 것이 빨랐다. (위의 문제는 작은 수에 대해 테스트했기 때문에 이런 결과가 나오지 않았나 싶다)
Plus Operator: 6.242ms
Bitwise Add: 23.961ms(예제 코드)
const a = 111111111;
const b = 111111111;
// 반복 횟수
const iterations = 1e7; // 10,000,000번 반복
var bitwiseAdd = function (a, b) {
while (b != 0) {
const carry = (a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
};
// + 연산자 성능 테스트
console.time("Plus Operator");
for (let i = 0; i < iterations; i++) {
const result = a + b;
}
console.timeEnd("Plus Operator");
// bitwiseAdd 함수 성능 테스트
console.time("Bitwise Add");
for (let i = 0; i < iterations; i++) {
const result = bitwiseAdd(a, b);
}
console.timeEnd("Bitwise Add");
이번 주 문제는 평소에 자주 사용하지 않아 익숙하지 않은 비트 연산자에 대해서 많이 생각해보고 구현해볼 수 있어서 재미있었다.
틀린 점이나 궁금한 점이 있으시다면 댓글이나 연락 부탁드리겠습니다. 감사합니다.
참고
비트 연산자를 사용할 때 연산하기 전 64비트 부동 소숫점을 가진 숫자를 32비트 정수로 변환하고 연산 후 다시 32비트 정수를 64비트 부동 소숫점을 가진 숫자로 변환하기 때문에 예상치 못한 정확도 손실이 있을 수 있다. 비트 연산자를 사용할 때는 항상 이 점을 유의하면 좋을 것 같다.
