找到下一个具有相同设置位数的更大数字

Question

我正在解决一个问题，给定一个数字 n，我必须找到下一个具有相同设置位数的较大元素。在互联网上搜索时，我发现了一段有趣的代码，只需几行代码即可完成此操作（BIT MAGIC）here：

unsigned nexthi_same_count_ones(unsigned a) {
  /* works for any word length */
  unsigned c = (a & -a);
  unsigned r = a+c;
  return (((r ^ a) >> 2) / c) | r;  // original typo corrected
}

但我想了解该算法始终有效的底层逻辑。所有边界情况都会得到妥善处理。

有人可以用简单的步骤解释一下逻辑吗？

谢谢

Answer 1

在下一个更高的数字中，最右边的

1

中最左边的

1

与其左侧的

0

交换位置，而其余

1

则移至最右侧。

• 代码隔离了最低的

  1

  ，
• 将其添加到

  a

  （使进位波动到下一个更高的

  0

  ，反转所有这些位）
• 前或得到最不重要的一串，向左扩展一个位置。
• 将其向右移动两个位置，使其左边界比原始边界右移一个位置 （从高位给那个

  0

  留位置），
• 除以最低的

  1

  可以为

  0

  右端的

  a

  位腾出空间。

Answer 2

假设我们有一个位模式，例如

111100111 - 代表十进制的 487

为了生成下一个最大整数，同时保留输入中 0 和 1 的数量，我们需要找到输入右侧的第一个 0 位，后跟 1，并且需要将该位切换为 1。然后，我们需要将该翻转点右侧的 1 数量减少 1，以补偿我们从 0 切换到 1 的位。

我们的新位模式将变成 111101011 - 十进制 491（我们保留了设置的位数，而不是根据输入设置）

int getNextNumber(int input)
{
    int flipPosition=0;
    int trailingZeros=0;
    int trailingOnes=0;
    int copy = input;

    //count trailing zeros
    while(copy != 0 && (copy&1) == 0 )
    {
        ++trailingZeros;

        //test next bit
        copy = copy >> 1;
    }

    //count trailing ones
    while(copy != 0 && (copy&1) == 1 )
    {
        ++trailingOnes;

        //test next bit
        copy = copy >> 1;
    }

    //if we have no 1's we cannot form another patter with the same number of 1's
    //which will increment the input, or if we have leading consecutive
    //zero's followed by consecutive 1's up to the maximum bit size of a int
    //we cannot increase the input whilst preserving the no of 0's and
    //1's in the original bit pattern
    if(trailingZeros + trailingOnes  == 0 || trailingZeros + trailingOnes == 31)
        return -1;

    //flip first 0 followed by a 1 found from the right of the bit pattern
    flipPosition = trailingZeros + trailingOnes+1;
    input |= 1<<(trailingZeros+trailingOnes);

    //clear fields to the right of the flip position
    int mask = ~0 << (trailingZeros+trailingOnes);
    input &= mask;

    //insert a bit pattern to the right of the flop position that will contain
    //one less 1 to compensate for the bit we switched from 0 to 1
    int insert = flipPosition-1;
    input |= insert;

    return input;
}