用相同的设置位数寻找下一个更大的数

Question

我在研究一个问题，给我一个数字n，我必须找到下一个更大的元素，有相同的设置位数。当我在网上搜索时，我发现了一段有趣的代码，它在这里用了几行代码（有点神奇）：

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（使pripple通过下一个更高的0，反转所有这些位）
• ex-or得到最小有效运行的一个，向左扩展一个位置。
• 将其向右移动两个位置将使其左边界位于原始边界的右一个位置（从高位离开那个0的位置），
• 除以最低的1可以容纳与A右端相同的0位。