给出一个数字打印下一个具有相同数量的数字

Question

给定一个数字,我们必须找到下一个最高数字和前一个数字,它们的二进制表示中具有相同数量的1位

我的解决方案是一种强力方法,即增加数量并计算1的数量,如果它具有相同数量的1然后打印它

以前的数字与上述方法相同

是否有任何优化的解决方案而不是检查所有数字？

Answer 1

要获得下一个最高数字,只需搜索第一个实例01,从右侧开始并将其更改为10.然后1将交换位右侧的所有s 折叠到最不重要的位置.

例:

 ||
00110000 // 0x30 in hex

交换后:

 ||
01010000 // 0x50 in hex

接下来,将交换位右侧的所有1折叠到最不重要的位置:

 ||---->
01000001 // 0x41 in hex

要获取前一个数字,请搜索10从右侧开始的第一个实例,并将其替换为01.然后0在交换位到达最低位置1之后将所有s 折叠(或者,在交换位之后将所有s 折叠到它们的最重要位置).

例:

    ||
01001001 // 0x48 in hex

交换后:

    ||
01000101 // 0x45 in hex

接下来,将交换位右侧的所有0折叠到最不重要的位置:

    ||->
01000110 // 0x46 in hex

这是一个简短的程序,将显示下一个更高和更低的数字.

#include <iostream>
#include <bitset>
#include <stdlib.h>

using namespace std;
#define NUMSIZE 8       // The number of bits to display

// Finds the first and second values, swaps them, and collapses.
void swap_and_collapse(bitset<NUMSIZE>& num, bool v1, bool v2, bool c) {
  // Find the v1 immediately followed by v2 in the number.
  int insert_pos = 0;
  for (int i=1; i<NUMSIZE; i++) {
    if ((num.test(i-1) == v2) && (num.test(i) == v1)) {
      // Found them.  Swap the values.
      num.flip(i-1); num.flip(i);
      break;
    } else {
      // Move any c bits to the beginning.
      if (num.test(i-1) == c) {
        num.flip(i-1);
        num.flip(insert_pos++);
      } // if (num.test(i-1) == c) 
    } // if ((num.test(i-1) == v2) && (num.test(i) == v1)) 
  } // for (int i=0; i<16; i++)
} // swap_and_collapse

int main(int argc, char* argv[]) {
  // Get the number from the command line and display in binary.
  int value = atoi(argv[1]);
  bitset<NUMSIZE> orig  (value);
  cout << "Original Number " << orig.to_ulong() << " is " << orig << endl;

  // Find the next higher number.
  bitset<NUMSIZE> higher(value);
  swap_and_collapse(higher, 0, 1, 1);
  // Find the next lower number.
  bitset<NUMSIZE> lower (value);
  swap_and_collapse(lower,  1, 0, 0);

  cout << "Higher number   " << higher.to_ulong() << " is " << higher << endl;
  cout << "Lower number    " <<  lower.to_ulong() << " is " <<  lower << endl;
} // main