Discussion :

[sandball22]

bonjour,
je calcul un gain. Ensuite je voudrais trouver la puissance de 2 correspondant à ce gain ou la puissance de 2 la plus proche supérieure.

Exempl: si gain =4096 trouver la puissnace de de 2: 16 car 2^12=4096

si gain= 10000 , puissance de 2 : 14 car 2^14=16384.

merci.

[hegros]

Tu écris ton équation puis tu en déduis la formule à appliquer. Ici tu vas avoir besoin peut être d'utiliser les logarithmes car je crois 2^n = 4096 -> n= ln de quelque chose

[sandball22]

donc c n= log4096. Comment fait-on log en c? il me faut un log en base 2.

[souviron34]

sinon un algo tout simple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
puissance = 0
dep = 2
 
tant que puissance(2,puissance) < gain
   puissance = puissance + 1

[hegros]

Ceci marcherait peut être aussi

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
int i = 0;
while (gain != pow(2,i)) i++;

Edit: mince ca ressemble à ce que tu as écris souviron Sauf que ma version est buggé

[berg]

Joue avec les les oprations binaires (&, |, >>, <<)

Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
Soit N = 8 = 2^3
alors (N & (1 << 3)) = 1

Une fois que tu as compris ca c est tout simple.

Soit N un nombre au hasard, tu trouve le bit le plus fort egale a 1 dans N. Imaginons que ce bit se trouve a l indice 4.
cela veut dire que N >= 2^4 et que N < 2^5.
Il te reste a faire le minimum entre N - 2^4 et 2^5 - N pour trouver la puissance de 2 la plus proche de N.

Edit : WAOUAAAA j ai mis autant de temps a ecrire ??

[Neitsa]

Bonjour,

je voudrais trouver la puissance de 2 correspondant à ce gain ou la puissance de 2 la plus proche supérieure.

avec x le nombre dont on doit trouver la puissance de 2 la plus proche :

(x > 0)

2^(round(log2(x)))

avec log2 :

log2(n) = ln(n) / ln(2)

[souviron34]

sauf qu'un log est plus long à calculer qu'une multiplication ...

en C :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
double d=2.0 ;
int puissance=1 ;
 
while ( d < gain )
   {
      puissance  = puissance + 1 ;
      d = 2.0 * d ;
   }

ou

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
include <math.h>
 
double puissance=1.0 ;
 
while ( pow(2.0,puissance) < gain )
   puissance = puissance + 1.0 ;

[Emmanuel Delahaye]

bonjour,
je calcul un gain. Ensuite je voudrais trouver la puissance de 2 correspondant à ce gain ou la puissance de 2 la plus proche supérieure.

Exempl: si gain =4096 trouver la puissnace de de 2: 16 car 2^12=4096

si gain= 10000 , puissance de 2 : 14 car 2^14=16384.

merci.

Ebauche de code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
#include <stdio.h>
#include <limits.h>
 
unsigned nearest_power_of_2 (unsigned x)
{
   int bit = ((UINT_MAX / CHAR_BIT) - 1);
   unsigned m = x << bit;
 
   while (m >> 1 >= x)
   {
      m >>= 1;
   }
 
   return m;
}
 
int main (void)
{
   unsigned i;
   for (i = 1; i < UINT_MAX / 2; i *= 77)
   {
      unsigned np2 = nearest_power_of_2 (i);
 
      printf ("%08X -> %08X\n", i, np2);
   }
   return 0;
}

ATTENTION Je ne suis pas sûr que les cas limites soient couverts...

[Neitsa]

sauf qu'un log est plus long à calculer qu'une multiplication ..

Rha oui tu as tout à fait raison !

Finalement, je suis arrivé à une implémentation proche de celle d'Emmanuel avec des décalages :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#include <stdio.h>
#include <math.h>
 
// nombre de bits pour un entier non signé
#define NBFUI 32
 
unsigned int NearestHighestPowerOf2(unsigned int n);
 
int main(void)
{
 
	printf("%u", NearestHighestPowerOf2(1895));
 
	return 0;
}
unsigned int NearestHighestPowerOf2(unsigned int n)
{
	unsigned int decalage = 1, i;
 
	n -= 1;
 
	for (i = 0; i < NBFUI; i++)
	{
		n = n | (n >> decalage);
		decalage <<= 1;
	}
 
	n += 1;
 
	return n;
}

[berg]

bonjour,
je calcul un gain. Ensuite je voudrais trouver la puissance de 2 correspondant à ce gain ou la puissance de 2 la plus proche supérieure.

Exempl: si gain =4096 trouver la puissnace de de 2: 16 car 2^12=4096

si gain= 10000 , puissance de 2 : 14 car 2^14=16384.

merci.

j avais pas fait gaffe au superieur

[hegros]

sauf qu'un log est plus long à calculer qu'une multiplication ...

en C :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
double d=2.0 ;
int puissance=1 ;
 
while ( d < gain )
   {
      puissance  = puissance + 1 ;
      d = 2.0 * d ;
   }

Est-ce que tu pourrais donner la complexite de ton algorithme et celle utilisant log2 pour qu'on puisse vraiment comparer

[souviron34]

Est-ce que tu pourrais donner la complexite de ton algorithme et celle utilisant log2 pour qu'on puisse vraiment comparer

ben un log est calculé comme une suite d'après la formule de ... je sais plus qui (Mercator ??), mais qui est en gros :

ln (1+x) = x - x^2/2 + x^3/3 ....

(voir http://fr.wikipedia.org/wiki/Logarithme_naturel)

En tous cas par exemple une discusssion des implémentations peut se trouver ici (http://www.jacques-laporte.org/Logarithm_1.htm) ou ici (http://www2.toki.or.id/book/AlgDesig...OOK/NODE16.HTM).

Donc les algos varient, mais nécessitent de toutes façons nettement plus d'opérations qu'une (multiplication + addition) ....