VITESSE ALGO, CONCOURS POUR TOUS

DWORD __fastcall Puiss2SupEgal_C(DWORD d)
{
  DWORD r, n;
  if(!d) return 0;
  if(d & 1) d++;
  r = 0x80000000;
  n = d;
  if(d & 0x80000000) goto verifInf;
  do {
    r >>= 1;
    d <<= 1;
  } while(!(d & 0x80000000));
verifInf:
  if(r < n) r <<= 1;
  if(!r) r = 0xFFFFFFFF;
  return r;
}

Cette fonction retourne la plus proche puissance de 2 >= au param.
Si param == 0 doit retourner 0.
Si param > (2 puiss 31) doit retourner 0xFFFFFFFF;

Voila, je suis ouvert à toute proposition plus rapide, prog de test est fait.
Pas de table précalculée ni série de 32 'if' ou chose de ce genre pour cause de taille de code.
J'ai deja fait version ASM (dispo sur demande), est 6 fois + rapide que celle ci mais je voudrais savoir si vous avez des idées d'amélioration en C.

Toutes les propositions seront mesurées.
A vos claviers et merci de votre participation.

ciao...
BruNews, MVP VC++

Bonsoir,

J'essaie :

unsigned Puiss2SupEgal_C(unsigned d)
{
  unsigned Depart = 0x80000000;
 
      // Difficile de faire mieux
  if(!d) return 0;

      // Ca tombe pile poil
  if((d & d-1) == 0)
    return d;

      // Trop grand
  if(d > Depart)
    return 0xFFFFFF;


  while((Depart & d) == 0)
    Depart >>= 1;
   
  Depart <<= 1;
  return Depart;
   
}

Matt...

Merci je teste, résultats sous peu.

ciao...
BruNews, MVP VC++

598283328 ticks la mienne
599283328 la tienne
on peut dire équivalent, je n'ai pas vérifié les résultats de la fonction.

ciao...
BruNews, MVP VC++

Bonsoir,

(Bien essayé Matt)
Ok, je vais voir si on peut faire mieux,

Matt...

Une petite modif dans la boucle while (je ne pense pas que ca change grand chose mais bon)

unsigned Puiss2SupEgal_C(unsigned d)
{
  unsigned Depart = 0x80000000;
 
      // Difficile de faire mieux
  if(!d) return 0;

      // Ca tombe pile poil
  if(!(d & d-1))
    return d;

      // Trop grand
  if(d > Depart)
    return 0xFFFFFF;

  while(((Depart >>= 1) & d) == 0);
  Depart <<= 1;

  return Depart;
}

Matt...

identique.

Le souk c'est qu'on a pas d'opérateur de scann bits en C, on est obligé de boucler.

ciao...
BruNews, MVP VC++

Je ne vois pas trop comment faire autrement.
Si quelqu'un trouve un autre algo !!!
Bonne soirée,
Matt...

une version avec une lookup table:

unsigned Puiss2SupEgal_C( unsigned u )
{
    static const unsigned mask [] =
    {
        0x00000000,
       
        0x00000001,
        0x00000002,
        0x00000004,
        0x00000008,
       
        0x00000010,
        0x00000020,
        0x00000040,
        0x00000080,
       
        0x00000100,
        0x00000200,
        0x00000400,
        0x00000800,
       
        0x00001000,
        0x00002000,
        0x00004000,
        0x00008000,
       
        0x00010000,
        0x00020000,
        0x00040000,
        0x00080000,
       
        0x00100000,
        0x00200000,
        0x00400000,
        0x00800000,
       
        0x01000000,
        0x02000000,
        0x04000000,
        0x08000000,
       
        0x10000000,
        0x20000000,
        0x40000000,
        0x80000000,
       
        0xffffffff
    };
   
    const int *p = mask;
 
    while( *p < u)
       p++;
    return *p;
}

salut,

1 doit renvoyer 2 ou 1  ? vaut deux fonctions ne sont pas d'accord.

bizarre sur les perfs, je trouve quasiment deux fois plus rapide pour la fonction de Matt ?
Je vais essayer avec cl pour voir.


Ma participation à la saturation du net:
http://hylvenir.free.fr