2013 南京邀请赛 C - Count The Carries

题意是a+,,,,,+b，在二进制计算中有多少次进位，

只要统计一下从a~b所有数位上1的和就可以了

写了前十的二进制数，发现了规律，

0位上每2个数后1个数有1,，即奇数

1位上每4个数后2个有1，

2位上每8个数后4个有1，.......

。。。。。。。。。。。。。。

 

    #include<stdio.h>

#include<string.h>

int numa[70],numb[70];

void num(int a[],int n)//0-n每个数位上1的和

{

	int i,temp;

	temp=1;

	n++;

	for(i=0;i<64;i++)

	{

		if(temp>n)break;

		temp*=2;

		a[i]+=(n/temp)*(temp/2);

		if(n%temp>temp/2)//余数大于temp/2，后面还有n%temp-temp个1

		  a[i]+=n%temp-temp/2;

	}

}

int main()

{

	int i,a,b;

	long long sum;

	while(scanf("%d%d",&a,&b)!=-1)

	{

		memset(numa,0,sizeof(numa));

		memset(numb,0,sizeof(numb));

		num(numa,a-1);

		num(numb,b);

		for(i=0;i<64;i++)

        	numb[i]-=numa[i];

	    sum=0;

		for(i=0;i<63;i++)

		{

			sum+=numb[i]/2;

			numb[i+1]+=numb[i]/2;

		}

		printf("%lld\n",sum);





	}

	return 0;



}


  

 

 

 

2013 南京邀请赛 C - Count The Carries