题目描述
给定一个长度为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
(lowbit) $O(nlogn)$
使用lowbit操作,进行,每次lowbit操作截取一个数字最后一个1后面的所有位,每次减去lowbit得到的数字,直到数字减到0,就得到了最终1的个数,
lowbit原理
根据计算机负数表示的特点,如一个数字原码是10001000,他的负数表示形势是补码,就是反码+1,反码是01110111,加一则是01111000,二者按位与得到了1000,就是我们想要的lowbit操作
C++ 代码
#include<iostream>
using namespace std;
int lowbit(int x){
return x&(-x);
}
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;
}
算法2
(暴力枚举) $O(nlongn)$
blablabla
时间复杂度分析:blablabla
思路
对于每个数字a,a&1得到了该数字的最后一位,之后将a右移一位,直到位0,就得到了1的个数
C++ 代码
#include<iostream>
using namespace std;
int n;
int a,k;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a);
k=0;
while(a){
k+=a&1;
a=a>>1;
}
printf("%d ",k);
}
return 0;
}
用lowbit感觉有点多此一举,直接让x&=(x-1)就行了,效果就是每次都去掉末尾的1。根本不用得到之后再减去。
但是显然 lowbit 更好理解,无脑套就行了
妙啊
算法二的时间复杂度 $nlongn$ 是什么鬼?另外建议
log
写成\log
,比如n \log n
有点想笑哈哈哈哈哈
妙啊
能问一下为啥i从32开始吗
我也想问,有解答踢我谢谢
可能是因为数据范围32位
int类型4个字节、32位,一般应该从31到0移位判断,这个32开始好像有点问题。
第三十二位,是不是代表数的正负?
题目说了是正数,int类型最高位为0,应该也没啥问题
我的傻瓜做法
#include[HTML_REMOVED]
using namespace std;
const int N = 1e6+10;
int q[N], n;
int main(){
scanf(“%d”,&n);
for(int i = 0 ;i<n ; i++) scanf(“%d”,&q[i]);
}
好憨啊,hh
哈哈哈哈我也是这么写的
C++STL 六行搞定:
玩尬的是吧:
强行缩短行数~~
nice
暴力的是时间复杂度是对的,lowbit的时间复杂度不对吧,应该是O(n*M),M是数字中1的个数的平均值。
算法二对负数会死循环。
为什么会出现死循环呢?
负数 右移 是 补 1
感谢~ 负数右移最后会变成全一的状态,等于-1
确实
时间复杂度都是 $O(n)$ 吧
不是
O(n
), 因为这里的n表示的是数列的个数,即总共输入n个整数;但是对于其中每个整数x,转化成二进制后的长度为logx
级别的;综合两者,时间复杂度为O(nlogn)
$\log x$ 怎么最后变 $\log n$ 了
两者都是位运算 , 都是nlogn 何来暴力一说
负数得不到正确结果吧
优秀,感谢帮助。你是大大的好人。
暴力不会超时吗
负数的补码,不是这样求的吗:负数的原码符号位不变,其他位取反,得到反码,反码再加1,得到补码,这里说-x=~x+1,怎么对呢
想出来了,谢谢大家。。,负数的原码就是正数的原码全部取反,然后加1,
这个和上面的说法其实做法都一样
感谢大佬!
#include [HTML_REMOVED]
using namespace std;
int main (){
int n;
cin>>n;
long long int a[100005];
for(int i=0;i[HTML_REMOVED]>a[i];
int num=0;
while(a[i]>=1)
{
if(a[i]%2==0)
num++;
a[i]=a[i]/2;
}
cout<<num<<” “;
}
}
下面暴力的
whlie(a)
{ k += a & 1;
a = a>>1;
} 这个是什么意思哇作者。
就是判断现在的a的最后一位是不是1如果是1,计数器加1; a右移一位,去掉最后一位接着判断
a&1 这个 &是什么意思
就是按位与,可以百度一下按位与就清楚了