c++ - 给定一个数字打印下一个具有相同数量的最大数字

Question

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

我的解决方案是一种蛮力方法，即增加数量和计数 如果它有相同数量的 1，则打印它

对于前面的数字，方法与上面的相同

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

Answer 1

要获得下一个最高数字，只需搜索 01 的第一个实例，从右侧开始并将其更改为 10。然后将交换位右侧的所有 1 折叠到它们的最低有效位置。

例子:

 ||
00110000 // 0x30 in hex

交换后:

 ||
01010000 // 0x50 in hex

接下来，将交换位右侧的所有 1 折叠到最低有效位置:

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

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

例子:

    ||
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