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

Question

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

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

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

Answer 1

汉明权重（a.k.a.按位总体计数）减少、不变或增加三种情况。

增加汉明权重

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

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

汉明权重不变

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

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

只要加上"carries a one,"位就会清零。产生的重量必须相等或减少。如果由于进位链导致多个位被清除，则需要通过设置低位来增加补偿权重。

减少汉明权重

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

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