Étant donné un nombre n, trouver la plus grande puissance de 2 qui est inférieure ou égale à n.
Exemples :
Entrée : n = 10 Sortie : 8 Entrée : n = 19 Sortie : 16 Entrée : n = 32 Sortie : 32
Une solution simple consiste à commencer à vérifier à partir de n et à décrémenter jusqu'à ce que nous trouvions une puissance de 2.
int highestPowerof2(int n){ int res = 0; for (int i = n; i >= 1; i--) { // If i is a power of 2 if ((i & (i - 1)) == 0) { res = i; break; } } return res;}// Driver codeint main(){ int n = 10; printf("%d", highestPowerof2
); return 0;}8
Complexité temporelle : O. Dans le pire des cas, la boucle s'exécute floor(n/2) fois. Le pire des cas se produit lorsque n est de la forme 2 x – 1.
Espace auxiliaire : O(1) puisque seul l'espace constant est utilisé pour les variables
Une solution efficace consiste à utiliser l'opérateur de décalage à gauche au niveau du bit pour trouver toutes les puissances de 2 à partir de 1. Pour chaque puissance, vérifiez si elle est inférieure ou égale à n ou non. Vous trouverez ci-dessous la mise en œuvre de l'idée.
int highestPowerof2(unsigned int n){ // Invalid input if (n < 1) return 0; int res = 1; // Try all powers starting from 2^1 for (int i = 0; i < 8 * sizeof(unsigned int); i++) { int curr = 1 << i; // If current power is more than n, break if (curr > n) break; res = curr; } return res;}// Driver codeint main(){ int n = 10; printf("%d", highestPowerof2); return 0;}8
Complexité temporelle : O(32)
Espace auxiliaire : O(1)
Une solution utilisant Log
int highestPowerof2(int n){ int p = (int)log2; return (int)pow(2, p);}// Driver codeint main(){ int n = 10; cout << highestPowerof2; return 0;}8
Complexité temporelle : O(logn)
Espace auxiliaire : O(1)
Solution utilisant des masques de bits :
unsigned highestPowerof2(unsigned x){ // check for the set bits x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; // Then we remove all but the top bit by xor'ing the // string of 1's with that string of 1's shifted one to // the left, and we end up with just the one top bit // followed by 0's. return x ^ (x >> 1);}int main(){ int n = 10; cout << highestPowerof2 << "\n"; return 0;}Complexité temporelle : O(1)
Espace auxiliaire : O(1) puisque seul l'espace constant est utilisé pour les variables
Une solution utilisant MSB
Si le nombre donné est la puissance de deux, c'est le nombre requis, sinon définissez uniquement le bit le plus significatif qui nous donne le nombre requis.
long long highestPowerof2(long long N){ // if N is a power of two simply return it if (!(N & (N - 1))) return N; // else set only the most significant bit return 0x8000000000000000 >> (__builtin_clzll(N));}// Driver Codeint main(){ long long n = 5; cout << highestPowerof2; return 0;}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)
Problème d'application :
certaines personnes font la queue. Un processus de sélection suit une règle selon laquelle les personnes se tenant sur des positions paires sont sélectionnées. Parmi les personnes sélectionnées, une file d'attente est formée et à nouveau parmi celles-ci, seules les personnes en position paire sont sélectionnées. Cela continue jusqu'à ce qu'il nous reste une seule personne. Découvrez la position de cette personne dans la file d'attente d'origine.
Imprimez la position (file d'attente d'origine) de cette personne qui reste.
Exemples :
Entrée : n = 10 Sortie : 8 Explication : 1 2 3 4 5 6 7 8 9 10 ===>File d'attente donnée 2 4 6 8 10 4 8 8 Entrée : n = 17 Entrée : 16 Explication : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ===>File d'attente donnée 2 4 6 8 10 12 14 16 4 8 12 16 8 16 16