LeetCode 명상: 횟수

이 항목에 대한 설명부터 시작하겠습니다.

양의 정수 n이 주어지면 이진 표현(해밍 가중치라고도 함)으로 설정된 비트 수를 반환하는 함수를 작성하세요.

예:

Input: n = 11
Output: 3

Explanation: The input binary string 1011 has a total of three set bits.

또는:

Input: n = 128
Output: 1

Explanation: The input binary string 10000000 has a total of one set bit.

또는:

Input: n = 2147483645
Output: 30

Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

---

이전 게시물의 장 소개에서 언급했듯이 설정 비트는 1의 값을 갖는 비트를 의미합니다.

그래서 우리가 해야 할 일은 1비트를 세는 것입니다.

한 가지 방법은 숫자를 문자열로 변환하고 1의 수만 세는 것입니다. 또는 이를 배열로 변환하고 0을 필터링하여 길이를 얻을 수 있습니다. 하지만 비트 조작을 사용할 수 있는 또 다른 접근 방식이 있습니다.

숫자가 0이 될 때까지 설정된 비트(값이 1인 비트)를 제거할 수 있습니다.

알아두면 좋은 점은 n - 1이 n의 가장 오른쪽에 있는 집합이 제거된 버전

이라는 점입니다.

예를 들어 n이 0010이면 n - 1은 000

1입니다.

또는 n이 0110이면 n - 1은 010

1입니다.

Note

It does not matter whether n - 1 introduces other 1s because we are doing the AND operation to count the set bits.
For example, if n is 0000, then n - 1 is 0111. Their AND will be 0000.
Or, if n is 0010, then n - 1 is 0001. The rightmost set bit of n is 0 in n - 1, and that's all that matters.

참고 우리는 설정된 비트를 계산하기 위해 AND 연산을 수행하기 때문에 n - 1이 다른 1을 도입하는지 여부는 중요하지 않습니다. 예를 들어 n이 0000이면 n - 1은 0111입니다. 해당 AND는 0000입니다.

또는 n이 0010이면 n - 1은 0001입니다. n의 가장 오른쪽 세트 비트는 0입니다. n - 1, 그게 전부입니다.

n에 1비트가 있는 동안 각 비트를 세면서 실행되는 루프를 만들 수 있습니다. 또한 매번 n과 1개(n & (n - 1))를 사용하여 AND

연산을 수행할 수 있습니다.

간단한 TypeScript 솔루션은 다음과 같습니다.

function hammingWeight(n: number): number {
  let result = 0;
  while (n > 0) {
    n &= (n - 1);
    result++;
  }

  return result;
}

Note

We are using the bitwise AND assignment operator to assign the value to n.

시간과 공간의 복잡성

시간복잡도는 $오(logn)$O(log n) — 모든 비트가 설정된 최악의 경우 루프를 실행합니다. $logn$로그 n 시간(숫자의 이진 표현의 비트 수 $n$n 될 것이다 $logn$로그 n ).

공간 복잡도는 일정합니다( $O(1)$O(1) ) 입력이 증가함에 따라 증가하는 추가 메모리 사용량이 없기 때문입니다.

---

다음으로 살펴볼 문제는 비트 계산입니다. 그때까지 즐거운 코딩하세요.

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