代码拉取完成,页面将自动刷新
同步操作将从 陌溪/LearningNotes 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
来源: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
~,用法只有一个那就是按位取反,需要注意的是:
5 的二进制为 0101,
~5
>> ~5
>> -6
-5 因为是负数,存储时存储的是其补码:
>> ~(-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.
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。