写法一,移位&1运算
解释:
十进制 -> 二进制:
2
-> 10
2&1 = 0
的解释:
10&1
: 判断二进制数10的最后一位是否为1 -> 本质上是比较10&01
= 0
-> 最后一位不为1
10>>1
: 二进制数10
右移一位 -> 10
->1
1&1
: -> True
-> 最后一位为1
1>>1
: -> 0
3&1 = 1
- >11&01 = 01
-> 1
-> 3的二进制表达中最后一位为1
15&1 = 1
- >1111&0001 = 0001
-> 1
-> 15的二进制表达中最后一位为1
n = int(input())
a = list(map(int,input().split()))
def lowbit(x):
res = 0
while(x):
if(x&1):res+=1
x = x>>1
return res
b = [lowbit(i) for i in a]
for i in b:
print(i,end = ' ')
写法2 补码运算
二进制表达中 , -x
= x取反+1
所以x&-x
相当于将最后一位1位置后面的数字返回
例子:
a = 1000100
a
取反 = 0111011
a
取反再+1 = 0111100
那么a&-a
相当于1000100&0111100
,也就是0000100
即a&-a = 100
那么我们就可以每次把这个数字减去lowbit(n),直到n=0为止,总共减了几次就说明该数的二进制表达中存在多少个1
.
n = int(input())
a = list(map(int,input().split()))
def lowbit(x):
return x&-x
for i in range(n):
x = a[i]
res = 0
while(x):
t = lowbit(x)
x-=t
res+=1
print(res,end = ' ')
写法三 python自带进制转换,将转换后的数字换为字符串,count1字符的数量即可。
n = int(input())
b = list(map(int,input().split()))
for i in b:
t = str(bin(i))[2:]
s = t.count('1')
print(s,end = ' ')