附上题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4588 题目意思是a + a+1 + a+2 .. + b-1 + b, 的二进制加法中总共发生了多少次进位， 假设我们知道从a - b的而二进制表示的某一位的1的总个数num1， 那么当前向后一位的进位就是num1 + x(之前为向次位的进位), 现在问题就转化成了求a - b的二进制表示中某一位的1的总个数， 我们发现第i位二进制是程周期出现的， 周期为2^i， 这样我们就可以算出从0 - a 的1的个数， 从0 - b+1的1的个数， 两个相减即可， 代码如下：
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; typedef long long LL; LL numa[100], numb[100]; int main() { LL a, b; while(cin>>a>>b){ memset(numa, 0, sizeof(numa)); memset(numb, 0, sizeof(numb)); b += 1; //这里应该将b+1， 具体原因请在纸上画画 LL k = 2; for(int i=0; i<60; i++){ numa[i] = a/k*k/2 + (a%k>k/2?a%k-k/2:0); //计算第i位0 - a-1的1的个数 numb[i] = b/k*k/2 + (b%k>k/2?b%k-k/2:0); //计算第i位0 - b的1的个数 k <<= 1; } LL cnt = 0; LL x = 0; //进位 for(int i=0; i<60; i++){ cnt += (numb[i]-numa[i]+x)/2; x = (numb[i]-numa[i]+x)/2; } cout<<cnt<<endl; } return 0; }