计算几何 找规律

题意：给一段l~r的区间，在这个区间内有多少个数是在二进制下1的个数是奇数，输出这个数
https://ac.nowcoder.com/acm/contest/11173/B
思路：
首先用到二进制下求1的个数，lowbit；

bool check(ll n){
    ll cnt=0;
    while(n){
        cnt++;
        n-=lowbit(n);
    }
    if(cnt&1) return true;
    return false;
}

然后可以用一个sum函数求，1~n下这样的数有多少个，然后就有以下的表格，来自大佬的题解计算几何

当n+1是4的倍数时，有以下规律，n=(n+1)/2;

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull; 

#define sc(n) scanf("%d",&n)
#define pr(n) printf("%d\n",n)
#define endl "\n";
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)

const int N=100010;
const int MOD = 1e9 + 7;
const int INF=1e9;
const double eps=1e-5;
int n,m,k;
string s;
int a[N];

ll lowbit(int x){
    return  x&-x;
} 

bool check(ll n){
    ll cnt=0;
    while(n){
        cnt++;
        n-=lowbit(n);
    }
    if(cnt&1) return true;
    return false;
}
ll sum(ll n){
    ll ans=0;
    while(n){
     if((n+1)%4==0)  return ans+(n+1)/2;
     if(check(n)) ans++;   
     n--;
    }
    return ans;
}


int main(){
    int T;
    cin>>T;
    while(T--){
      ll l,r;    
      cin>>l>>r;
      cout<<sum(r)-sum(l-1)<<endl;  
    }
    return 0;
}