最接近的数

题目描述

有一个正整数，请找出其二进制表示中1的个数相同、且大小最接近的那两个数。(一个略大，一个略小)

给定正整数int x，请返回一个vector，代表所求的两个数（小的在前）。保证答案存在。

测试样例：2
返回：[1,4]

解答

位操作法

取得后一个较大的树

　　以数字13948为例，二进制表示如下：

　　我们想让这个数大一点，但又不会太大，同时1的个数又要保持不变。你会发现：给定一个数 和两个位的位置i和j，假设将位i从1翻转为0，位j从0翻转为1。如果i>j，n就会减小；反之，n就会增大。
继而得到以下几点：

1. 若将某个0翻转成1，就必须将某个1翻转为0
2. 进行位翻转时，如果0变1的位处于1变0的位的左边，这个数字就会变大。
3. 我们想让这个数变大，但又不至于太大，因此必须翻转最右边的0，且它的右边必须还有个1。

也就是说，我们要翻转最右边但非拖尾的0。用上面的例子来说，拖尾0位于第0到第1个位置。因此，最右边但不是拖尾的0处在位置7。我们将这个位置记作p。

• 步骤1：翻转最右边、非拖尾0

  
  　　将位置7翻转后，n就会变大。但是现在n中的1多了一个，0少了一个。我们还需要尽量缩小数值，同时要满足要求。
  　　缩小数值时，可以重新排列p右边的那些位，其中0放到左边，1放到右边。在重新排列的过程中，还要将其中一个1改为0。
  　　有种相对简单的做法是：数出p右方有几个1，将位置0到位置p的所有位清零，然后回填c1-1个1。假设c1是p右方1的个数，c0是p右方0的个数。

• 步骤２：将ｐ右方的所有位清零。由步骤１可知，例子中c0=2，c1=5,p=7
  
  　　为了将这些位清零，需要创建一个掩码，前面是一连串的１，后面跟着ｐ个０，做法如下
  ａ

• 
  　
  　　
  　　
  
  • 步骤2：

最后

以上就是愤怒自行车为你收集整理的最接近的数的全部内容，希望文章能够帮你解决最接近的数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。