计算比另一个整数x大且具有k个二进制位为1的最小整数是多少？

Question

我想计算比另一个整数x大的恰好有k个位设置的最小整数。

例如，如果x = 1001010，则 对于k=2，答案应为1010000 对于k=4，答案应为1001011 对于k=5，答案是1001111 我认为需要设置至少与整数x中左侧设置的位数相同的位，然后在选择设置相邻于x中下一个左侧设置的位的MSB侧位或设置下一个左侧设置的位之间进行选择，并查看通过重复相同过程设置其后续位；同时计算剩余的未设置的k位。

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

- adi

---

提供示例输入/输出将使您的问题更容易理解。您的意思是这两个整数应该具有相同数量的位设置吗？ - xvatar

@xvatar 我认为x和k都是程序的输入，也就是说，x = 1001010，k = 2会返回1010000。 - ffao

答案应该恰好包含k个设置位还是至少包含k个设置位？ - Colin D

@xvatar，我意识到我的问题应该表述得更清楚。我已经做出了适当的更改。 - adi

@EitanT 不，这不是作业 :-) 。我在解决一个与我在面试中被问到的相关问题时想到的。 - adi

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;
}

- Evgeny Kluev

---

@ffao：在 D.Knuth 的《计算机程序设计艺术》第 4A 卷中有许多这样的技巧。或者在 "Matters Computational" 这本书中也能找到。 - Evgeny Kluev

@EvgenyKluev 谢谢你的回答，也感谢你向我介绍了 gcc popcnt。我之前不知道这个，可能会写一个循环来计算设置位。 - adi