查找具有特定汉明重量的下一个数字 [英] Find next number with specific hamming weight
问题描述
给定一个整数 x ，我想计算下一个 更高一个整数 y 汉明体重 w .请记住，x的汉明权重也必须是w.
Given a certain integer x, I wish to compute the next higher integer y which has a certain hamming weight w. Mind that the hamming weight of x does not have to be w as well.
因此，例如x = 10(1010)且w = 4，结果应为y = 15(1111).
So, for example x = 10 (1010) and w = 4 the result should be y = 15 (1111).
很显然，我可以通过增加x来实现这一点，但这对于高数字来说是一个非常慢的解决方案.我可以通过某种方式的移位来实现吗?
Obviously, I could achieve this by just incrementing x but that would be a very slow solution for high numbers. Can I achieve this by the means of bit shifts somehow?
推荐答案
有以下三种情况:汉明权重(又称按位人口数)减少，不变或增加.
There are three cases: the Hamming weight (a.k.a. bitwise population count) is reduced, unchanged, or increased.
设置足够的连续低位0位以达到所需的权重.
Set enough successive low-order 0-bits to achieve the desired weight.
之所以起作用，是因为每个连续的低位是您可以添加的最小值，并且它们的和是可以充分增加汉明权重的最小差.
This works because each successive low-order bit is the smallest value that you can add, and their sum is the smallest difference that will sufficiently increase the Hamming weight.
- 添加最低位1位的值.
- 如有必要，增加上述汉明重量.
之所以起作用，是因为最低设置位的值是将引起进位的最低值.添加任何较低的位值只会设置该位，并增加汉明的权重.
This works because the value of the lowest set bit is the lowest value that will cause a carry to occur. Adding any lower bit-value would simply set that bit, and increase the Hamming weight.
只要加法运算符"1"将被清除.最终的重量必须等于或减小.如果由于一连串的进位而清除了几个位，则需要通过设置低位来增加补偿的权重.
As long as addition "carries a one," bits will be cleared. The resulting weight must be the equal or reduced. If several bits are cleared due to a chain of carries, you'll need to increase the weight in compensation by setting low-order bits.
- 清除足够的低位1位以达到所需的新权重.
- 按照上述步骤操作以保持体重不变.
之所以起作用，是因为清除低位1位会通过减去最小的可行量来找到具有所需权重的前个数字.从正确权重的前一个数字开始，按照不变权重"算法到达下一个数字.
This works because clearing low-order 1-bits finds the preceding number with the desired weight, by subtracting the smallest viable amount. From the preceding number of the correct weight, follow the "unchanged weight" algorithm to reach the next number.
这篇关于查找具有特定汉明重量的下一个数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
