Calcular el entero más pequeño con k bits conjunto que es mayor que otro entero x?

Question

Quiero calcular el número entero más pequeño con exactamente k bits establecidos, que es mayor que otro número entero x.

Por ejemplo, si x = 1001010 continuación para k=2, la respuesta debería ser 1010000 para k=4, la respuesta debería ser 1001011 y para k=5 la respuesta es 1001111

creo que uno tenga que configurar al menos tan muchos bits como los bits más a la izquierda establecidos en el entero x, y luego elija entre configurar el bit del lado MSB adyacente al siguiente bit configurado más a la izquierda en x, o establecer el siguiente bit establecido más a la izquierda y luego ver los siguientes bits repitiendo el sa mi proceso; todo el tiempo contando los bits que quedaron fuera de la k.

No estoy seguro de si este es el enfoque correcto.

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

---

segundo bucle puede ser optimizado:

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