获取下一个非连续的二进制数

Question

我一直在做一个问题,其中我给了一个数字,让我们说5(101)没有任何连续的,我需要找到下一个没有连续的数字.

接下来是6(110),7(111),8(1000).所以我的回答应该是8.

任何人都可以告诉我这种方法,除了转到下一个数字并看到连续的位.

Answer 1

解决此问题的一种快速方法是扫描数字的位,直到找到两个连续的1s.发生这种情况时,您需要修复它.换句话说,您想要使数字略大于当前数字.真的多大了多少？

考虑以下两侧的位11:

...11...

我们会说这11...是当前数字的后缀.想象一下,我们继续在后缀中加1,直到11消失.什么时候会发生？好吧,11不会变成10或者01,因为那会使它变小.我们只是增加了这个数字.

将11只会当后缀变消失00....最小的此类后缀由全零组成.因此,当我们遇到a时11,我们可以立即将其清零并将其后的所有位清零.然后我们添加1到后缀左侧的位.

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

        1000101011000100
                ^^
        suffix: 11000100
prefix: 10001010

我们将后缀清零并在前缀中添加一个:

        suffix: 00000000
prefix: 10001011
result: 1000101100000000

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

以下函数右移到后缀为零,在前缀中加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;
}

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

下面是一个完整的程序,它接受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;
}