Geek asks and answers

Compute the smallest integer with a set of k bits that is larger than another integer x?

I want to calculate the smallest integer with exactly set kbits, which is larger than another integer x.

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

It seems to me that you need to set at least as many bits as the left bits specified in the integer x, and then choose between setting the MSB side bit next to the next leftmost bit in x, or set the next leftmost bit to the left, and then look at setting the bits that follow after him, repeating the same process; all the while counting the bit remaining from k.

I am not sure if this is the right approach.

+5
source share
1 answer
++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;
}

The second loop can be optimized:

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

More articles:


All Articles