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

Question

我正在解决一个问题，我得到了一个数字 n，我必须找到下一个具有相同设置位数的更大元素。在 Internet 上搜索时，我发现了一段有趣的代码，只需几行代码即可完成此操作 (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);
}

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

谁能用简单的步骤解释一下逻辑。

谢谢

Answer 1

在下一个更高的数字中，最左边的 1最右边的 1与0交流的地方在它的左边，而剩下的1让我们移到最右边。

• 代码隔离最低1 ,
• 将其添加到 a (使波纹传递到下一个更高的 0，反转所有这些位)
• ex-or 获得最不重要的一连串，向左扩展一个位置。
• 将其向右移动两个位置使其左边界在原始边界右侧移动一个位置(从高位留给那个0)，
• 除以最低 1为尽可能多的人腾出空间0 -比a的右端多一点.