permutation - 查找具有特定汉明权重的下一个数字

Question

给定一个整数x，我希望计算下一个 更高的整数y，它具有一定的汉明权重w。请注意，x 的汉明权重也不必是 w。

因此，例如 x = 10 (1010) 和 w = 4，结果应该是 y = 15 (1111)。

显然，我可以通过增加 x 来实现这一点，但对于大数字来说，这将是一个非常缓慢的解决方案。我可以以某种方式通过位移来实现这一点吗？

score 2 · Accepted Answer

存在三种情况：汉明权重（也称为按位人口计数）减少、不变或增加。

汉明重量增加

设置足够多的连续低位 0 位以实现所需的权重。

这是有效的，因为每个连续的低位是您可以添加的最小值，并且它们的总和是足以增加汉明权重的最小差异。

这是有效的，因为最低设置位的值是导致进位发生的最低值。添加任何较低的位值将简单地设置该位，并增加汉明权重。

只要加法“携带一个”，位就会被清除。产生的重量必须相等或减少。如果由于一系列进位而清除了几个位，则需要通过设置低位来增加补偿权重。

这是有效的，因为清除低位 1 位通过减去最小可行量来找到具有所需权重的前一个数字。从正确权重的前一个数字开始，按照“不变权重”算法得出下一个数字。