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，並取得其長度。但是，還有另一種方法可以使用位元操作。

我們可以刪除設定的位元（值為 1 的位元），直到數字變成 0。

需要知道的一件好事是 n - 1 是 n 的最右邊集合刪除版本。

例如，如果 n 為 0010，則 n - 1 為 0001。

或者，如果 n 為 0110，則 n - 1 為 0101。

注意 標題> n - 1 是否引入其他 1 並不重要，因為我們正在執行 AND 運算來計算設定的位元。

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 減去 (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.

時間和空間複雜度

時間複雜度是，我認為， $O(logn)$ >O(log n) — 在最壞的情況下，當所有位元都已設定時，我們將運行循環 $logg$登入 次（數字的二進位表示中的位數 $n$nn > 將 $lo\text{g} 登入n$登入

). 空間複雜度將是恆定的（ $O\mathrm{(}11$)O(1)

---

O(1)

）因為沒有額外的記憶體使用量會隨著輸入的增加而增加。 我們要研究的下一個問題是計數位。在那之前，祝您編碼愉快。

以上是LeetCode 冥想：其數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！