Calcola il numero intero più piccolo con k bit impostato maggiore di un altro intero x?

Question

Desidero calcolare il numero più piccolo con esattamente il bit k impostato, ovvero maggiore di un altro numero intero x.

Per esempio, se x = 1001010 poi per k=2, la risposta dovrebbe essere 1010000 per k=4, la risposta dovrebbe essere 1001011 e per k=5 la risposta è 1001111

credo che uno avrebbe bisogno di impostare almeno altrettanto molti bit come i bit più a sinistra impostati nel numero intero x, quindi scegliere tra l'impostazione del bit MSB-side adiacente al bit più prossimo più a sinistra in x o l'impostazione del bit più a sinistra successivo e quindi osservare l'impostazione dei bit che seguono ripetendo il sa processo mio; per tutto il tempo contando i bit lasciati fuori dal k.

Non sono sicuro se questo è l'approccio corretto.

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

---

secondo ciclo può essere ottimizzata:

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