algorithm - una - wiegand 32 bits

Manera eficiente de encontrar Siguiente Número más pequeño con el mismo número de 1 bits

Question

Estoy trabajando en esta cuestión y propongo una solución (puede ser una o dos condiciones que se deben agregar), pero no estoy seguro de si esta es la manera correcta de hacerlo y me resulta incómodo usar dos bucles y no estoy seguro si esto es la manera eficiente de hacerlo. Sería genial si alguien tiene algún buen truco para hacerlo o cualquier mejor enfoque sería bienvenido :). (El lenguaje no es una barrera)

Mi algoritmo:

• Primero encuentre el primer bit ''1'' lsb en el número
• luego encuentra el siguiente bit configurado que está al lado de este bit ''0''
• Cambie el que encuentre ''0'' bit por 1 y ''1'' bit por ''0''
• El número que obtendrás es el siguiente más pequeño
• si todo el bit está configurado, entonces no tiene ningún número que sea el siguiente más pequeño con el mismo número de ''1'' bits.

void nextSmaller(int number) {
    int firstZeroBitHelper = 1, nextOneBitHelper;
    while (firstZeroBitHelper < number) {
        // when we find first lsb zero bit we''ll stop
        bool bit = number & firstZeroBitHelper;
        if (bit == false)
            break;
        firstZeroBitHelper = firstZeroBitHelper << 1;
    }

    if (firstZeroBitHelper >= number) {
        cout << "No minimum number exists" << endl;
        return;
    }

    nextOneBitHelper = firstZeroBitHelper;
    nextOneBitHelper = nextOneBitHelper << 1;

    while (nextOneBitHelper < number) {
        // when we get ''1'' after the previous zero we stop
        bool bit = number & nextOneBitHelper;
        if (bit == true)
            break;
        nextOneBitHelper = nextOneBitHelper << 1;
    }

    // change the first zero to 1
    number = number | firstZeroBitHelper;
    // change the next set bit to zero
    number = number & ~nextOneBitHelper;

    cout << number << endl;
}

Answer 1

Continuando con mi comentario ...

Bueno, lo encontré, y bastante rápido también. Consulte el capítulo 7.1.3 de El arte de la programación de computadoras (en el volumen 4A), responda a la pregunta 21: "al revés del truco de Gosper".

Se parece a esto:

t = y + 1;
u = t ^ y;
v = t & y;
x = v - (v & -v) / (u + 1);

Donde y es la entrada y x el resultado. Las mismas optimizaciones que en el truco de Gosper se aplican a esa división.

Answer 2

El algoritmo que describiste no es del todo correcto; hace todo bien excepto un detalle. Cualquier número binario tiene la siguiente forma, que se encuentra en el medio de su algoritmo:

xxxxx...10000...1111...
         ---n---// f // 

Aquí xxx... son bits arbitrarios, y los números de ceros consecutivos y unos están determinados por firstZeroBitHelper y nextOneBitHelper ( f y n ).

Ahora tiene que disminuir este número dejando la misma cantidad de bits configurados, lo que necesariamente convierte el 1 a 0 más significativo:

xxxxx...0????...????...
         -----n+f------ 

Tenga en cuenta que cualquier valor para los bits ??? hace que el nuevo número sea menor que el original, y realmente desea elegir estos bits para que el número resultante tenga el valor máximo:

xxxxx...011111...0000...
         ---f+1--//n-1// 

Por lo tanto, debe voltear no solo 2 bits, sino también f+2 bits (un bit de 1 a 0 , y f+1 otros de 0 a 1 ).

Una forma de hacerlo es la siguiente.

Primero apague todos los bits relevantes:

number &= ~nextOneBitHelper;
number &= ~(nextOneBitHelper - 1);

Ahora encienda los bits necesarios, comenzando desde MSB:

nextOneBitHelper >>= 1;
while (firstZeroBitHelper != 0)
{
    number |= nextOneBitHelper;
    nextOneBitHelper >>= 1;
    firstZeroBitHelper >>= 1;
}

Es posible implementar el trenzado de bits descrito anteriormente sin bucles; para eso necesitarías calcular n y f . Habiendo hecho eso:

unsigned mask = (1 << (f + 1)) - 1; // has f+1 bits set to 1
mask <<= n - 1; // now has these bits at correct positions
number |= mask; // now the number has these bits set

Answer 3

Yendo hacia arriba:

• Encuentre la ocurrencia más a la derecha de "01" en el número y conviértalo en "10".
• Justifique todos los siguientes 1 bit lo más a la derecha posible.

Yendo hacia abajo:

• Encuentre la ocurrencia más a la derecha de "10" en el número y conviértalo en "01".
• Justifica a la izquierda todos los siguientes 1 bit (es decir, no hagas nada si el bit que acabas de configurar ya está seguido de un 1).

Un ejemplo para aclarar el caso a la baja:

• 225 = 0b11 10 0001
• Intercambio: 0b11 01 000 1
• Left-justify: 0b1101 1 000 = 216

Explicaré el caso de ir hacia arriba primero, porque me parece menos complicado. Queremos encontrar la posición menos significativa donde podamos mover una posición de 1 bit a la izquierda (en otras palabras, el 0 más a la derecha que tiene un 1 a su derecha). Debería quedar claro que este es el bit más a la derecha que podemos establecer, ya que tenemos que borrar un poco en otro lugar para cada bit que establecemos, y tenemos que despejar un poco en algún lugar a la derecha del bit que establecemos, o bien el número se hará más pequeño en lugar de más grande.

Ahora que hemos establecido este bit, queremos borrar un bit (para restablecer el número total de bits establecidos) y reorganizar los bits restantes para que el número sea lo más pequeño posible (esto lo convierte en el siguiente número más grande con el el mismo número de bits establecidos). Podemos despejar el bit a la derecha del que acabamos de configurar, y podemos empujar cualquier 1 bit restante lo más derecho posible sin temor a ir por debajo de nuestro número original, ya que todos los bits menos significativos juntos todavía se suman a menos que el único bit que acabamos de configurar.

Encontrar el siguiente número más bajo en lugar del siguiente más alto es básicamente el mismo, excepto que estamos buscando la posición más a la derecha donde podemos mover un bit determinado una posición correcta , y luego de hacerlo queremos mover todos los bits menos significativos como más a la izquierda como sea posible.

Parece que otros tienen las versiones de este pozo en mano, pero quería ver si podía dar una buena explicación del lado lógico / matemático del algoritmo.

Answer 4

#include <iostream>

bool AlmostdivBy2(int num) {
    return (-~num & (num)) == 0;
}

void toggleright(int &num) {
    int t;
    for (t = -1; num & 1; t++)
        num >>= 1;
    ++num = (num << t) | ~-(1 << t);
}

void toggleleft(int &num) {
    while (~num & 1)
        num >>= 1; //Simply keep chopping off zeros
    //~num & 1 checks if the number is even
    //Even numbers have a zero at bit at the rightmost spot
}

int main() {

    int value;
    std::cin >> value;
    if (!AlmostdivBy2(value)) {
        (~value & 1) ? toggleleft(value) : toggleright(value);
    }
    std::cout << value << "/n";
    return 0;
}

Creo que podría haber pensado demasiado en esto, pero aquí está mi explicación:

• Si el número está cerca de ser una potencia de 2, es decir, valores como 1, 3, 7, 15, 31, ..., entonces no hay ningún valor más pequeño que el que podría tener el mismo número de unidades en su representación binaria. Por lo tanto, no nos preocupamos por estos números.

• si el número es par, esa es otra solución fácil, simplemente seguimos cortando ceros desde el final hasta que el número sea impar

• Los números impares presentaron el mayor desafío por lo que es recursivo. Primero tenía que encontrar el primer bit cero comenzando desde la derecha del número. Cuando se encuentra esto, agregas uno a ese número que convertirá ese último bit en 1. A medida que la recursión se desenrolla, sigues desplazando los bits hacia la izquierda y agregando uno. Cuando se hace esto, tienes el siguiente más pequeño.

Espero no confundirte

EDITAR

Trabajé en eso más y aquí hay una versión no recursiva de toggleright

void toggleright(int &num) {    
    int t = 1;
    while ( (num >>= 1) & 1 && t++ );
    num = (-~num << ~-t) | ~-(1 << t);    
}

Answer 5

anatolyg cubrió tu algoritmo bastante bien, pero hay una solución más eficiente.

Puedes usar el truco de Gosper con una comprensión inteligente de que si giras los bits, Gosper produce los valores en orden descendente.

Algo así como este pseudocódigo funcionaría:

let k := number
let n := num bits in k (log base 2)
k = k ^ ((1 << n) - 1)
k = gosper(k)
k = k ^ ((1 << n) - 1)
return k

Esto le da un buen algoritmo O (1) (o O (log n) si considera xor ser tiempo lineal). :)

Hay algunos casos que debes considerar, como si k=2^x-1 para alguna x , pero eso es bastante fácil de atrapar.