LeetCode 명상: 두 정수의 합

Sum of Two Integers에 대한 설명은 매우 간단합니다.

두 개의 정수 a와 b가 주어지면 연산자 및 -를 사용하지 않고 두 정수의 합을 반환합니다.

예:

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

또는:

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

---

이 시리즈의 마지막 문제에서는 우리가 즐겨 사용하는 더하기 연산자 대신 비트 조작을 사용하여 두 개의 정수를 추가하는 것으로 마무리하겠습니다.

1 또는 0만 될 수 있는 두 비트를 추가해도 결과가 많이 달라지지는 않습니다.
1과 0(또는 0과 1)인 두 비트를 더하면 결과는 1이 됩니다. 두 개의 0 비트를 더하면 결과는 0이 됩니다. 그러나 두 개의 1을 더하면 결과는 0이 됩니다. 비트, carry가 있습니다. 즉, 출력에 0을 써야 하지만 또한 a를 전달합니다. 1.

예를 들어 2와 3을 더하면 5가 되고 연산 중에 캐리 값을 갖게 됩니다.

캐리 값을 고려하지 않고 두 비트를 추가한 후 얻어야 하는 출력은 XOR 연산 후의 출력과 매우 유사합니다. 서로 다른 비트(0과 1 또는 1과 0)가 있으면 출력은 1이 되고, 그렇지 않으면 0(0과 0을 추가하거나)이 됩니다. , 1과 1).

그래서 XOR 연산이 출력에 도움이 될 수 있습니다.

캐리는 어떻습니까?

두 비트가 모두 1인 경우에만 캐리 값이 있습니다. 이는 AND 연산처럼 보입니다.

따라서 AND 연산이 캐리에 도움이 될 수 있습니다.

또한 캐리 값이 왼쪽으로 이동하므로 편리한 왼쪽 시프트 연산자도 있습니다.

따라서 출력과 캐리는 다음과 같습니다.

let output = a ^ b;
let carry = (a & b) << 1;

우리가 가지고 있는 두 값을 계속 수정하고 캐리 값이 더 이상 남지 않을 때까지 계속할 수 있습니다. a를 출력으로, b를 캐리로 수정하고, 마지막에 최종 출력을 보유하는 return a를 수정할 수 있습니다.

전체적으로 최종 솔루션은 TypeScript에서 다음과 같습니다.

function getSum(a: number, b: number): number {
  // while we still have carry
  while (b !== 0) {
    let output = a ^ b;
    let carry = (a & b) << 1;
    a = output;
    b = carry;
  }

  return a;
}

시간과 공간의 복잡성

a와 b는 모두 상수 값이고 입력에 비례하여 크기가 커지는 추가 데이터 구조도 필요하지 않으므로 시간과 공간의 복잡성이 모두 일정합니다. $O(1)$O(1) .

---

그리고 이것이 LeetCode Meditations 시리즈의 마지막 문제입니다! 다음 포스팅에서 결론으로 ​​마무리하도록 하겠습니다. 그때까지 즐거운 코딩하세요.

위 내용은 LeetCode 명상: 두 정수의 합의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!