HDU 5491 The Next-蒲公英云

HDU 5491 The Next

2015 ACM/ICPC Asia Regional Hefei Online
Problem Description
Let L denote the number of 1s in integer D’s binary representation. Given two integers S1 and S2, we call D a WYH number if S1≤L≤S2.
With a given D, we would like to find the next WYH number Y, which is JUST larger than D. In other words, Y is the smallest WYH number among the numbers larger than D. Please write a program to solve this problem.

Input
The first line of input contains a number T indicating the number of test cases (T≤300000).
Each test case consists of three integers D, S1, and S2, as described above. It is guaranteed that 0≤D<231 and D is a WYH number.

Output
For each test case, output a single line consisting of “Case #X: Y”. X is the test case number starting from 1. Y is the next WYH number.

Sample Input
3
11 2 4
22 3 3
15 2 5

Sample Output
Case #1: 12
Case #2: 25
Case #3: 17

解题思路：先将给的d加一，然后判断d中1的个数，如果大于s2，则将s2中最右边的1加1，如1100就加上100，不断循环直到小于s2，如果小于s1的话，则将0变为1，顺序是从右向左，直到大于等于s1即可。

注意两点：
1.首先虽然声明的D小于2的三十一次方，但是移动的时候可能会大于，所以要开成longlong 型。
2.这道题检测1的个数与查询第一个1的位置时不要一个一个检测，要懂得运用x&-x这个数据结构

检测1的个数：

这种方法速度比较快，其运算次数与输入n的大小无关，只与n中1的个数有关。如果n的二进制表示中有k个1，那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1，同时累加计数器，直至n为0，代码如下

int BitCount2(unsigned int n)
{
    unsigned int c =0 ;
    for (c =0; n; ++c)
    {
        n &= (n -1) ; // 清除最低位的1
    }
    return c ;
}

为什么n &= (n – 1)能清除最右边的1呢？因为从二进制的角度讲，n相当于在n - 1的最低位加上1。举个例子，8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）= 0（0000），清除了8最右边的1（其实就是最高位的1，因为8的二进制中只有一个1）。再比如7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二进制表示中最右边的1（也就是最低位的1）。

最右边1加1：x+=x&-x；(树状数组的lowbit哦)

AC代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<string>
#include<map>
using namespace std;
int eva(int d)
{
    int c=0;
    for(;d;c++)
    {
        d&=(d-1);
    }
    return c;
}
int main()
{
    int t,_=1;
    scanf("%d",&t);
    while(t--)
    {
        int s1,s2,x;
        long long d,d1;
        scanf("%I64d%d%d",&d,&s1,&s2);
        d++;
        x=eva(d);
        while(x>s2)
        {
            d+=d&(-d);
            x=eva(d);
        }
        if(x<s1)
        {
            int k=1;
            for(int i=0; i<s1-x; i++)
            {
                while(d&k) k<<=1;
                d|=k;
            }
        }
        printf("Case #%d: %lld\n",_++,d);
    }
    return  0;
}