Same binary weight (位运算)-白红宇

Same binary weight (位运算)

阅读量：6982 次

发布时间：2019-06-27

本文共 1574 字，大约阅读时间需要 5 分钟。

题目描述

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.

样例输入

17174712555555

样例输出

171881117555557

题解：

1717（0110 1011 0101），下一位是 1718（0110 1011 0110）

767（0010 1111 1111），下一位是 895（0011 0111 1111）

348（0001 0101 1100），下一位是 355（0001 0110 0011）

其中不难发现一个规律，从右起的第一个“01”改变为“10”，并且在“01”的后面所有的“1”都移动至最后，事实上，这个就是解题的关键点，那么整个问题求解的核心就转移到这两个子问题：

1. 将右起第一个“01”，改变为“10”

2. 将该“01”后面的所有“1”移动至最后

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                
                 13 #include
                 
                  14 #include
                  15 using namespace std;16 typedef long long LL;17 18 int main()19 {20 int n;21 while(cin>>n)22 {23 int b=n&(-n);// 得到n中最后一个‘1’到最后的值24 int t=n+b; // 产生进位， 实现‘01’ 变成 ‘10’25 int s=t^n; // 得到进位中发生变动的位26 int k=(s>>2)/b;//先 ‘01’->'10'发生后不要去改变这两位，所以右移2位，然后将‘01’以后的‘1’移动到最后。27 int n=t|k; // 最后的结果就是t|k28 cout<
                   
                    <

转载于:https://www.cnblogs.com/wangmengmeng/p/5185483.html

你可能感兴趣的文章