HDU 4588 Count The Carries （数学，计数）

题意：给定两个十进制数，求二进制中，从x加到y的二进制进了多少位。

析：把这些数字的二进制纵向罗列出来，然后一位一位的把和加起来，最终得到总的进位数。从1到x，第i位上1的总数是x左移i+1位再右移i位后得到的，

（在第 0位上，1和0以1010101010的周期出现，并且每个周期一个1，在第1位上，1和0以11001100的周期出现，并且每个周期2个1，以此类推，
则第n位上的1的个数是x/2^n*2^(n-1)，即先左移n+1位，再右移n位），如果x在i位上面上是1，特殊判断一下，求一下周期以外的1的个数，这个时候的1的个数是

a%（1<<k）+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 <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <string>

#include <algorithm>

#include <vector>

#include <map>

using namespace std ;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f3f;

const int maxn = 10000 + 5;

LL solve(LL num, int i){

    if(-1 == num)  return 0;

    LL ans = (num>>i+1)<<i;

    if(num & (1LL<<i))  ans += (num % (1LL<<i)) + 1LL;

    return ans;

}

int main(){

    int a, b;

    while(scanf("%d %d", &a, &b) == 2){

        LL ans = 0;

        LL sum = 0;

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

            sum += solve(b, i) - solve(a-1, i);

            sum /= 2;

            ans += sum;

        }

        cout << ans << endl;

    }

    return 0;

}