喜爱（一道有趣的C++题）
题目描述
小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 <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef unsigned long long ll;
using namespace std;
const int maxn = 210;
#define inf 0x3f3f3f3f
const int mod = 998244353;
const int MOD = 10007;
ll n, m, k, sum, cnt;
ll a[maxn], b[maxn], dp[maxn];
char str[maxn], s[maxn];
ll qpow(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
{
ans = (ans * a);
}
a = (a * a);
b /= 2;
}
return ans;
}
int main() {
ll t;
cin >> t;
a[0] = 1;
for (ll i = 1; i <= 200; i++)
a[i] = a[i - 1] + i - 1;
while (t--) {
cin >> n >> m;
sum = 0;
for (int i = 0; i <= 200; i++)
if (m < qpow(2, i))
{
k = i;
break;
}
ll x = qpow(2, k) - 1;
for (int i = k - 2; i >= 0; i--)
{
if (m >= (x - qpow(2, i)))
{
sum++;
}
}
for (int i = 1; i <= 200; i++)
if (n < qpow(2, i))
{
cnt = i;
break;
}
ll y = qpow(2, cnt) - 1;
for (int i = 0; i < cnt - 1; i++)
if (n <= (y - qpow(2, i))) {
sum++;
}
sum += a[k - 1] - a[cnt];
cout << sum << endl;
}
return 0;
}
