本文共 1065 字，大约阅读时间需要 3 分钟。

请实现一个函数，输入一个整数（以二进制串形式），输出 该数二进制表示中 1 的个数。

例如，把 9 表示成二进制是 1001，有 2 位是 1。

因此，如果输入 9，则该函数输出 2。

【解题思路】

• 若 n&1=0 ，则 n 二进制 最右一位 为 0 ；
• 若 n&1=1 ，则 n 二进制 最右一位 为 1 。

根据以上特点，考虑以下 循环判断 ：

1. 判断 n 最右一位是否为 1 ，根据结果计数。
2. 将 n 右移一位（本题要求把数字 n 看作无符号数，因此使用 无符号右移 操作）。

【算法流程】

1. 初始化数量统计变量 count=0 。
2. 循环逐位判断： 当 n = 0 时跳出。
   1. res += n & 1 ： 若 n&1=1 ，则统计数 res 加一。
   2. n >>= 1 ： 将二进制数字 n 无符号右移一位（ Java 中无符号右移为 “>>>” ） 。
3. 返回统计数量 count 。

作者：jyd

链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/solution/mian-shi-ti-15-er-jin-zhi-zhong-1de-ge-shu-wei-yun/

class Solution:    def hammingWeight(self, n: int) -> int:        count = 0   # 计数        for i in range(32): #             count += n&1            n>>=1        return count

• 复杂度分析

  • 时间复杂度O(log₂n) ： 此算法循环内部仅有 移位、与、加 等基本运算，占用 O(1) ；逐位判断需循环 log₂n次，逐位判断需循环 log₂n次，其中log₂n 代表数字 n 最高位 1 的所在位数（例如 log₂4 = 2, log₂16 = 4）。

  此处的2是 每一位可取【0、1】两种选择，设 循环 t 次，则2^t = n ，推出 t = log₂n 次

  【扩展】：

  若是八进制，则每一位可取【0、1、2、3、4、5、6、7】八种选择，则 t = log₈n 次

  t = log₂n / log₂8 = 1/3 * log₂n，也即O(log₂n)

  • 空间复杂度O(1)：变量 res 使用常数大小额外空间。

该题是 思路3中的预备工作

转载地址：http://hfjii.baihongyu.com/