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) — 在最坏的情况下，当所有位都已设置时，我们将运行循环 $logn$登录 次（数字的二进制表示中的位数 $n$n 将 $logn$登录 ).

空间复杂度将是恒定的（ $O(1)$O(1) ）因为没有额外的内存使用量会随着输入的增加而增加。

---

我们要研究的下一个问题是计数位。在那之前，祝您编码愉快。

以上是LeetCode 冥想：其数量的详细内容。更多信息请关注PHP中文网其他相关文章！