【题解】An Easy Problem

题目描述

　　给定一个正整数N，求最小的、比N大的正整数M，使得M与N的二进制表示中有相同数目的1。

　　举个例子，假如给定的N为78，其二进制表示为1001110，包含4个1，那么最小的比N大的并且二进制表示中只包含4个1的数是83，其二进制是1010011，因此83就是答案。

输入格式

　　输入若干行，每行一个数n(1≤n≤1000000)，输入"0"结束。

输出格式

　　输出若干行对应的值。

输入样例

1

2

3

4

78

0

输出样例

2

4

5

8

83

题解

　　容易想到，当$n$加上$lowbit(n)$时，$1$的数量一定会减少$cnt$，我们只需要从末位开始找$cnt$个$0$位，将其改为$1$，得到的就是$m$了。

#include <iostream>

#include <cstdio>

#define lowbit(x) ((x) & -(x))

using namespace std;

int n, m;

int cnt;

int main()

{

    int tmp;

    while(scanf("%d", &n) && n)

    {

        m = n + lowbit(n);

        tmp = n;

        while(tmp) ++cnt, tmp -= lowbit(tmp);

        tmp = m;

        while(tmp) --cnt, tmp -= lowbit(tmp);

        tmp = ;

        while(cnt)

        {

            if((tmp & lowbit(m)) ^ ) --cnt, m += tmp;

            tmp <<= ;

        }

        printf("%d\n", m);

    }

    return ;

}

参考程序