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

Question

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

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);
}

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

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

谢谢

Answer 1

在下一个更高的数字中，最右边1的 s 串中最左边的s 与其左边的1交换位置，而其余的s 移动到最右边。 01

• 该代码隔离了最低的1，
• 将其添加到a（使进位波动到下一个更高的位0，反转所有这些位）
• 前或得到最不重要的一串，向左扩展一个位置。
• 将其右移两位，使其左边界比原来的右边界右移一位（为该位置0从高位留出位置），
• 除以最低位1可以容纳0与 右端一样多的 - 位a。