範例程式碼 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的個數相同)
}