NYOJ 412(bitset)

  1. 云栖社区>
  2. 博客>
  3. 正文

NYOJ 412(bitset)

哈沙给 2012-09-09 15:20:00 浏览348
展开阅读全文

 

Same binary weight

时间限制:300 ms | 内存限制:65535 KB
难度:3
 
描述

The binary weight of a positive integer is the number of 1's in its binary representation.for example,the decmial number 1 has a binary weight of 1,and the decimal number 1717 (which is 11010110101 in binary) has a binary weight of 7.Give a positive integer N,return the smallest integer greater than N that has the same binary weight as N.N will be between 1 and 1000000000,inclusive,the result is guaranteed to fit in a signed 32-bit interget.

 
输入
The input has multicases and each case contains a integer N.
输出
For each case,output the smallest integer greater than N that has the same binary weight as N.
样例输入
1717
4
7
12
555555
样例输出
1718
8
11
17
555557
 1 //第一个01,变为10,1的右边有n个1,把1变为0,再次把 右边的n为0变为1,答案为所求 
 2 #include <iostream>
 3 #include <bitset>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int i,j,k;
 9     int num;
10     while(cin>>num)
11     {
12         bitset <32> Q;
13         i=0;
14         while(num>0)//大于0,更安全 
15         {
16             if(num&1)
17                 Q.set(i);//默认设置为1 
18             num/=2;
19             i++;
20         }
21         for(j=0;j<i;j++)
22         {
23             if(Q.test(j)&&!Q.test(j+1))//test()函数返回在pos上的位的值。
24             {
25                 Q.flip(j);
26                 Q.flip(j+1);
27                 break;
28             }
29         }
30         int count=0;
31         for(i=0;i<j;i++)
32         {
33             if(Q.test(i)) 
34             {
35                 count++;
36                 Q.flip(i);
37             }
38         }
39         for(i=0;i<count;i++)
40             Q.flip(i);
41         //printf("%u\n",Q.to_ulong());
42         cout<<Q.to_ulong()<<endl;
43     }
44     return 0;
45 }        

 

网友评论

登录后评论
0/500
评论
哈沙给
+ 关注