POJ 2453 解题报告

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

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

代码:

#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;
}

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

Leave a Reply

Your email address will not be published.