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; }
❓
延伸问答
如何计算正整数n的二进制表示中1的数量？
可以通过字符串计数或位操作实现，位操作方法是使用循环和与运算（n & (n - 1)）逐个去掉1，直到n为0。
给定n=11，输出的汉明重量是多少？
输出为3，因为二进制表示为1011，有三个1。
位操作方法的时间复杂度和空间复杂度分别是多少？
时间复杂度为O(log n)，空间复杂度为O(1)。
如何使用TypeScript实现汉明重量的计算？
可以使用以下代码：function hammingWeight(n: number): number { let result = 0; while (n > 0) { n &= (n - 1); result++; } return result; }
n=128时，汉明重量的输出是什么？
输出为1，因为二进制表示为10000000，有一个1。
汉明重量的定义是什么？
汉明重量是指一个数的二进制表示中1的数量。
➡️
