钉钉日报

二进制中1的个数

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。

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

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

示例 1：

输入：11

输出：3

解释：输入的二进制串 00000000000000000000000000001011中，共有三位为 ‘1’。

示例 2：

输入：128

输出：1

解释：输入的二进制串 00000000000000000000000010000000中，共有一位为 ‘1’。

示例 3：

输入：4294967293

输出：31

解释：输入的二进制串 11111111111111111111111111111101中，共有 31 位为 ‘1’。

------------------------------------------------------------------

方法一：

def NumberOf1(n):
    if n >= 0:
        return bin(n).count('1')
    # bin函数： bin返回一个整数的二进制字符串，以0b开头，
    # bin(10) '0b1010'  bin(-10)  '-0b1010'
    # count函数 返回字符串当中非重叠的字符串的个数，
    else:
        return bin(2 ** 32 + n).count('1')
    #如果一个数为负数，那么2**32 + n 然后再用bin返回的就是它的补码形式。 补码+源码=2**32

print(NumberOf1(11))
print(NumberOf1(128))
print(NumberOf1(4294967293))

'''3
1
31'''

------------------------------------------------------------------

方法二：

from collections import Counter

def int_Conter(n):
    bin_n = bin(n)                  #先转换为二进制数
    dict_bin = Counter(bin_n)       #此函数输出的是字典，key为出现的数字，value为出现的次数
    for k, v in dict_bin.items():    #将key为1的值输出
        if k == '1':
            return v
print(int_Conter(11))
print(int_Conter(128))
print(int_Conter(4294967293))

------------------------------------------------------------------

方法三：

def int_count(n):
    bin_n = bin(n)                     #先转换为二进制数
    num = str(bin_n).count('1')        #将字符串进行计数
    return num

print(int_count(11))
print(int_count(128))
print(int_count(4294967293))

------------------------------------------------------------------

方法四：

def count_1(n):
    return n and (n & 1) + count_1(n >> 1)
print(count_1(11))
print(count_1(4294967293))

------------------------------------------------------------------

方法五：

def count_1(n):
    return bin(n).count('1')
print(count_1(11))
print(count_1(128))

------------------------------------------------------------------

方法六：

def onecount2(nn):
    countnum = 0
    while nn:
        nn = nn & (nn - 1)
        countnum += 1
    print(countnum)


nn = int(input("请输入十进制数:"))
onecount2(nn)

------------------------------------------------------------------

方法六（翻版–from 黄毅）：

def onecount2(nn):
    countnum = 0
    while nn:
        print(nn, nn-1)
        print(bin(nn))
        print(bin(nn-1))
        nn = nn & (nn - 1)
        print("与运算结果:", bin(nn))
        countnum += 1
    print(countnum)

onecount2(58)

1. 首先创建一个新的整数为原始整数减去1, 即为’00100001000011’.

2. 将新创建的数字与原始数字进行按位与运算,即00100001000100 & 00100001000011 = 00100001000000,此时已经移除了最右边的1

3. 将新得到的数字赋值给原始变量,判断是否为0, 不为0说明其中还有1, 再进行前两步的循环操作,每次循环计数器加1

4. 循环结束时,变量为0,其中的1已经全部消除,此时的循环次数就是原始整数中1的个数

5. 返回循环次数

| & | 按位与运算符：参与运算的两个值,如果两个相应位都为1,则该位的结果为1,否则为0

11的二进制为1011,10的二进制为1010,(11 & 10)的运算结果为1010,输出结果 10

已知11小于2的4次方，大于2的3次方,则11的二进制中1的个数小于等于4

将1011看做字符串s,s[4]=1,s[3]=0,s[2]=1,s[1]=1

每次的nn&(nn-1)都是在向前一位做运算，算这一位是0还是1

相对好理解的方法是，我们可以逆向来看运算结果

首先59的二进制的第六位(32)肯定是1,剩下27 1

27>16,所以第五位是1，剩下11 2

11>8,第四位是1，剩下3 3

4>3>2,第二位是1，剩下1 4

1=1，第一位是1 剩下0 5

上述代码只是变相运用了该过程

from 刘林

本文地址：https://blog.csdn.net/jasbjbd/article/details/107464504