下一个更高的数字,一个零位

有三种情况.

该数字x在其二进制表示中具有多于一个零位.除了这些零位之外的所有零位必须用1"填充"以获得所需的结果.请注意,通过获取x和填充其一个或多个低阶零位获得的所有数字在数值上更接近于x通过仅填充最顶部的零位获得的数字.因此,答案是x填充零位全部但只有一个的数字:只有其最顶部的零位保持未填充.例如,如果x=110101001那么答案是110111111.为了得到答案,发现该指数i最上面的零位的x,然后计算该位或中x和2^i - 1.

这种情况的C代码:

// warning: this assumes x is known to have *some* (>1) zeros!
unsigned next(unsigned x)
{
  unsigned topmostzero = 0;
  unsigned bit = 1;
  while (bit && bit <= x) {
      if (!(x & bit)) topmostzero = bit;
      bit <<= 1;
  }
  return x | (topmostzero - 1);
}

数字x在二进制中没有零位.这意味着x=2^n - 1一些数字n.通过与上述相同的推理,答案就是如此2^n + 2^(n-1) - 1.例如,如果x=111,那么答案是1011.

数字x在其二进制表示中恰好具有一个零位.我们知道结果必须严格大于x,所以x不允许自己作为答案.如果x在其最低有效位中只有零,那么这种情况减少到情况#2.否则,零点应该向右移动一个位置.假设x其i第-8位为零,则答案应该在i-1第n位为零.例如,如果x=11011,那么结果是11101.