Algorithme permettant de trouver la plus petite puissance de deux qui est supérieure ou égale à une valeur donnée.

Question

Je dois trouver la plus petite puissance de deux qui est supérieure ou égale à une valeur donnée. Pour l'instant, j'ai ceci :

int value = 3221; // 3221 is just an example, could be any number
int result = 1;

while (result < value) result <<= 1;

Cela fonctionne bien, mais semble un peu naïf. Existe-t-il un meilleur algorithme pour ce problème ?

EDIT. Il y a eu quelques suggestions intéressantes concernant l'Assembleur, donc j'ajoute ces balises à la question.

Answer 1

Voici mon préféré. À part la vérification initiale pour savoir s'il n'est pas invalide (<0, que vous pouvez ignorer si vous savez que vous ne recevrez que des nombres >=0), il n'y a pas de boucles ou de conditionnels, et il est donc plus performant que la plupart des autres méthodes. Ceci est similaire à la réponse d'erickson, mais je pense que ma décrémentation de x au début et l'ajout de 1 à la fin est un peu moins maladroite que sa réponse (et évite également la conditionnelle à la fin).

/// Round up to next higher power of 2 (return x if it's already a power
/// of 2).
inline int
pow2roundup (int x)
{
    if (x < 0)
        return 0;
    --x;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x+1;
}

Answer 2

ceil(log2(value))

ilog2() peut être calculé en 3 instructions asm, par exemple, http://www.asterisk.org/doxygen/1.4/log2comp_8h-source.html

Answer 3

Sur le matériel Intel, l'instruction BSR est proche de ce que vous voulez - elle trouve le bit de poids fort. Si vous avez besoin d'être plus précis, vous pouvez alors vous demander si les bits restants sont précisément nuls ou non. J'ai tendance à supposer que les autres CPU ont quelque chose comme BSR - c'est une question à laquelle il faut répondre pour normaliser un nombre. Si votre nombre est supérieur à 32 bits, vous devriez effectuer un balayage à partir de votre DWORD le plus significatif pour trouver le premier DWORD avec N'IMPORTE QUEL ensemble de bits. Edsger Dijkstra remarquerait probablement que les "algorithmes" ci-dessus supposent que votre ordinateur utilise des chiffres binaires, alors que de son point de vue "algorithmique" hautain, vous devriez penser aux machines de Turing ou quelque chose du genre - je suis évidemment d'un style plus pragmatique.

Answer 4

Dans l'esprit du 0x5f3759df de Quake II et de la version IEEE de Bit Twiddling Hacks - cette solution atteint un double pour extraire l'exposant comme moyen de calculer floor(lg2(n)). Elle est un peu plus rapide que la solution acceptée et beaucoup plus rapide que la version IEEE de Bit Twiddling puisqu'elle évite les calculs en virgule flottante. Tel que codé, il suppose qu'un double est un réel*8 IEEE float sur une machine little endian.

int nextPow2(int n) 
{ 
    if ( n <= 1 ) return n;
    double d = n-1; 
    return 1 << ((((int*)&d)[1]>>20)-1022); 
}

Edit : Ajout d'une version optimisée en assembleur x86 avec l'aide d'un collègue de travail. Un gain de vitesse de 4% mais toujours environ 50% plus lent qu'une version bsr (6 sec vs 4 sur mon ordinateur portable pour n=1..2^31-2).

int nextPow2(int n) 
{ 
    if ( n <= 1 ) return n;
    double d;
    n--;
    __asm {
      fild    n 
      mov     eax,4
      fstp    d 
      mov     ecx, dword ptr d[eax]
      sar     ecx,14h 
      rol     eax,cl 
  }
}

Answer 5

Votre implémentation n'est pas naïve, elle est en fait logique, sauf qu'elle est fausse - elle renvoie un négatif pour les nombres supérieurs à la moitié de la taille maximale des entiers.

En supposant que vous puissiez restreindre les nombres à la plage de 0 à 2^30 (pour les ints 32 bits), cela fonctionnera très bien, et beaucoup plus rapidement que toutes les fonctions mathématiques impliquant des logarithmes.

Les ints non signés fonctionneraient mieux mais vous vous retrouveriez avec une boucle infinie (pour les nombres supérieurs à 2^31) puisque vous ne pouvez jamais atteindre 2^32 avec l'opérateur <<.