範例程式碼 uva12208
//uva12208
#include <iostream>
#include <cmath>
using namespace std;
long long int digit[32] = {1};
long long int count1(long long int n);
int main() {
long long int a,b;
int j=0;
for (int i = 1; i < 32; i++) //建表,digit[i]表示1~i的二進制1的個數總數
digit[i] = (digit[i-1] * 2) + pow(2, i); //digit[i]=digit[i-1]*2+2^(i-1)
while (cin >> a >> b){
if (a <= 0 && b <= 0)
break;
cout << "Case " << ++j << ": " << (count1(b)-count1(a-1)) << endl; //(1~b的總數)-(1~a-1的總數)=[a,b]的總數
}
return 0;
}
long long int count1(long long int n) {
if (n < 1)
return 0;
if (n == 1)
return 1;
int firstbit;
for (int i = 0; i < 32; i++)
if ((n >> i) & 1) //尋找最高位元的1所在位置 (即二進制100..0,n為同長度的二進制數字)
firstbit = i;
if(firstbit) //100..0之前的結果查表(1~100..0的1總數)
return digit[firstbit - 1] + (n - pow(2, firstbit) + 1) + count1(n - pow(2, firstbit));
return (n - pow(2, firstbit) + 1) + count1(n - pow(2, firstbit));
//n與100..0的之間最高位元1的個數+其餘位元遞迴(其餘位元恰與1~(n-100..0)的1的個數相同)
}