C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 384K, 提交时间: 2019-07-09 17:25:33

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

using ll=long long;

ll C(ll n, ll m){
	double x=1.0;
	for(int i=1;i<=m;++i){
		x*=(n-i+1);
		x/=i;
	}
	return (ll)x;
}

ll calc(ll x){
	ll h=0, m=1, ans=0;
	while(x>>h) ++h;
	for(int i=h-2;i>=0;--i){
		for(int j=(i+2)/2;j<=i;++j){
			ans += C(i, j);
		}
	}
	for(int i=h-2;i>=0;--i){
		if(((x>>i)&1)==0) continue;
		for(int a=std::max((h+1)/2-h+i+m,0LL);a<=i;++a){
			ans += C(i, a);
		}
		++m;
	}
	return ans;
}

int main(){
	ll a,b;
	scanf("%lld%lld", &a, &b);
	ll x=calc(b+1)-calc(a);
	printf("%lld\n", a>0?x:x+1);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 480K, 提交时间: 2019-07-05 18:55:20

#include<bits/stdc++.h>
using namespace std;
int dp[31][31],g[31];
int check(int x){
	int m=0,ans=0,s=1;
	while(x){
		g[++m]=x&1;
		x>>=1;
	}
	for(int i=2;i<m;i++)
	for(int j=0;j<i/2;j++)
	ans+=dp[i-1][j];
	for(int i=m-1;i>=1;i--){
		if(g[i]){
		    for(int j=0;j<=m/2-s;j++)
		    ans+=dp[i-1][j];
		}
		s+=g[i];
	}
	ans+=s<=(m/2);
	return ans;
}
int main(){
	dp[0][0]=1;
	for(int i=1;i<=30;i++)
	for(int j=dp[i][0]=1;j<=i;j++)
	dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
	int a,b;
	cin>>a>>b;
	cout<<check(b)-check(a-1)<<"\n";
	return 0;
}