c++ - 获取下一个不连续的二进制数

Question

我一直在做一个问题，其中我得到了一个数字，比如 5(101)没有任何连续的数字，我需要找到下一个没有连续数字的数字。

接下来是 6 (110)、7 (111)、8 (1000)。所以我的答案应该是 8。

除了转到下一个数字并查看连续的位之外，谁能告诉我该方法。

Answer 1

解决此问题的一种快速方法是扫描数字的位，直到找到两个连续的 1。发生这种情况时，您想修复它。换句话说，您想创建一个比当前数字稍大的数字。究竟大多少？

考虑 11 两侧的位:

...11...

我们假设 11... 是当前数字的后缀。想象一下，我们一直向后缀添加 1，直到 11 消失。什么时候会发生？好吧，11 不会变成 10 或 01，因为那样会使它变小。我们只是在增加数量。

11 只有在后缀变为 00... 时才会消失。最小的此类后缀由全零组成。因此，当我们遇到 11 时，我们可以立即将它和它后面的所有位清零。然后我们将 1 添加到后缀左侧的位。

例如，考虑这个数字中最右边的 11:

        1000101011000100
                ^^
        suffix: 11000100
prefix: 10001010

我们将后缀清零并在前缀上加一:

        suffix: 00000000
prefix: 10001011
result: 1000101100000000

现在我们继续向左搜索，寻找下一个 11。

下面的函数右移将后缀置零，前缀加一，左移恢复前缀位置。

int next(int x) {              /* Look for a number bigger than x. */
  x += 1;
  int mask = 3,                /* Use the mask to look for 11.     */
      pos = 2;                 /* Track our location in the bits.  */
  while (mask <= x) {
    if ((mask & x) == mask) {  /* If we find 11, shift right to    */
      x >>= pos;               /*  zero it out.                    */
      x += 1;                  /* Add 1, shift back to the left,   */
      x <<= pos;               /*  and continue the search.        */
    }
    mask <<= 1;                /* Advance the mask (could advance  */
    pos += 1;                  /*  another bit in the above case). */
  }                            
  return x;
}

这种方法对输入的每一位执行恒定数量的操作，使其比蛮力方法快很多。形式上，运行时间是输入大小的对数。

下面是一个完整的程序，它在命令行上获取 x 的值。

#include <stdlib.h>
#include <stdio.h>

void display(int x) {
  int p = 1;
  while (p < x) {
    p <<= 1;
  }
  while (p != 0) {
    printf("%d", (x & p) ? 1 : 0);
    p >>= 1;
  }
}

int next(int x) {              /* Look for a number bigger than x. */
  x += 1;
  int mask = 3,                /* Use the mask to look for 11.     */
      pos = 2;                 /* Track our location in the bits.  */
  while (mask <= x) {
    if ((mask & x) == mask) {  /* If we find 11, shift right to    */
      x >>= pos;               /*  zero it out.                    */
      x += 1;                  /* Add 1, shift back to the left,   */
      x <<= pos;               /*  and continue the search.        */
    }
    mask <<= 1;                /* Advance the mask (could advance  */
    pos += 1;                  /*  another bit in the above case). */
  }                            
  return x;
}

int main(int arg_num, char** args) {
  int x, y;
  if (arg_num != 2) {
    printf("must specify a number\n");
    return 0;
  }
  x = atoi(args[1]);
  y = next(x);
  printf("%d -> %d\n", x, y);
  display(x);
  printf(" -> ");
  display(y);
  printf("\n");
  return 0;
}