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 つの方法は、数値を文字列に変換し、単に 1 を数えることです。または、それを配列に変換して 0 を除外し、その長さを取得することもできます。ただし、ビット操作を使用できる別のアプローチもあります。

数値が 0 になるまで、設定されたビット (値 1 を持つビット) を削除できます。

知っておくべきことは、n - 1 は n の右端のセット削除バージョンであるということです。

たとえば、n が 0010 の場合、n - 1 は 0001 となります。

または、n が 0110 の場合、n - 1 は 0101 となります。

メモ セットされたビットをカウントするために AND 演算を行っているため、n - 1 に他の 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.

たとえば、n が 0000 の場合、n - 1 は 0111 です。それらの AND は 0000 になります。 または、n が 0010 の場合、n - 1 は 0001 です。n の右端の設定ビットは 0 です。 n - 1、重要なのはそれだけです。

n に 1 ビットがある限り実行され、各ビットをカウントしながら実行するループを作成できます。 また、毎回、n から 1 を引いた値で AND

演算を実行できます (n & (n - 1))。

単純な 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.

時間と空間の複雑さ

時間計算量は次のとおりだと思います $O(logn)$O(log n) — すべてのビットが設定されている最悪の場合、ループを実行します。 $logn$ログ 倍 (数値の 2 進数表現のビット数) $n$n になるだろう $logn$ログ ).

空間の複雑さは一定になります ( $O(1)$O(1) ) 入力が増加しても追加のメモリ使用量が増加することがないためです。

---

次の問題はビットのカウントです。それまで、コーディングを楽しんでください。

以上がLeetCode 瞑想: その数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。