位1的个数

1. 题目描述

编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

示例 1：

输入：n = 11 输出：3 解释：输入的二进制串 1011 中，共有 3 个设置位。 示例 2：

输入：n = 128 输出：1 解释：输入的二进制串 10000000 中，共有 1 个设置位。 示例 3：

输入：n = 2147483645 输出：30 解释：输入的二进制串 11111111111111111111111111111101 中，共有 30 个设置位。

2. 分析

• 逐位判断 根据 与运算 定义，设二进制数字 n ，则有：

若 n&1=0 ，则 n 二进制 最右一位 为 0 。 若 n&1=1 ，则 n 二进制 最右一位 为 1 。 根据以上特点，考虑以下 循环判断 ：

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

• 使用 n&(n-1) (n−1) 作用： 二进制数字 n 最右边的 1 变成 0 ，此 1 右边的 0 都变成 1 。

n&(n−1) 作用： 二进制数字 n 最右边的 1 变成 0 ，其余不变。

3. 代码

#逐位判断
def hammingWeight(n):
    res = 0
    while n:
        res += n & 1
        n >>= 1
    return res

if __name__ == '__main__':
    n=5
    print(hammingWeight(n))

# 使用n&(n-1)
def hammingWeight(n) -> int:
    res = 0
    while n:
        res += 1
        n &= n - 1
    return res


if __name__ == '__main__':
    n=5
    print(hammingWeight(n))