fonction sur les puissances

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.

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 :aie:

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

sinon un algo tout simple :

Code:

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

Ceci marcherait peut être aussi
Code:

1 2 3 int i = 0; while (gain != pow(2,i)) i++;
Edit: mince ca ressemble à ce que tu as écris souviron :aie: Sauf que ma version est buggé :yaisse2:

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

Exemple :
Code:

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 ??:mrgreen:

Bonjour,

Citation:

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)

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

en C :

Code:

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:

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

Citation:

Envoyé par 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.

Ebauche de code :
Code:

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...

Citation:

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:

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;
}

Citation:

Envoyé par 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.

j avais pas fait gaffe au superieur :aie:

Citation:
Envoyé par souviron34
sauf qu'un log est plus long à calculer qu'une multiplication ... ;)

en C :
Code:

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 :)

Citation:

Envoyé par hegros

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 :

Citation:

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) ....
:P