点击打开链接
Count The Carries
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 672 Accepted Submission(s): 230
Problem Description
One day, Implus gets interested in binary addition and binary carry. He will transfer all decimal digits to binary digits to make the addition. Not as clever as Gauss, to make the addition from a to b, he will add them one by one
from a to b in order. For example, from 1 to 3 (decimal digit), he will firstly calculate 01 (1)+10 (2), get 11，then calculate 11+11 (3)，lastly 110 (binary digit), we can find that in the total process, only 2 binary carries happen. He wants to find out that
quickly. Given a and b in decimal, we transfer into binary digits and use Implus's addition algorithm, how many carries are there？
from a to b in order. For example, from 1 to 3 (decimal digit), he will firstly calculate 01 (1)+10 (2), get 11，then calculate 11+11 (3)，lastly 110 (binary digit), we can find that in the total process, only 2 binary carries happen. He wants to find out that
quickly. Given a and b in decimal, we transfer into binary digits and use Implus's addition algorithm, how many carries are there？
Input
Two integers a, b（0<=a<=b<1000000000), about 100000 cases, end with EOF.
Output
One answer per line.
Sample Input
1 2
1 3
1 4
1 6
Sample Output
0
2
3
6
Source
给你a和b，让你计算从a到b之间的数的二进制数之和进位的总次数。
将每个数拆成二进制数，那么第一位数1的总数就是从a到b第一位是1的数量之和，那么第一位进位的数量为第一位是1的总数/2;
第二位1的总数就是从a到b第二位是1的数量之和加上由第一位进位的数量;
第三位1的总数就是从a到b第三位是1的数量之和加上由第二位进位的数量;
.
.
.
怎样求每一位上1的总数？0到8的二进制数例如以下：
8 7 6 5 4 3 2 1 0
0 0 0 0 0 0 0 0 0 (0)
0 0 0 0 0 0 0 0 1 （1）
0 0 0 0 0 0 0 1 0 （2）
0 0 0 0 0 0 0 1 1 （3）
0 0 0 0 0 0 1 0 0 （4）
0 0 0 0 0 0 1 0 1 （5）
0 0 0 0 0 0 1 1 0 （6）
0 0 0 0 0 0 1 1 1 （7）
0 0 0 0 0 1 0 0 0 （8）
第一位是10交替出现，第二位是0011交替出现，第三位是00001111交替出现......
那么规律就出来了。
#include<stdio.h>
#include<string.h>
long long s[77],x[77];
int main()
{
long long a,b;
while(scanf("%I64d%I64d",&a,&b)!=EOF)
{
memset(s,0,sizeof(s));
memset(x,0,sizeof(x));
b++;
int n=b;
if(a==b){printf("0\n");continue;}
for(int i=0,k=2;i<=70;i++,k*=2)
{
s[i]=a/k*k/2+(a%k>=k/2?a%k-k/2:0);//求第i位是1的个数总和
x[i]=b/k*k/2+(b%k>=k/2?b%k-k/2:0);
n/=2;if(!n)break;
}
long long count=0;
for(int i=0;i<70;i++)
{
count+=(x[i]-s[i])/2;
x[i+1]+=(x[i]-s[i])/2;
}
printf("%I64d\n",count);
}
return 0;
}