POJ 2453 解题报告

题目意思:给定正整数x,求出在二进制表示中与他有相同个数的‘1’,且比他大的最小的数。

可以把此题当成求二进制中1的个数来做。而该算法在我的其他帖子(点击这里)中已经有详细说明。

代码:

[cpp]
#include <iostream>

using namespace std;

int Count (int);
int main()
{
int x, num;

while(cin >> x)
{
if(!x)
break;
num = Count(x);
while(x++)
if(Count(x) == num)
{
cout << x << endl;
break;
}
}
return 0;
}

int Count(int x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);

return x;
}
[/cpp]

原题连接http://poj.org/problem?id=2453

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.