题目描述
给定一个长度为n的数列,请你求出数列中每个数的二进制表示中1的个数。
输入格式
第一行包含整数n。
第二行包含n个整数,表示整个数列。
输出格式
共一行,包含n个整数,其中的第 i 个数表示数列中的第 i 个数的二进制表示中1的个数。
数据范围
1≤n≤100000,
0≤数列中元素的值≤109
输入样例:
5
1 2 3 4 5
输出样例:
1 1 2 1 2
观众老爷们,如果本思路对您有帮助,求关注一波~~~
思路
先了解原码 补码 反码
原码:是最简单的机器数表示法。用最高位表示符号位,‘1’表示负号,‘0’表示正号。其他位存放该数的二进制的绝对值
举例
1010 : 最高位为‘1’,表示这是一个负数,其他三位为‘010’,
即(0*2^2)+(1*2^1)+(0*2^0)=2(‘^’表示幂运算符)
所以1010表示十进制数(-2)
同理 0010表示十进制数(2)
0001+0010=0011 (1+2=3)ok
0000+1000=1000 (+0+(-0)=-0) ok
0001+1001=1010 (1+(-1)=-2)no
由此引出了反码的概念来解决1 + -1 = -2的问题
反码:正数的反码还是等于原码,负数的反码就是他的原码除符号位外,按位取反。
举例
若以带符号位的四位二进制数为例:
3是正数,反码与原码相同,则可以表示为0011
-3的原码是1011,符号位保持不变,低三位(011)按位取反得(100)所以-3的反码为1100
0001(1 )+1110 (- 1)=1111(-7)no 正确答案为0
1110(-1)+1101(-2)=1011(-4)no 正确答案为-3
1110(-1)+1100(-3)=1010(-5)no 正确答案为-4
细心的你可能发现,除了第一个,其他计算错误的结果差值只是相差了1
由此引出了补码的概念来解决问题
补码:正数的补码等于他的原码, 负数的补码等于反码+1。也等于正数反码+1。
可能有小伙伴疑惑为什么 0001(1 )+1110 (- 1)=1111(-7)no 正确答案为0
如果这个+1不是会错误吗??
哈哈,显然不是
机器码的位数在操作系统中是固定位,假设只有4位
源码 1 : 0001 -1:1001
补码 1 :0001 -1:1110 + 1 = 1111
补码相加 1 + -1 = 0001 + 1111 = 10000,因为保留4位,所以最终结果为0000
nice~~完美
负数的补码等于反码+1,也等于正数反码+1。
1. -1 :1001 -> 1111
2. -1 : (1: 0001)的反码 1110 + 1 -> 1111
进入正题
二进制中1的个数,
本题是通过找出x的二进制位中最末尾出现的1的位置,用二进制表示出来
假设 x = 9 即 0 1001
有前面只是的铺垫
-x = ~x + 1即1 0111 =>1 0110 + 1 =1 0111
x & -x
0 1001
& 1 0111
————————————
0 0001
用x - (x&-x) = 1000,这样我们即得到了一个1,同时将该1的位置从数x中去除
int lowbit(int x){
return x & -x;
//-x = ~x + 1 //(x取反加1)
}
java
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while(n -- != 0){
int x = sc.nextInt();
int res = 0;
while(x != 0){
x -= lowbit(x);
res ++;
}
System.out.print(res + " ");
}
}
public static int lowbit(int x){
return x & -x;
}
}
python
def lowbit(x):
return x & -x;
def main():
n = int(input())
x = list(map(int, input().split(" ")))
for i in range(len(x)):
v = x[i]
res = 0
while(v != 0):
v -= lowbit(v)
res += 1
print(res, end=" ")
main()
c++
#include <iostream>
using namespace std;
int lowbit(int x){
return x & -x;
//-x = ~x + 1 //(x取反加1)
}
int main(){
int n;
cin >> n;
while(n --){
int x;
cin >> x;
int res = 0;
while(x) {
x -= lowbit(x);
res ++;
}
cout << res << " ";
}
return 0;
}
-x = ~x + 1即1 1001 =>1 0110 + 1 =1 0111
x & -x = 1 1001& 0 0111
这里-x不是1 0111 吗,怎么变成了0 0111
哈哈,好久没登录了,这个可能当时太晚了,写错了
你好 请问不需要先转化成二进制吗?
不需要,数据以二级制的方式存储到计算机当中
哦哦~谢谢
负数的补码等于反码+1,也等于正数反码+1。这句话成立吗?
不成立,正数的原码反码补码都是一致,只有负数考虑变