题解:P14074 [GESP202509 五级] 有趣的数字和

· · 题解

第一种做法

直接拆分,但每次除 2 不现实,也就是while(x>>=1)的做法会超时,那么,考虑 lowbit

得出代码: ```cpp #include<bits/stdc++.h> using namespace std; int lowbit(int x){return x&(-x)} int chai(int x) { int num=0; while(x-=lowbit(x)) { num++; } return num; } int main( ) { int l,r; cin>>l>>r; long long sum=0; for(int i=l;i<=r;i++) if(chai(i)%2==0) sum+=i; cout<<sum; return 0; } ``` 但是任然不对。 ## 第二种做法 这里介绍一个可以在 $O(1)$ 时间复杂度直接返回一个数二进制一的个数的函数:$\_\_builtin\_popcount(x)

那么,很容易得出代码:

#include<bits/stdc++.h>
using namespace std;
int main(  )
{
    int l,r;
    cin>>l>>r;
    long long sum=0;
    for(int i=l;i<=r;i++) if(__builtin_popcount(i)%2==1) sum+=i;
    cout<<sum;
    return 0;
}

感谢观看!