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

Question

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

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

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

Answer 1

存在三种情况:汉明权重(又名按位总体计数)减少、不变或增加。

增加汉明重量

设置足够的连续低位 0 位以获得所需的权重。

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

不变的汉明重量

1. 添加最低 1 位的值。
2. 如有必要，增加上述汉明重量。

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

只要加法“带一”，位就会被清除。所得重量必须相等或减少。如果由于进位链而导致多个位被清除，则需要通过设置低位来增加补偿权重。

减少汉明重量

1. 清除足够的低位 1 位以获得新的所需权重。
2. 按照上述流程保持重量不变。

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