题意：已知D（0<=D<2^31）、s1、s2，其中L为D转化为二进制数时1的个数，题目保证s1<=L<=s2，求一个数，满足以下条件：
1、比D大
2、转化为二进制时1的个数在[s1, s2]内
3、找出满足1、2条件的最小数字
分析：
1、首先将D加1，假设该数为x，求出x转化为二进制时1的个数cnt。
2、若s1<=cnt<=s2,则输出x
3、若cnt<s1,则应当增加1的数目，因为要保证找到的数字最小，所以要从二进制数的最右边开始改变。
方法：从右向左，将找到第一个0变为1，假设找到的这个0的位数为i（从右往左数第一个数字位数为0，以此类推），那将该数字变为1时，D会增加2^i。（eg：5的二进制数位101，将第1位的0变为1，则是111，转化为十进制是7，，5变成7增加了2^1）
4、若cnt>s1,则应当减少1的数目，因为要保证找到的数字最小，所以要从二进制数的最右边开始改变。
方法：从右向左，将找到第一个1变为0，假设找到的这个1的位数为i（从右往左数第一个数字位数为0，以此类推），那将该数字变为0时，D会增加2^i。（eg：6的二进制数位110，将第1位的1变为0，则是1000，转化为十进制是8，，6变成8增加了2^1）
5、循环上述操作直到满足条件。
6、如上解法的原因有二：
（1）因为是在二进制上操作，所以当cnt<s1加1时，就不必要调用get函数求二进制中1的个数(如果这道题想暴力水过的话，就容易明白这句话)
（2）最最主要的原因是，它跳过了许多不满足的中间数字。
如以下例子:D = 4, s1 = 1, s2 = 1,为了方便理解可以看下表。
按照该题的解题思路，D+1为5，那么因为其二进制数中1的个数是2，cnt>s2,因此按代码操作后D为6，仍cnt>s2,继续按代码操作，可得D为8，跳过了D为7的情况，这种跳过的现象数越大越明显，此处不再举例。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #define Min(a, b) a < b ? a : b #define Max(a, b) a < b ? b : a typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1}; const int dc[] = {-1, 1, 0, 0}; const double pi = acos(-1.0); const double eps = 1e-8; const int MAXN = 100 + 10; const int MAXT = 10000 + 10; using namespace std; int a[MAXN]; int get(ll n){//求二进制数中1的个数，边求边将D+1的二进制数依次存入数组a，便于之后从右向左找第一个1或第一个0 int k = 0; int cnt = 0; while(n){ a[k++] = n % 2; if(n & 1) ++cnt; n >>= 1; } return cnt; } ll POW(int k){//快速幂，因为该题只需求2的k次幂，所以只传了k ll ans = ll(1); ll x = ll(2); while(k){ if(k & 1) ans *= x; x *= x; k >>= 1; } return ans; } int main(){ int T; scanf("%d", &T); for(int i = 1; i <= T; ++i){ memset(a, 0, sizeof a); ll D; int s1, s2; scanf("%lld%d%d", &D, &s1, &s2); printf("Case #%d: ", i); int cnt = get(++D); while(1){ if(cnt >= s1 && cnt <= s2){ printf("%lld\n", D); break; } else if(cnt < s1){ int k = 0; while(a[k]) ++k; a[k] = 1;//将0变成1，a数组中存的是D的二进制数 D += POW(k); ++cnt;//注意1的个数要增加 } else if(cnt > s2){ int k = 0; while(!a[k]) ++k; D += POW(k);//此处可以改为lowbit(D),所需函数如下 cnt = get(D);//1的个数可能不变，可能减少，此处不仅重新计算了D的二进制中1的个数，而且更新了a数组，存进了新的D的二进制数，便于之后从右向左找第一个1或第一个0 } } } return 0; }
PS：lowbit的功能是求2^p，p为x的二进制数中，从右向左数第一个1的位置（从右往左数第一个数字位数为0，以此类推）
int Lowbit(int x){
return x&(-x);
}
eg:若x=9，则9&-9为0000 1001 & 1111 0111，结果为1.（注意该二进制是补码表示，最左边的位为符号位，正数为0 ，负数为1，原码变为补码是按位取反再加1）
而9的二进制数时1001，从右向左数第一个1的位置，其位数为0，所以Lowbit(9) = 2^0 = 1.