题目描述
小s最近对数字情有独钟。他又发现了一种神奇的数字。对于数x，如果它二进制表示中只有一位是0，则x就会被小s所喜爱。比如5，二进制为101，则它被小s所喜爱。
现在，小s想知道，对于一个区间[L, R]，有多少数是他所喜爱的。
输入格式
输入包含多组数据。
输入第一行T，表示数据组数。
每组数组仅有一行，包含两个正整数L, R。
输出格式
对于每组数据输出一行，表示答案。
输入样例
2
5 10
2015 2015
输出样例
2
1
数据范围与提示
【数据范围与约定】
30%: L, R <= 10^6, T <= 10
60%: L, R <= 10^10, T <= 100
100%: L, R <= 10^18, T <= 10000
#include<bits/stdc++.h>
using namespace std;
const int MAXN=210;
const int mod=998244353;
const int MOD=10010;
long long n,m,k,sum,cnt,a[MAXN],b[MAXN],dp[MAXN],t;
char str[MAXN],s[MAXN];
long long qpow(long long a,long long b){
long long ans=1;
while(b){
if(b&1){
ans=(ans*a);
}
a=(a*a);
b/=2;
}
return ans;
}
int main(){
cin>>t;
a[0]=1;
for(int i=1;i<=200;i++){
a[i]=a[i-1]+i-1;
}
while(t--){
cin>>n>>m;
sum=0;
for(long long i=0;i<=200;i++)
if(m<qpow(2,i)){
k=i;
break;
}
long long x=qpow(2,k)-1;
for(long long i=k-2;i>=0;i--){
if(m>=(x-qpow(2,i))){
sum++;
}
}
for(long long i=1;i<=200;i++){
if(n<qpow(2,i)){
cnt=i;
break;
}
}
long long y=qpow(2,cnt)-1;
for(long long i=0;i<cnt-1;i++){
if(n<=(y-qpow(2,i))){
sum++;
}
}
sum+=a[k-1]-a[cnt];
cout<<sum<<endl;
}
return 0;
}
进制转换这是最基本的啊，十进制转2进制的话，不停除以二取余，看看余数有多少个1就行。
不过这样很可能超时，推荐用位运算，右移一位相当于除以2，然后求除以二的余数，就和1进行按位与。