PKU 2453 An Easy Problem
http://acm.pku.edu.cn/JudgeOnline/problem?id=2453
题目的大意是给一个数I要求出一个比I大的最小值，这个值二进制的表示1的数量要和I中1的数目相同。
那么首先我们可以想到的方法是，对相同的I的排列数，不用通同位运算得解，但是效率应该不会很高，如果要提高效率或者可以研究一个1的位置变换的规律，比如当I中只有一个1的时候，这时，答案只需将I左移一位：1à2 ，4à8
其次，我们想到的肯定是位操作来解决，运用位操作的高效应该可以用枚举来完成此题。
我们可以很容易地想到这样的枚举方式：
for (i=I+1;;i++) If (i中1的个数和I相同) break;
print(i);
这样的话要处理的之剩下，如何判断i中1的个数是否和I相同
求出i中1的个数：
首先题目最大的数为：1000000 得到的2进制有20位之多
可以确定的是，最大的这个数的解不会超出20位
写一个函数传入n:
const int M = 20;
int cnt = 0;
for (i=0;i<=M;i++) if ((n >>i)&1) cnt++;
return cnt;
这样便可以求出一个数n中1的个数了。
具体AC代码：(C++)
#include <iostream>
using namespace std;
const int M = 21;
int num(int n)
{
int i,cnt = 0;
for (i=0;i<=M;i++)
if ((n>>i)&1)
cnt++;
return cnt;
}
int main()
{
int i,I;
while (scanf("%d",&I)!=EOF,I)
{
int numI = num(I);
for (i=I+1;;i++)
if (num(i) == numI)
break;
printf("%d/n",i);
}
return 0;
}
以上代码的时间复杂度大约为O(nm)
虽然AC了，但这题光凭枚举效率一定是不高的，看一下运行的情况：
2453 Accepted 204K 219MS C++ 342B
为了提高时间效率，其实这道题还是可以找到规律的
其解法为：从右向左，找到第一个“01”以便进位
那么我们把01里的1向前进一位，变成10，它后面的1要移到最右边
实现：我们可以从右向左遍历这个数，找到第一个’01’，进位后把后面的1移到最右边
这样的一个算法，可以写成O(n+m)也可以优化到O(n)
我用优化的方法写了一下：
具体AC代码：(C++)
#include <iostream>
using namespace std;
const int M = 21;
int main()
{
int i,j,k,I;
while (scanf("%d",&I)!=EOF,I)
{
int numOfRZero = 0;
int flag;
for (i=0;i<=M;i++)
{
if ((I>>i)&1)
{
if (!((I>>(i+1))&1))
{
I+=(1<<i);
flag = i;
break;
}
}
else
numOfRZero++;
}
int cleaner = 0xffffff; //用来将后面的几位清零
int clean = 0xffffff;
cleaner <<= flag;
cleaner &= clean;
I &= cleaner; // 将后面的几位清零
clean >>= (24-(flag-numOfRZero));
I |= clean;
printf("%d/n",I);
}
return 0;
}
运行结果：
2453 Accepted 204K 0MS C++ 1120B
终于0MS AC ，但这样大家就满足了吗？！
我不得不提，我们应该清楚一点：其实位运算的最高境界是：无遍历
也是就是在常数的时间效率里得解。
高手AC CODE：（C）
#include <stdio.h>
int main()
{
int n,x;
while(scanf("%d",&n),n)
{
x=n&-n;
printf("%d/n",n+x+(n^n+x)/x/4);
}
return 0;
}
两行代码，无遍历，