11 二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

示例：

输入: 5  (二进制: 101)
输出: 2

输入: 7  (二进制: 111)
输出: 3

输入: -1 (补码: 全1)
输出: 32

解题思路

方法一：逐位检查

核心思想：检查每一位是否为1，通过右移和与运算实现。

方法二：n & (n-1) 技巧

核心思想：n & (n-1) 的作用是消除n的二进制表示中最右边的1。

• 例如：n = 1010, n-1 = 1001, n & (n-1) = 1000
• 每次操作消掉一个1，统计操作次数即可

时间复杂度：O(k)，k为二进制中1的个数 空间复杂度：O(1)

Python 实现

def number_of_1(n):
    """
    使用 n & (n-1) 技巧统计1的个数

    Args:
        n: 整数

    Returns:
        int: 二进制中1的个数
    """
    count = 0
    while n:
        n = n & (n - 1)
        count += 1
    return count


# 方法一：逐位检查
def number_of_1_shift(n):
    """
    逐位检查法
    """
    count = 0
    flag = 1
    while flag:
        if n & flag:
            count += 1
        flag = flag << 1
    return count


# Python内置函数
def number_of_1_bin(n):
    """
    使用Python内置函数
    """
    # 处理负数（补码表示）
    if n < 0:
        n = n & 0xFFFFFFFF
    return bin(n).count('1')


# 测试代码
if __name__ == "__main__":
    test_cases = [5, 7, 8, 15, -1, 0]

    for n in test_cases:
        print(f"n={n}: {number_of_1(n)}个1")

# 输出:
# n=5: 2个1
# n=7: 3个1
# n=8: 1个1
# n=15: 4个1
# n=-1: 32个1
# n=0: 0个1

图解

n & (n-1) 技巧:
n = 1010 (10)
n-1 = 1001 (9)
n & (n-1) = 1000 (8)  → 消掉最右边的1

n = 1100 (12)
n-1 = 1011 (11)
n & (n-1) = 1000 (8)  → 消掉最右边的1

统计过程示例: n = 13 (1101)
第1次: n = 1101 & 1100 = 1100, count=1
第2次: n = 1100 & 1011 = 1000, count=2
第3次: n = 1000 & 0111 = 0000, count=3
循环结束，共3个1