Si tengo un número entero n, ¿cómo puedo encontrar el siguiente número k > n tal que k = 2^i, con algunos i elemento de N por bit a bit desplazamiento o la lógica.

Ejemplo: Si tengo n = 123, ¿cómo puedo encontrar k = 128, que es una potencia de dos, y no 124 que sólo es divisible por dos. Este debe ser simple, pero se me escapa.

InformationsquelleAutor AndreasT | 2009-08-24

17 Comentarios

  1. 95

    De enteros de 32 bits, esta es una forma simple y sencilla ruta:

    unsigned int n;
    
    n--;
    n |= n >> 1;   //Divide by 2^k for consecutive doublings of k up to 32,
    n |= n >> 2;   //and then or the results.
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;           //The result is a number of 1 bits equal to the number
                   //of bits in the original number, plus 1. That's the
                   //next highest power of 2.
    

    He aquí un ejemplo más concreto. Tomemos el número 221, que es 11011101 en binario:

    n--;           //1101 1101 --> 1101 1100
    n |= n >> 1;   //1101 1100 | 0110 1110 = 1111 1110
    n |= n >> 2;   //1111 1110 | 0011 1111 = 1111 1111
    n |= n >> 4;   //...
    n |= n >> 8;
    n |= n >> 16;  //1111 1111 | 1111 1111 = 1111 1111
    n++;           //1111 1111 --> 1 0000 0000
    

    Hay un bit en la novena posición, lo que representa el 2^8, o 256, que es de hecho la mayor potencia de 2. Cada uno de los cambios que se superpone a todas las existentes en bits 1 en el número con algunos de los anteriormente virgen ceros, finalmente, la producción de un número de bits 1 es igual al número de bits en el número original. La adición de uno a ese valor se produce una nueva potencia de 2.

    Otro ejemplo, vamos a utilizar 131, que es 10000011 en binario:

    n--;           //1000 0011 --> 1000 0010
    n |= n >> 1;   //1000 0010 | 0100 0001 = 1100 0011
    n |= n >> 2;   //1100 0011 | 0011 0000 = 1111 0011
    n |= n >> 4;   //1111 0011 | 0000 1111 = 1111 1111
    n |= n >> 8;   //... (At this point all bits are 1, so further bitwise-or
    n |= n >> 16;  //     operations produce no effect.)
    n++;           //1111 1111 --> 1 0000 0000
    

    Y, de hecho, 256 es el siguiente más alto de potencia de 2 de 131.

    Si el número de bits utilizados para representar el número entero en sí misma es una potencia de 2, usted puede seguir extender esta técnica de manera eficiente y de forma indefinida (por ejemplo, agregar un n >> 32 línea de enteros de 64 bits).

    • Me pegaba a él. +1
    • Ah muchas gracias! Tuve un tiempo difícil de entender por qué usted podría doble k cada paso, pero ya que el «doble» de cada ‘1’ se hizo evidente. Gracias por el ejemplo.
    • No hay problema! (Por CIERTO, a ver por qué tienes que ir todo el camino hasta el n >> 16, considere lo que sucede si n es ya una potencia de 2. Usted sólo tendrá un único 1 bit que debe abarcar todas las de la anterior bits, que es por qué el cambio es necesario.)
    • +1 sí, un buen truco, me gusta 🙂 Algunos de los más bits-con los trucos se pueden encontrar aquí: graphics.stanford.edu/~seander/bithacks.html
    • Gran ejemplo, este algoritmo aparece en al menos un lugar en el Api Java y se me confunde.
    • A pesar de esto funciona, pero alguien podría por favor dar una explicación de por qué funciona?
    • Creo que hay una errata en el segundo ejemplo, el número después de la tubería debe ser 0100 0001.
    • ¿Por qué no acaba de desplazamiento de bits hasta que es igual a cero? Parece que sería más rápido.
    • Que tiene registro N turnos. Esta toma de registro(log N) se cambia, por lo que utiliza un menor número de turnos.
    • Sí, probablemente debería haber leído el código más cuidadosamente antes de comentar…
    • No k >= n, no k > n
    • si usted acaba de agregar un n >> 32 línea que usted recibe instrucción ilegal para valores de n > 4611686018427387904 , así que para 64 bits usted necesita una verificación de si n es más allá de la mayor potencia de dos que realmente encaja en el de 64 bits

  2. 29

    No es en realidad una asamblea solución para esto (ya que el 80386 conjunto de instrucciones).

    Puede utilizar la BSR (Bits Escaneo Inverso) de la instrucción para buscar el bit más significativo en su entero.

    bsr exploraciones de los bits, a partir de la
    bit más significativo, en el
    doubleword o el operando de la segunda palabra.
    Si los bits son cero, ZF es
    aclaró. De lo contrario, ZF y el
    poco índice de la primera serie de bits encontrado,
    durante la exploración en el reverso
    dirección, se carga en el
    registro de destino

    (Extraído de: http://dlc.sun.com/pdf/802-1948/802-1948.pdf)

    Y que inc con el resultado 1.

    así:

    bsr ecx, eax  //eax = number
    jz  @zero
    mov eax, 2    //result set the second bit (instead of a inc ecx)
    shl eax, ecx  //and move it ecx times to the left
    ret           //result is in eax
    
    @zero:
    xor eax, eax
    ret
    

    En las nuevas CPU puede utilizar el mucho más rápido lzcnt instrucción (aka rep bsr). lzcnt hace su trabajo en un único ciclo.

    • Si la entrada ya es una potencia de 2, esto no va a volver a pesar de
  3. 21

    Más matemáticamente, sin bucles:

    public static int ByLogs(int n)
    {
        double y = Math.Floor(Math.Log(n, 2));
    
        return (int)Math.Pow(2, y + 1);
    }
    
    • Gracias. Pero yo estaba buscando una de bits «juguetear» manera. 😉
    • +1, no lo que el OP quería, pero curiosamente yo necesitaba una respuesta que se ajuste en una sola expresión en línea: 2 ^ (floor(log(x) / log(2)) + 1)
    • Lo que si la entrada es 0? También, OP preguntó por la mayor potencia de 2, floor busca el siguiente menor potencia de 2, no?
    • Usted obtiene el valor existente. La siguiente parte, y+1, obtiene la mayor potencia.
    • pero si n es ya una potencia de 2, se da la siguiente potencia de 2 en lugar de devolver n
    • Si n es una potencia de dos y desea obtener n en lugar de «la siguiente potencia de dos», puede utilizar 2 ^ ( ceil(log(x) / log(2)) ) lugar. Pero esa no fue la pregunta (…¿cómo puedo encontrar el siguiente número k > n…)
    • Sí, pero el método de registro es inexacto para números más altos de todos modos. si x = 536870912 devuelve 1073741824 en lugar de 536870912.

  4. 12

    Aquí una lógica respuesta:

    function getK(int n)
    {
      int k = 1;
      while (k < n)
        k *= 2;
      return k;
    }
    
    • Ha, así de simple!!! No piensen en ello 🙂
  5. 8

    Aquí Juan Feminella la respuesta implementada como un bucle de modo que puede manejar Python enteros largos:

    def next_power_of_2(n):
        """
        Return next power of 2 greater than or equal to n
        """
        n -= 1 # greater than OR EQUAL TO n
        shift = 1
        while (n+1) & n: # n+1 is not a power of 2 yet
            n |= n >> shift
            shift <<= 1
        return n + 1

    También se vuelve más rápido, si n es ya una potencia de 2.

    Para Python >2.7, este es más sencillo y rápido para la mayoría de las N:

    def next_power_of_2(n):
        """
        Return next power of 2 greater than or equal to n
        """
        return 2**(n-1).bit_length()

    Dado un entero, ¿cómo puedo encontrar la mayor potencia de dos, utilizando bits-cambiando?

    • Si vas a usar poco turnos, que bien podría hacer shift <<= 1 en lugar de shift *= 2. No estoy seguro si eso es realmente más rápido en Python, pero debería ser.
  6. 3

    Aquí un salvaje que no tiene bucles, pero utiliza un intermedio de flotación.

    // compute k = nextpowerof2(n)
    
    if (n > 1) 
    {
      float f = (float) n;
      unsigned int const t = 1U << ((*(unsigned int *)&f >> 23) - 0x7f);
      k = t << (t < n);
    }
    else k = 1;
    

    Este, y muchos otros de bits con los hacks, como el presentado por Juan Feminella, se puede encontrar aquí.

    • wtf! 😎 , lo comprobará. Thx
  7. 3

    Mayor que Mayor o igual que

    Los siguientes fragmentos de código son para el siguiente número k > n tal que k = 2^i

    (n=123 => k=128, n=128 => k=256) como se indica en OP.

    Si quieres la menor potencia de 2 mayor que O igual a n, a continuación, sólo tiene que sustituir __builtin_clzll(n) por __builtin_clzll(n-1) dentro de los anteriores fragmentos.

    C++11, utilizando GCC o Clang (64 bits)

    constexpr uint64_t nextPowerOfTwo64 (uint64_t n)
    {
        return 1ULL << (sizeof(uint64_t) * 8 - __builtin_clzll(n));
    }
    

    Mejora el uso de CHAR_BIT propuesto por martinec

    #include <cstdint>
    
    constexpr uint64_t nextPowerOfTwo64 (uint64_t n)
    {
        return 1ULL << (sizeof(uint64_t) * CHAR_BIT - __builtin_clzll(n));
    }
    

    C++17 uso de GCC o Clang (de 8 a 128 bits)

    #include <cstdint>
    
    template <typename T>
    constexpr T nextPowerOfTwo64 (T n)
    {
       T clz = 0;
       if constexpr (sizeof(T) <= 32)
          clz = __builtin_clzl(n); //unsigned long
       else if (sizeof(T) <= 64)
          clz = __builtin_clzll(n); //unsigned long long
       else { //See https://stackoverflow.com/a/40528716
          uint64_t hi = n >> 64;
          uint64_t lo = (hi == 0) ? n : -1ULL;
          clz = _lzcnt_u64(hi) + _lzcnt_u64(lo);
       }
       return T{1} << (CHAR_BIT * sizeof(T) - clz);
    }
    

    Otros compiladores

    Si utiliza un compilador distinto de GCC o Clang, por favor visite la página de la Wikipedia listado de la Recuento de Ceros a la izquierda bit a bit funciones:

    • Visual C++ 2005 => Reemplazar __builtin_clzl() por _BitScanForward()
    • Visual C++ 2008 => Reemplazar __builtin_clzl() por __lzcnt()
    • icc => Reemplazar __builtin_clzl() por _bit_scan_forward
    • GHC (Haskell) => Reemplazar __builtin_clzl() por countLeadingZeros()

    Contribución de bienvenida

    Por favor proponer mejoras en los comentarios. También proponer alternativas para el compilador que uso, o de su lenguaje de programación…

    Ver también respuestas similares

  8. 2

    Si utiliza GCC, MinGW o Clang:

    template <typename T>
    T nextPow2(T in)
    {
      return (in & (T)(in - 1)) ? (1U << (sizeof(T) * 8 - __builtin_clz(in))) : in;
    }
    

    Si utiliza Microsoft Visual C++, utilice la función de _BitScanForward() para reemplazar __builtin_clz().

  9. 1

    De bits cambiando, dice usted?

    long int pow_2_ceil(long int t) {
        if (t == 0) return 1;
        if (t != (t & -t)) {
            do {
                t -= t & -t;
            } while (t != (t & -t));
            t <<= 1;
        }
        return t;
    }
    

    Cada bucle tiras el menos significativo de 1 bit directamente. N. B. Esto sólo funciona cuando firmó números están codificados en complemento a dos.

    • Puede reemplazar con seguridad su while con do/while y guardar una prueba, como ya has confirmado que la prueba inicial con el anterior if declaración.
    • Gracias @seh; mejora con do while.
    • Método más rápido aquí, por qué no upvotes? Aunque, he cambiado a while(t > (t & -t)).
    • Al menos en C# aceptado respuesta es más de 2,5 veces más rápido en promedio para los enteros de 32 bits.
  10. 0

    ¿Qué pasa con algo como esto:

    int pot = 1;
    for (int i = 0; i < 31; i++, pot <<= 1)
        if (pot >= x)
            break;
    
  11. 0

    Usted sólo tiene que encontrar el bit más significativo y elevarla a la izquierda una vez. He aquí una implementación de Python. Creo x86 tiene una instrucción para obtener la MSB, pero aquí estoy implementando todo en la recta de Python. Una vez que usted tiene el MSB es fácil.

    >>> def msb(n):
    ...     result = -1
    ...     index = 0
    ...     while n:
    ...         bit = 1 << index
    ...         if bit & n:
    ...             result = index
    ...             n &= ~bit
    ...         index += 1
    ...     return result
    ...
    >>> def next_pow(n):
    ...     return 1 << (msb(n) + 1)
    ...
    >>> next_pow(1)
    2
    >>> next_pow(2)
    4
    >>> next_pow(3)
    4
    >>> next_pow(4)
    8
    >>> next_pow(123)
    128
    >>> next_pow(222)
    256
    >>>
    
    • Hablando de la asamblea en Python respuesta no agrega ningún valor ya que Python utiliza código de bytes…
  12. 0

    Olvides de esto! Utiliza bucle !

         unsigned int nextPowerOf2 ( unsigned int u)
         {
             unsigned int v = 0x80000000; //supposed 32-bit unsigned int
    
             if (u < v) {
                while (v > u) v = v >> 1;
             }
             return (v << 1);  //return 0 if number is too big
         }
    
  13. 0
    private static int nextHighestPower(int number){
        if((number & number-1)==0){
            return number;
        }
        else{
            int count=0;
            while(number!=0){
                number=number>>1;
                count++;
            }
            return 1<<count;
        }
    }
    
  14. -3
    //n is the number
    int min = (n&-n);
    int nextPowerOfTwo = n+min;
    
    • Es esta idea: llene todos los 1s hasta el más grande, actualmente ‘en’ bits? Si es así, sería n+min+1?
    • Esto no funciona, por desgracia. Pruebe, por ejemplo, para n=19
    • Esta falla. (5 & -5) = 1; 5 + 1 = 6.
  15. -3
    #define nextPowerOf2(x, n) (x + (n-1)) & ~(n-1)
    

    o incluso

    #define nextPowerOf2(x, n)  x + (x & (n-1)) 
    

Dejar respuesta

Please enter your comment!
Please enter your name here