CODEWITHSUNDEEP
calgorithmintegerbit-manipulation
adi
adi

Reputation: 590

Calculate the smallest integer with k bits set that is greater than another integer x?

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.

Upvotes: 5

Views: 833

Answers (1)

Evgeny Kluev
Evgeny Kluev

Reputation: 24657

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

Upvotes: 6

Related Questions