1 Star 0 Fork 1.5K

沐瑶 / LearningNotes

forked from 陌溪 / LearningNotes 
Create your Gitee Account
Explore and code with more than 6 million developers,Free private repositories !:)
Sign up
Clone or download
README.md 3.90 KB
Copy Edit Web IDE Raw Blame History
陌溪 authored 2020-04-27 23:02 . add blog

二进制中的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,

~5

  • (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.
    

Comment ( 0 )

Sign in for post a comment

1
https://gitee.com/muyao_vip/LearningNotes.git
git@gitee.com:muyao_vip/LearningNotes.git
muyao_vip
LearningNotes
LearningNotes
master

Search

102255 3a0e046c 1850385 102255 7aaa926c 1850385