2014-03-19 05:57

题目：给定一个整数N，求出比N大，而且二进制表示中和N有相同个数的‘1’的最小的数，比如3是‘11’，接下来的5是‘101’，再接下来的6是‘110’。

解法：从低位往高位，首先跳过连续的‘0’，然后跳过连续的‘1’，并数数有多少个1。如果这时还没到最高位，那就从刚才跳过的‘1’中拿出1个放到这位上(当前位是‘0’)，然后把剩下的‘1’填到最低的几位上去。中间填充‘0’。比如：‘100111000’的下一个是‘101000011’

代码：

// 5.3 Find the next largest number that have same number of '1's with the given number.
#include
using namespace std;

unsigned int findNext(unsigned int n)
{
int n_zero;
int n_one;

 n\_zero = ;  
 while (n\_zero <  && (n & ( << n\_zero)) == ) {  
     ++n\_zero;  
 }  
 if (n\_zero == ) {  
     // all 0  
     return n;  
 }

 n\_one = n\_zero;  
 while (n\_one <  && (n & ( << n\_one)) != ) {  
     ++n\_one;  
 }  
 if (n\_one  == ) {  
     // no larger number is possible  
     return n;  
 }

 n = n >> n\_one << n\_one;  
 n |= ( << n\_one);  
 for (int i = ; i < n\_one - n\_zero - ; ++i) {  
     n |= ( << i);  
 }

 return n;  

}

int main()
{
unsigned int n;

 while (scanf("%u", &n) == ) {  
     printf("%u\\n", findNext(n));  
 }

 return ;  

}