二进制中的1的个数

2022-08-11
浏览 (604)

二进制中的1的个数

描述

来源：https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8

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

补码

正数不变，负数就是它的正数的反码 + 1
一个负整数（或原码）与其补数（或补码）相加，和为模。
对一个整数的补码再求补码，等于该整数自身。
补码的正零与负零表示方法相同

-2 的补码：

-2 的二进制为 1 0 0 0 0 …….0 0 0 1 0 ,

-2 的反码为： 1 1 1 1 1 …….1 1 1 0 1

-2 的补码为： 1 1 1 1 1 …….1 1 1 1 0

对于任意一个数n：

n = n & 0xFFFFFFFF

按位取反 ~

~，用法只有一个那就是按位取反，需要注意的是：

~ 的按位取反，包括符号位
正数各位取反变为负数，显示时转化为其补码
负数本身需要先转换为补码（符号位不变，各位取反再加 1），再对其补码进行各位去反

1. ~5

5 的二进制为 0101，

（1）各位取反，1010
（2）变为负数，转化为其补码形式（符号位保持不变），各位取反 1（1101），再加1（1110），也即 -6

>> ~5
>> -6

2. ~(-5)

-5 因为是负数，存储时存储的是其补码：

-5 的补码是：1011，
~(-5)将其各位取反（包括符号位），也即 0100（4）

>> ~(-5)
>> 4

代码

# 第一种
class Solution:
    def NumberOf1(self, n):
        # 这一步是求补码的
        n = n & 0xFFFFFFFF
        count = 0
        for c in str(bin(n)):
            if c == "1":
                count +=1
        return count

    def NumberOf2(self, n):
        # 这一步是求补码的
        n = n & 0xFFFFFFFF
        count = 0
        for i in range(32):
            mask = 1 << i
            if n & mask != 0:
                count += 1
        return count

#第二种：
class Solution:           
    def NumberOf1(self, n):
        # write code here
        #补码：正数不变，负数是它的正数的反码 + 1
        # -2 补码： -2 的 1 0000.。。000010，
        #                 1 1111.。。111101 + 1
        #-2 的补码就是    1 1111.。。111110
        #把输入的正数n转化为二进制的数，并把0b 替换掉，计算1的数量，如果输入的值不是正数的话
        #一个负整数（或原码）与其补数（或补码）相加，和为模。2 的32 次方 是模。
        #那么就是 2 的32 次方 然后 + n  这是在取一个负数的补码  就相当于  n & 0xffffffff
        #然后计算 这个数里面 1 的 数量
        return bin(n).replace("0b", "").count("1") if n >= 0 else bin(2 ** 32 + n).replace("0b", "").count("1")

    
#第三种：
# -*- coding:utf-8 -*-
class Solution2:
    def NumberOf1(self, n):
        # write code here
        # 1 出现的次数为0 次
        count = 0
        #判断 这个数 n 是不是负数，如果是负数的话 求其补码：
        if n < 0:
            n = n & 0xffffffff
        #如果这个数不是0 的话，那么它在二进制的表示中至少有一位是1，所以一开始我们赋值 count +=1.
        while n:
            count += 1
            #把一个整数先减去1，再和原整数做与运算，会把该整数最右边的1 变从成0，那么一个二进制中有多少个1，就可以进行多少次这样的操作。
            n = (n - 1) & n
        return count
    """
    例如：一个二进制1100， 它的第二位 是从最右边数起的一个1，减去一个1后，第二位变成0，它后面的两位0变成1，而前面的1保持不变，因此结果是1011.
    那把 这个整数 和它 减去1 的结果  做一个按位 与运算，相当于 把 最右边的 1 变成 0,。
    1011 和 1100 做 按位与 运算  1100 & 1011  结果为  1000，那么刚好是我们 要得到 将最右边的1 变成0 的结果   1000.