JZ15 二进制中1的个数

发表于 分类于 本文字数： 344 阅读时长 ≈ 1 分钟

JZ15 二进制中1的个数

描述

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

数据范围：$−2^{31}<=n<=2^{31}−1$

即范围为:$−2147483648<=n<=2147483647$

示例1

1
2
3
输入：10
返回值：2
说明：十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。

示例2

1
2
3
输入：-1
返回值：32
说明：负数使用补码表示 ，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1

题解

首先将数字转换为无符号数，具体的转换方法就是使用0xFFFFFFFF和原数字做与运算，此后创建一个掩码，其中只有第i位是1，逐个检查该位是否是1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def NumberOf1(self , n: int) -> int:
        n_unsigned = n & 0xFFFFFFFF
        count = 0
        for i in range(32):
            if n_unsigned & (1 << i):
                count += 1
        return count

Brain Kernighan算法

1
2
3
4
5
6
def count_ones_brian_kernighan(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

详解：

1
2
3
4
n-1				使得除了最低位的1变成0，且最低位右侧的0全部变成1(向最低位借位)
n & n-1				使得最低位左侧不变，右侧的1恢复成0
最终实现删除最低位的1
不断重复直到所有1变为0结束