Başka bir tam sayıdan x daha büyük olan k bit kümesiyle en küçük tamsayı hesaplayın x?

Question

En küçük tamsayıyı tam olarak bit kümesiyle hesaplamak istiyorum, bu x başka bir tam sayıdan büyük. k=2 için, cevap 1010000 k=4 için olmalı x = 1001010 sonra Örneğin

, cevap 1001011 olmalı ve k=5 için cevap 1001111

Ben biri en az olarak ayarlamanız gerekir olacağını düşünüyorum x tamsayısında ayarlanan en soldaki bitler gibi birçok bit ve daha sonra, x'da bir sonraki en soldaki ayar bitine bitişik MSB tarafındaki bit ayarını yapmak veya bir sonraki en soldaki ayar bitini ayarlamak arasında seçim yapın ve daha sonra bitleri tekrarlayarak tekrar ayarlamaya bakın. sa işlemek; tüm süre k bitten kalan bit sayılır.

Doğru yaklaşım olup olmadığından emin değilim.

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

---

İkinci döngü optimize edilebilir:

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