lowbit 左手的ㄟ右手 2021-06-22 15:36 233阅读 0赞 (lowbit) O(nlogn)O(nlogn) 使用lowbit操作，进行，每次lowbit操作截取一个数字最后一个1后面的所有位，每次减去lowbit得到的数字，直到数字减到0，就得到了最终1的个数， lowbit原理 根据计算机负数表示的特点，如一个数字原码是10001000，他的负数表示形势是补码，就是反码+1，反码是01110111，加一则是01111000，二者按位与得到了1000，就是我们想要的lowbit操作 给定一个长度为n的数列，请你求出数列中每个数的二进制表示中1的个数。 输入格式 第一行包含整数n。 第二行包含n个整数，表示整个数列。 输出格式 共一行，包含n个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中1的个数。 数据范围 1≤n≤100000, 0≤数列中元素的值≤109 输入样例： 5 1 2 3 4 5 输出样例： 1 1 2 1 2 ```bash #include <iostream> using namespace std; const int maxn=1e5+10; int lowbit(int x){ return x&-x; } int main() { int n; cin>>n; int x; for(int i=0;i<n;i++){ cin>>x; int res=0; while(x){ x-=lowbit(x); res++; } cout<<res<<" "; } }
相关 ACdream 1154 Lowbit Sum （数位dp） 题目链接： [ACdream 1154][] 题解：数位dp。 这题可以加深对 lowbit 的理解啊。 你打个表就可以发现规律了。 当 n 为偶数时，dp\ Dear 丶/ 2022年06月13日 00:52/ 0 赞/ 172 阅读
相关 lowbit (lowbit) O(nlogn)O(nlogn) 使用lowbit操作，进行，每次lowbit操作截取一个数字最后一个1后面的所有位，每次减去lowbit得到的数字，直到 左手的ㄟ右手/ 2021年06月22日 15:36/ 0 赞/ 233 阅读
Dear 丶
左手的ㄟ右手
还没有评论，来说两句吧...