1223：An Easy Problem

1223：An Easy Problem 题目链接

题目的要求是：

**要使得 n 在 a 不变的情况下，得到任意多的 n' 满足 n' > n ，定义为集合 M ，要求取 M 中最小的 n' 为 **

(a 代表 n 中二进制位为 1 的个数)

一种暴力做法是，统计 n 的二进制中 1 的个数为 a ，然后设置一个变量 t = n，t 每次自增 1 （t++），

之后，统计 t 的二进制中 1 的个数为 b ，如果 a == b，那么 t 就是比 n 大的正整数集合 M 中，最小的数。
O(1) 的做法是用位运算，举个例子 :

n == 78，我们尝试着在不改变 a 的情况下，移动 n 的二进制中的 1 ，让 n 变大的幅度尽可能的小

序号 n n 中的二进制表示

1 78 ‭0100 1110‬

2 77 0100 1101

3 89 0101 0101

4 83 ‭0101 0011‬
- 为了实现变大的过程，肯定要把某个 1 向左移动，那么如何选取这个 1 呢？
  
  从右边开始寻找第一段连续的 1 (只有一个 1 也算一段)，把将这段连续 1 中最左端的 1 向左前进一位
  
  要让这段连续 1 中的左端前进一位，只要在这段连续的 1 的右端加 1就好了，二进制的加法进位到头
  
  如何寻找右端的 1 呢？
  
  lowbit运算 : t1 = n & (-n) 得到最右边的 1
  
  ‭0100 1110‬
  
  & 1011 0010
  
  = 0000 0010
  
  之后 t2 = n + t1; 得到进位之后的值。
  
  ‭ 0100 1110‬
  
  + 0000 0010
  
  = 0101 0000
  
  但是，这么做了之后，我们就丢失了原先那段连续的 1 的信息了。
- 为了让 n 变大的幅度尽可能的小
  
  就要把那一段连续的 1 剩余的部分，全部移动到最右边（参考序号 1 和序号 4 的二进制表示）
  
  寻找那段丢失的 1 。
  
  n ^ t2
  
  0100 1110‬
  
  ^ 0101 0000
  
  = 0001 1110
  
  我们发现，这样经过 ^ 得到的结果，会多出两个 1 ，解法办法是，右移的时候，再向右移动两位就好
  
  即 >> 2
  
  (n ^ t2) / t1 ，（ / t1）这个操作是为了把 ^ 之后的 1 整个向右移动 (log_2 t1) 的位置，
  
  因为 t1 代表了最右边的 1 ，且只有 1 ，在二进制表示中，肯定是 2的幂，(log_2 t1) 得到当前t1 中 1的位置
  
  / t1 相当于 >>(log_2 t1) ，两者相等，之后再 >>2 消去多余的两个 1 ，
  
  最后和 t2 取按位或就得到了最终想要的结果。

序号	n	n 中的二进制表示
1	78	‭0100 1110‬
2	77	0100 1101
3	89	0101 0101
4	83	‭0101 0011‬

代码实现

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int x,t1,t2,y;
    while(cin>>x){
        if(x == 0) break;
        t1 = x & (-x);  
        t2 = x + t1;
        y = t2 | ((x ^ t2) / t1) >> 2;
        cout<<y<<endl;
    }
    return 0;
}

参考: https://blog.csdn.net/u012891472/article/details/52641838

author : lukelmouse