Trouver les puissances de deux

Date de publication : 1-03-10

Ce module comporte deux fonctions permettant d'obtenir
- la plus grande puissance de deux inférieure ou égale à un nombre donné.
- la plus petite puissance de deux supérieure ou égale à un nombre donné.

Version PDF (Miroir) Version hors-ligne (Miroir)

I. Présentation
II. Codes source

I. Présentation

Ce qui suit ne concerne que les nombres non signés (unsigned ...) pour lesquels la norme définit la représentation binaire sans équivoque comme étant le code binaire pur.

- La méthode classique pour déterminer la puissance de deux immédiatement inférieure à un nombre non signé (non nul) est de procéder par décalages vers la droite jusqu'à ce que le nombre obtenu soit nul, tout en comptant le nombre N de décalages effectués. Le bit de poids fort à 1 du nombre était donc à l'origine, en position N-1. On décale ensuite la valeur 1 (unsigned) vers la gauche de N-1 positions.
Ceci implique de faire N décalages de une position, N tests et un décalage de N-1 positions.

La méthode présentée ci-dessous devrait être plus rapide, puisqu'elle ne prend en compte que les bits à 1 dans la représentation binaire du nombre.
Elle est basée sur le fait que la représentation binaire du nombre

n & (n-1)

est la même que celle de n, à la seule différence que le bit à 1 de poids le plus faible dans la représentation de n est mis à 0.

Par exemple :

nombre	décimal	binaire
n	52	110100
n-1	51	110011
n & (n-1)		110000

On va donc répéter ce processus jusqu'à obtenir un nombre nul.
On construit donc la suite :

- S(0) = n
- S(i) = S(i-1) & (S(i-1)-1) pour i = 1..P, P tel que S(P) == 0
- La plus grande puissance de deux inférieure ou égale à n est S(P-1)

- Pour obtenir, la plus petite puissance de deux supérieure ou égale à un nombre, il suffit d'obtenir la plus grande puissance de deux inférieure ou égale à ce nombre de la façon précédente et, si le nombre n'est pas une puissance de deux, d'opérer un décalage vers la gauche.
Il est facile de savoir si le nombre était une puissance de deux, car, dans ce cas, on a P==1

II. Codes source

- Trouver la plus grande puissance de deux inférieure ou égale à un nombre n.

//-----------------------------------------------------
// la fonction renvoie 
// - 0 si n == 0
// - sinon, la plus grande puissance de deux inférieure ou égale à n
//-----------------------------------------------------
unsigned int puiss2InfEgal(unsigned int n)
{
  unsigned int m = n;
  while(m != 0)
  {
    n = m ;
    m &= (m-1);
  }
  return n;
}

- Trouver la plus petite puissance de deux supérieure ou égale à un nombre n.

//-----------------------------------------------------
// la fonction renvoie 
// - la plus petite puissance de deux supérieure ou égale à n
//-----------------------------------------------------
unsigned int puiss2SupEgal(unsigned int n)
{
  unsigned int m;
  if((m = n & (n-1)) == 0) return n == 0 ? 1 : n;
  do
  {
    n = m ;
    m &= (m-1);
  } while (m != 0);
  return n << 1;
}

Version PDF (Miroir) Version hors-ligne (Miroir)

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2010 Developpez. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts. Droits de diffusion permanents accordés à Developpez LLC.