计算设置的k位大于另一个整数x的最小整数？

Question

我想计算精确k位设置的最小整数,大于另一个整数x.

例如,如果x = 1001010然后k=2,答案应该是1010000 对k=4,答案应该是1001011 和k=5答案1001111

我认为需要设置至少与整数中设置的最左边的位一样多的位x,然后在设置与下一个最左边的设置位相邻的MSB侧位x,或者设置下一个最左边的设置位然后选择通过重复相同的过程来设置后面的位; 一直计算k中剩下的位数.

我不确定这是否是正确的方法.

Answer 1

++x;

while (popcnt(x) > k)
{
    // Substitute the least-significant group of bits
    // with single bit to the left of them
    x |= x-1;
    ++x;
}

unsigned bit = 1;
while (popcnt(x) < k)
{
    x |= bit;
    bit <<= 1;
}

可以优化第二循环:

for (i = k - popcnt(x); i != 0; --i)
{
    // Set the lowest non-set bit
    x |= x+1;
}