---

遞迴要怎麼推呢？不仿列一下前幾個二進制
00000
00001
00010
00011
00100
00101
00110
00111
01000

先看位數
1. 1位數 = 1
2. 2位數 = 4
3. 3位數 = 12
... 得到 digit[i] = digit[i-1]*2 + 2^(i-1)
這很好推的，發現最高位只有一半是1，而後面個數等同少一位的。

假使我們要求 n = 5, (101), 她是一個3位數的二進制數,
馬上可以知道2位所用的 1 的個數, 把三位的一去掉, 然後去求剩餘兩位的值。



#include <stdio.h>
long long digit[50] = {1};

long long cntOnes(long long n) {
    if(n < 1)  return 0;
    if(n == 1)  return 1;
    long long sum = 0;
    int i, high_bit;
    for(i = 0; i < 40; i++) {
        if((n>>i)&1)
            high_bit = i;
    }
    if(high_bit)
        sum += digit[high_bit-1];
    return sum + (n-(1LL<<high_bit)+1) + cntOnes(n-(1LL<<high_bit));
}
int main() {
    int i, cases = 0;
    long long a, b;
    for(i = 1; i < 50; i++)
        digit[i] = (digit[i-1]<<1) + (1<<i);
    while(scanf("%lld %lld", &a, &b) == 2) {
        if(a == 0 && b == 0)
            break;
        printf("Case %d: %lld\n", ++cases, cntOnes(b)-cntOnes(a-1));
    }
    return 0;
}