计算具有k位的最小整数设定为比另一个整数x更大？ [英] Calculate the smallest integer with k bits set that is greater than another integer x?

问题描述

我想正是 K 设置位计算的最小整数，比另一个整数 X 更大。

例如，如果 X = 1001010 然后
为 K = 2 ，答案应该是 1010000
为 K = 4 ，答案应该是 1001011
和 K = 5 答案是 1001111

我认为一个人需要至少设置为多少位作为整数 X 设置最左边位，然后设置MSB端位相邻之间进行选择在 X ，或设置，重复同样的过程的下一个最左边的设置一下，再看看下面的设置位的下一个最左边的设置位;所有的同时计数位冷落的k的。

我不知道这是否是正确的做法。

解决方案

  ++ X;而（POPCNT（X）＆GT; K）
{
    //替换位的最低显著组
    //单位对他们的左
    X | = X-1;
    + X;
}无符号位= 1;
而（POPCNT（X）LT; K）
{
    X | =位;
    比特下;＆下; = 1;
}
 

---

二回路可以进行优化：

 对（我= K  -  POPCNT（X）！I = 0; --i）
{
    //设置最低的非集位
    X | = X + 1;
}
 

I want to calculate the smallest integer with exactly k bits set, that is greater than another integer x.

For example if x = 1001010 then for k=2, the answer should be 1010000 for k=4, the answer should be 1001011 and for k=5 the answer is 1001111

I think that one would need to set at least as many bits as the leftmost bits set in the integer x, and then choose between setting the MSB-side bit adjacent to the next leftmost set bit in x, or setting the next leftmost set bit and then look at setting the bits following that by repeating the same process; all the while counting the bits left out of the k.

I am not sure if this is the correct approach.

解决方案

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

---

Second loop may be optimized:

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

这篇关于计算具有k位的最小整数设定为比另一个整数x更大？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！