Calcul rapide de puissance de 2

Portrait de trax

Ce qu'il ne faut pas faire

Encore une fois, il y a la méthode > (private joke inside) qui consiste à faire une boucle du genre :

int puissance2(int puissance){
	unsigned int resultat = 1;
	for (int i = 0 ; i<puissance ; i++){
		resultat *= 2;
	}
	return resultat;
}

Temps d'execution: o(puissance)

C'est moche... Pourquoi c'est moche ? Parce que le programme effectue pour calculer 2^n, n multiplication. Temps moyen par multiplication : 5 à 6 cycles d'horloges, soit n*6 ça peut faire beaucoup).

Ce qu'il faudrait faire

Petit rappel sur la numération binaire :
binaire => décimal
0 =>0
1 =>1
10 => 2
11 => 3
100 => 4
1000 => 8
10000 => 16

Il suffit donc pour calculer une puissance de 2 de faire des décalage a gauche comme suit :

unsigned int puissance2(int puissance){
	return 1 << puissance;
}

Temps d'exécution : o(1)

Domaine: 
Catégories: