用相同的设置位数查找下一个更大的数字 [英] Finding next bigger number with same number of set bits

问题描述

我正在解决一个给定数字n的问题，我必须找到具有相同设置位数的下一个更大的元素.在Internet上搜索时，我发现了一段有趣的代码，它只需几行代码(BIT MAGIC)

I'm working on a problem where I'm given a number n, I have to find the next larger element with same number of set bits. While searching on Internet, I found an interesting piece of code which does this in few lines of code (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);
}

但是我想了解有关该算法将始终有效的基本逻辑.所有边界案例将得到妥善处理.

But I want to understand the underlying logic about the algorithm that it will work always. All the boundary cases will be handled properly.

有人可以简单地解释一下逻辑吗?

Can someone please explain the logic in simple steps.

谢谢

推荐答案

在下一个更高的数字中，1的最右行中最左边的1与它的左侧的0交换位置，而剩余的1移到最右边.

In the next higher number, the leftmost 1 of the rightmost run of 1s exchanges place with the 0 to its left, while the remaining 1s move to the far right.

• 代码隔离了最低的1
• 将其添加到a(使纹波传递到下一个更高的0，将所有这些位取反)
• 异或运算得到的最低有效位，向左延伸一个位置.
• 将其向右移动两个位置，将其左边界移到原始位置的右一个位置 (从最高位置留出那个0的位置)，
• 除以最低的1可以为a的右端增加更多的0位.

• The code isolates lowest 1,
• adds it to a (making carries ripple through to the next higher 0, inverting all those bits)
• The ex-or gets the least significant run of ones, extended one position to the left.
• Shifting it right two positions takes its left boundary one position right of the original one (leaving place for that one 0 from the high position),
• dividing by the lowest 1 makes room for as many 0-bits more as there were on the right end of a.

这篇关于用相同的设置位数查找下一个更大的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！