POJ 3252 Round Numbers

// 求区间 [s,f]中有几个数在二进制表示下0的个数
// 转化成求 0到某个值里面有多少这样的数
// n二进制有m位 先求 1,2,3...m-1位二进制数里面有多少个符合
// 再求n位里面比n小的二进制数里面有几个符合
// 具体就是 将n写成二进制 从高位(m-1位)往地位枚举
// 如果该位是1 则改成0 求剩下位数里面满足的情况总数
// 如果该位是0 则不变 继续往下
#include <iostream>
#include <string>
#include<sstream>
#include <cmath>
#include <map>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define  LL long long
int C[40][40];
int ans[40];
void init()
{
    int i,j;
    for(i=0;i<=31;i++) C[i][0]=1;
     for(i=1;i<=31;i++)
        for(j=1;j<=i;j++)
         C[i][j]=C[i-1][j-1]+C[i-1][j];
    for(i=1;i<=31;i++)
        for(j=(i+1)/2;j<i;j++)
          ans[i]+=C[i-1][j];
}
int Count(int n)
{
    if(!n) return 0;
    int st[40],top=0;
    int sum=0;
    while(n)
    {
       st[++top]=n&1;
       n>>=1;
    }
    int i,k=0,len=top;// k记录n二进制里面0的个数
    for(i=1;i<top;i++) sum+=ans[i];// 先求 1,2,3...m-1位二进制数里面有多少个符合
    top--;
    while(top)
    {
        if(st[top])
        {
           k++;
           i=(len+1)/2-k;
           if(i<0) i=0;
           for(;i<=top-1;i++)
                sum+=C[top-1][i];
           k--;
        }
        else
          k++;
       top--;
    }
   if(k>=(len+1)/2) sum++;//判断这个数自己本身是不是
   return sum;
}
int main()
{
    init();
    int s,f;
    while(scanf("%d %d",&s,&f)!=EOF)
    {
       printf("%d
",Count(f)-Count(s-1));
    }
    return 0;
}