DEV Community ·

LeetCode 思考：1的数量

💡 原文英文，约500词，阅读约需2分钟。

📝

内容提要

编写一个函数，计算正整数n的二进制表示中1的数量（汉明重量）。可以通过字符串计数或位操作实现，位操作方法使用循环和与运算（n & (n - 1)）逐个去掉1，直到n为0。时间复杂度为O(log n)，空间复杂度为O(1)。

🎯

编写一个函数，计算正整数n的二进制表示中1的数量（汉明重量）。
可以通过字符串计数或位操作实现，位操作方法使用循环和与运算（n & (n - 1)）逐个去掉1，直到n为0。
示例输入：n = 11，输出：3，二进制表示为1011，有三个1。
示例输入：n = 128，输出：1，二进制表示为10000000，有一个1。
示例输入：n = 2147483645，输出：30，二进制表示为1111111111111111111111111111101，有三十个1。
可以使用位操作逐个去掉1，直到n为0，时间复杂度为O(log n)，空间复杂度为O(1)。
TypeScript示例代码：function hammingWeight(n: number): number { let result = 0; while (n > 0) { n &= (n - 1); result++; } return result; }

🔎

汉明重量在计算机科学中有广泛应用，尤其是在数据压缩、错误检测和纠正等领域。了解如何计算一个数的汉明重量，可以帮助开发者优化算法，提升程序性能。

使用位操作计算汉明重量相比于字符串计数具有更高的效率。位操作的时间复杂度为O(log n)，而字符串方法可能需要更多的内存和时间，尤其在处理大数时，位操作的优势更加明显。

在使用位操作时，确保理解n & (n - 1)的原理，这一操作会逐步去掉最右边的1位。错误的理解可能导致算法实现不当，影响最终结果。

❓

可以通过字符串计数或位操作实现，位操作方法是使用循环和与运算（n & (n - 1)）逐个去掉1，直到n为0。

输出为3，因为二进制表示为1011，有三个1。

时间复杂度为O(log n)，空间复杂度为O(1)。

可以使用以下代码：function hammingWeight(n: number): number { let result = 0; while (n > 0) { n &= (n - 1); result++; } return result; }

输出为1，因为二进制表示为10000000，有一个1。

汉明重量是指一个数的二进制表示中1的数量。

🏷️