Input

输入包含多个测试数据。
每个测试数据为一行，每行包括一个非负十进制整数n(n < 2^63)。
输入数据以-1结束。

Output

对于每个测试点，先输出"Case #:"，#代表第几个测试点，然后在下一行输出对应数列二进制表示后1的个数。

Sample Input

Sample Output

Case 1:
7
Case 2:
5744
Case 3:
239720074

列举前九个数的二进制数(把0也带进去)

0000

0001

0010

0011

0100

0101

0110

0111

1000

观察一下,最后一位,0101....交替.倒数第二位00110011....倒数第三位00001111.......

可以看出,从最后一位开始,每次交替的位数是2^i,用这样的方法去推理就会很容易找到相关公式,这我就不说了

程序如下:

#include<stdio.h>
#include<math.h>

int number(__int64 a) //转换为二进制数后的位数
{
      int s=0;
      while(a!=0)
      {
          a=a>>1;
    s++;
      }
      return s;
}

int main()
{
 __int64 a,s,t,v;
 int i,j,k=1;
 while(scanf("%I64d",&a)&&a!=-1)
 {
    s=0;
    j=number(a);
    for(i=1;i<=j;i++) //从最后一位开始数1的个数
    {
     t=(a+1)%(__int64)pow(2,i);
     v=t>(__int64)pow(2,i-1)?t-(__int64)pow(2,i-1):0;
     s+=(a+1)/(__int64)pow(2,i)*(__int64)pow(2,i-1)+v;
    }
  
    printf("Case %d:\n%I64d\n",k++,s);
 }
 return 0;
}