现在的位置: 首页 > 综合 > 正文

计算前N个数的二进制各位和

2019年02月10日 ⁄ 综合 ⁄ 共 811字 ⁄ 字号 评论关闭
#include <cstdio>
#include <iostream>

using namespace std;

int num[2][66];
int getPow( int k )
{
	if( k ==0) return 1;
	if( k == 1 ) return 2;
	if( k&1 ) return 2*getPow(k-1);
	int f = getPow( k /2 );
	return f*f;
}
int cal( int b , int cur){
	if(b==-1) return 0;
	int x = 0;
	int k = 1;
	int ans = 0;
	int n = getPow( k );
	x = (b)/n;
	x*=getPow(k-1);
	x+=min(n/2,(b)%n);
	num[cur][k] = x;
	k++;
	int q = 1;
	while( (1<<(k-1)) <= b )
	{
		n = getPow( k );
		int tmp;
		int bb = b - getPow(q)+1;
		if( bb < 0 ) break;
		tmp = (bb )/n;
		tmp*=getPow(k-1);
		tmp+= min(n/2,bb%n);
	
		
		num[cur][k] = tmp;
		k++;
		q++;
	}
	return ans;
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	__int64 a, b;
	int cnt = 1;
	while(~scanf("%I64d%I64d",&a,&b)){
		//if(a>b) swap(a,b);
		memset(num,0,sizeof(num));
		cal(b,1);
		cal(a-1,0);
        for(int i=0;i<65;i++)num[1][i]-=num[0][i];
        __int64 ans2=0;
        for(int i=0;i<65;i++)
        {
            ans2+=num[1][i]/2;
            num[1][i+1]+=num[1][i]/2;
        }
		printf("%I64d\n",ans2);
	}
	return 0;
}

【上篇】
【下篇】

抱歉!评论已关闭.