Écrire une fonction qui, pour un non n donné, trouve un nombre p qui est supérieur ou égal à n et qui est la plus petite puissance de 2. 

Exemples : 

Entrée : n = 5
Sortie : 8     

Entrée : n = 17
Sortie : 32     

Entrée : n = 32
Sortie : 32     

Il existe de nombreuses solutions pour cela. Prenons l'exemple de 17 pour en expliquer quelques-uns. 

Méthode 1 (en utilisant le journal du nombre) 

    1. Calculer la position du bit défini dans p (puissance suivante de 2) :
        pos = ceil(lgn) (plafond de log n de base 2)
    2. Calculez maintenant p :
        p = pow(2, pos)

Exemple : 

    Essayons pour 17
            position = 5
            p = 32    

Méthode 2 (En obtenant la position du seul bit défini dans le résultat) 

    /* Si n est une puissance de 2 alors retourne n */
    1 Si (n & !(n&(n-1))) alors retourne n
    2 Sinon, continuez à droite en décalant n jusqu'à ce qu'il devienne zéro
        et compter le nombre de quarts de travail
        un. Initialiser : compte = 0
        b. Alors que n ! = 0
                n = n>>1
                compter = compter + 1

     /* Count a maintenant la position du bit défini dans le résultat */
    3 Retour (1 << compte)

Exemple : 

    Essayons pour 17
                 compter = 5
                 p = 32  

unsigned int nextPowerOf2(unsigned int n)

{

unsigned count = 0;

 

// First n in the below condition

// is for the case where n is 0

if (n && !(n & (n - 1)))

    return n;

 

while( n != 0)

{

    n >>= 1;

    count += 1;

}

 

return 1 << count;

}

 

// Driver Code

int main()

{

unsigned int n = 0;

printf("%d", nextPowerOf2);

return 0;

}

Complexité temporelle : O(log n)
Espace auxiliaire : O(1)

Méthode 3 (décaler le résultat un par un) 
Merci à coderyogi d'avoir suggéré cette méthode. Cette méthode est une variante de la méthode 2 où au lieu de compter, nous décalons le résultat un par un dans une boucle. 

unsigned int nextPowerOf2(unsigned int n)

{

    unsigned int p = 1;

    if (n && !(n & (n - 1)))

        return n;

 

    while (p < n)

        p <<= 1;

     

    return p;

}

 

// Driver Code

int main()

{

unsigned int n = 5;

printf("%d", nextPowerOf2);

return 0;

}

Production

8

Complexité temporelle : O(log) 
Espace auxiliaire : O(1)

Méthode 4 (personnalisée et rapide) 

    1. Soustraire n par 1
       n = n-1

    2. Définissez tous les bits après le bit défini le plus à gauche.

    /* La solution ci-dessous ne fonctionne que si l'entier est de 32 bits */
                n = n | (n >> 1);
                n = n | (n >> 2);
                n = n | (n >> 4);
                n = n | (n >> 8);
                n = n | (n >> 16);
    3. Retour n + 1

Exemple : 

Les étapes 1 et 3 de l'algorithme ci-dessus permettent de gérer les cas
de puissance de 2 nombres, par exemple, 1, 2, 4, 8, 16,

    Essayons pour 17(10001)
    étape 1
       n = n - 1 = 16 (10000)  
    étape 2
       n = n | n >> 1
       n=10000 | 01000
       n=11000
       n = n | n >> 2
       n=11000 | 00110
       n = 11110
       n = n | n >> 4
       n = 11110 | 00001
       n = 11111
       n = n | n >> 8
       n = 11111 | 00000
       n = 11111
       n = n | n >> 16
       n = 11110 | 00000
       n = 11111    

    étape 3 : Retour n+1
     On obtient n + 1 comme 100000 (32)

unsigned int nextPowerOf2(unsigned int n)

{

    n--;

    n |= n >> 1;

    n |= n >> 2;

    n |= n >> 4;

    n |= n >> 8;

    n |= n >> 16;

    n++;

    return n;

}

 

// Driver Code

int main()

{

    unsigned int n = 5;

    printf("%d", nextPowerOf2);

    return 0;

}    

Complexité temporelle : O(log) 
Espace auxiliaire : O(1)

Approche efficace :
si le nombre donné est la puissance de deux, c'est le nombre requis, sinon définissez uniquement le bit de gauche du bit le plus significatif qui nous donne le nombre requis.

long long nextPowerOf2(long long N)

{

    // if N is a power of two simply return it

    if (!(N & (N - 1)))

        return N;

    // else set only the left bit of most significant bit

    return 0x8000000000000000 >> (__builtin_clzll(N) - 1);

}

 

// Driver Code

int main()

{

    long long n = 5;

    printf("%lld", nextPowerOf2);

    return 0;

}

Production

8

Complexité temporelle : O(1) car le comptage des zéros non significatifs peut entraîner une complexité temporelle maximale de O(64).
Espace auxiliaire : O(1)