Count The Carries
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87326#problem/C
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？.
Input
Output
One answer per line.
Sample Input
1 2
1 3
1 4
1 6
Sample Output
0
2
3
6
HINT
题意
二进制累加，从A累加到B，问你在二进制中，一共进位了多少次
题解：
我并不知道怎么做的……
队友啪啪啪就拍完了= =
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm> using namespace std; long long x[],y[]; int main()
{
long long a,b;
while(scanf("%lld%lld",&a,&b)!=EOF)
{
long long now=;
long long cnt=;
if(a>) a--;
for(long long i=1LL;i<=*1LL;i++)
{ x[i]=(1LL<<(i-1LL))*(a>>i)+max(0LL,(a%(1LL<<i)-(1LL<<(i-1LL))+1LL));
y[i]=(1LL<<(i-1LL))*(b>>i)+max(0LL,(b%(1LL<<i)-(1LL<<(i-1LL))+1LL));
now+=y[i]-x[i];
cnt+=1LL*(now>>1LL);
now=now>>1LL;
}
while(now)
{
cnt+=1LL*now;
now>>=1LL;
}
printf("%lld\n",cnt);
}
return ;
}