Pour ma culture, quand tu parles de coût en temps c'est chiffrable directement en temps? Il y a des ratios constants? Du genre multiplier 2 et 3 prend 2 fois plus de temps qu'additionner 2 et 3.

Merci pour ta réponse.

Petite précision générale: pour le 4.2, l'entrée est N et pas 2^N

@racine: il n'y a pas vraiment de ratio théorique constant, ça dépend beaucoup de l'architecture du processeur, et beaucoup ont développé des moyens astucieux pour faire des multiplications plus rapidement (avec parfois quelques erreurs, par exemple: http://fr.wikipedia.org/wiki/Bug_de_la_ … du_Pentium ou comment une méthode pour faire des divisions plus rapidement fout en l'air toute une gamme de processeur)

@dhrm77: tes réponses ne sont pas fausses, loin de là; à ceci près que les mécanismes de type "boucle" ne sont pas dans le jeu d'instructions que j'ai défini dans l'énoncé (du coup, il faut faire tenir chaque réponse en une seule instruction "haut niveau")

Il m'arrive effectivement de coder, mais j'avoue ne jamais avoir poussé l'optimisation d'un code à ce point. J'y penserai sans doute la prochaine fois. Cependant, je ne connaissais pas certaines fonctions comme les décalages...

1.1) 2*p=p+p. On remplace donc la multiplication par une addition.
1.2) p*2^n. Ca revient à décaler tous les bits de p de n crans vers la gauche.

2.1) p/2=p*2^(-1). On décale tous les bits de p de 1 cran vers la droite. Si la variable à laquelle on assigne le résultat est déclarée comme un entier, le résultat est E(p/2).
2.2) p/2^n=p*2^(-n). On décale tous les bits de p de n crans vers la droite. Même remarque qu'en 2.1).

3) p==q <=> p-q==0. On fait donc la soustraction et on regarde si tous les bits du résultat sont nuls (ca revient à faire une boucle sur tous les bits de var=p-q). Enfin, je pense qu'il existe toujours dans les langages de programmation des indicateurs de test "==", je suppose qu'ils en tiennent déjà compte, non?

4.1) p mod(2)=1 si p est impair <=> si le premier bit de p est 1 (en partant de la droite)
p mod(2)=0 si p est pair <=> si le premier bit de p est 0.
Le résultat est donc la valeur du premier bit de p (en partant de la droite).
4.2) p mod(2^n). On remplace tous les bits qui ont un poids >=2^n par 0.

5) p==2^n <=> Un seul bit de p vaut 1. Ca revient encore à faire une boucle sur tous les bits de p...

6) p+q==2^n-1 <=> tous les bits de p+q valent 1. idem...

Bon, j'ai souvent fait intervenir des boucles, mais tu n'en parles pas, il me manque sûrement quelque chose...
Intéressant, merci.

Merci de faire découvrir cela aux non informaticiens. C'est une très bonne idée. On pourrait sans doute aller un peu plus loin dans une suite...

Tu as oublié à mon avis quelques opérateurs très importants: NOT qui inverse tous les bits d'un nombre, INC qui augmente de 1 (plus rapide qu'une addition générale) et DEC qui diminue de 1.

1.1: Décalage à gauche de 1 bit (A << 1)
1.2: Décalage à gauche de n bits (A << n)

2.1: Décalage à droite de 1 bit
2.2: Décalage à droite de n bits

3: A-B et on teste le bit permettant de savoir si le résultat est 0
On peut aussi faire NOT (A XOR (NOT B)) et vérifier si le résultat est 0

4.1: A ET 1: on isole le bit de poids faible)
4.2: A ET ((1 << n)-1): on isole les n bits de poids faible.

5: A ET (A-1) et on teste le bit de résultat nul. Si A est une puissance de 2, 2^n, A s'écrit avec un 1 suivi de n zéros, A-1 s'écrit avec n chiffres 1. Le ET donne donc 0. Si A n'est pas une puissance de 2, A-1 et A ont le même bit de poids fort et donc le ET ne donne pas 0

6: Si A+B donne une puissance de 2 moins -1, c'est qu'il ne s'écrit qu'avec des 1. Regardons le bit de poids faible. Pour valoir 1, il faut qu'il soit à 1 dans un des nombres et à 0 dans l'autre et ne génère pas de retenue. La situation du bit 1 est la même et ainsi de suite. Donc bit à bit, il y a à chaque fois 1 1 et 1 0. Donc XOR entre A et B donnera que des 1 et donc (A XOR B) ET ((A XOR B)+1) sera nul. (on ne calcule A XOR B qu'une fois). I doit y avoir mieux, je vais creuser...

Pour ceux qui aiment ça:
http://graphics.stanford.edu/~seander/b … With64Bits

1-1) En base n, si on multiplie un nombre par n on "rajoute un 0 à droite" donc ici on fait l'opération "Décaler à gauche d'un cran"
1-2)soit N = [latex] a_m 2^m+a_{m-1} 2^{m-1} +...+a_0 2^0[/latex]
[latex]N* 2^n=a_m 2^{m+n}+a_{m-1}2^{m-1+n}+...+a_02^n[/latex]et ensuite tous les coefficients des puissances de 2 inférieurs à n sont nuls : on "rajoute" donc n zéros.
On fait donc l'opération "Décaler à gauche de n crans"

2) En informatique la division prend 2 entiers et renvoie un entier : par exemple 9/2=4. 
2-1)De la même manière qu'au 1-1) on fait "Décaler à droite d'un cran"
2-1)"Décaler à droite de n crans "

Je continuerai plus tard si j'ai le temps.
Plutôt amusant sinon .
---------------
Bon ben j'ai plus de trop de temps là donc j'essaye le 3) rapidement :
on fait un XOR sur le premier bit de chaque nombre,c'est à dire le plus à droite,  (ça doit être permis sinon je vois pas comment faire), puis on test si le dernier résultat est 0 : Si oui alors on décale à droite et on continue sinon on arrête et on renvoie faux.

Des bonnes réponses un peu partout mais aucun "carton plein".
Notations : & signifie ET, ^ signifie XOR, | signifie OU, <<n signifie "Décalage gauche de n crans", >>n signifie "Décalage droite de n crans"

Voici donc les réponses:
1.1) Multiplier par 2 en base 2, c'est comme multiplier par 10 en base 10: on ajoute un 0. Autrement dit, on fait x <<1
1.2) Pareil, on ajoute n zéros: x <<n

2.1) Dans la même logique, on divise par 2 en binaire en ôtant le dernier chiffre (il s'agit de division euclidienne, sans reste). Autrement dit, on fait x >>1
2.2) Pareil, on ôte n chiffres: x >>n

3) 0^0 = 0, 1^1 = 0, et 0^1 = 1. Autrement dit, si x=y, alors x^y=0. Donc on fait x^y et on regarde l'indicateur de résultat nul

4.1) Le modulo 2 d'un nombre en binaire, c'est comme le modulo 10 d'un nombre en base 10: le dernier chiffre. De plus, x&0 = 0 et x&1 = x.
Autrement dit, x&1 nous donne le modulo 2 de x

4.2) Celle-ci n'était pas évidente:
* la réponse la plus communément admise est de faire x & ((1<<n)-1). En effet, 1<<n, c'est 1 avec n zéros derrière, donc (1<<n)-1, c'est n fois le chiffres 1 et x&((1<<n)-1), c'est donc les n derniers chiffres de x (qui, comme en base 10 pour 10^n, correspondent au modulo en base 2 de 2^n)
* cependant, pour faire des opérations moins coûteuses, on peut procéder autrement: en effet, x^0 = x et x^x = 0; et de plus (x>>n)<<n correspond à x auquel on remplace les n derniers nombres par des zéros (pour s'en convaincre, en base 10, si je prends le quotient de x divisé par 10^n, puis que je rajoute n zéros, j'obtient un nombre similaire à x sauf que ses n derniers chiffres sont nuls). Du coup, x^((x>>n)<<n) vaut
- le i-ème bit de x pour les n derniers bits
- 0 pour ceux qui sont devant

5) Sans faire de boucle, le plus simple est de faire x & (x-1) et de regarder l'indicateur de résultat nul. En effet, si x est une puissance de 2, c'est un 1 avec n zéros derrière, et x-1 c'est n fois le chiffre 1. L'un ET l'autre, ça donne donc zéro.
2 remarques pour celle-ci:
- Elle indique que 0 est une puissance 2 (mais comme je ne parle pas des nombres négatifs dans l'énoncé, on peut oublier cette limitation)
- Elle fait une opération "-". Faire une boucle pour vérifier qu'on n'a que des zéros, suivi d'un 1 et plus rien ensuite ne fait pas de -, mais d'un autre côté la boucle peut être plus longue (car pour 2^n, on bouclera n+1 fois). De toutes les façons, les boucles ne font pas partie des opérations prévues par l'énoncé.

6) Je pense que le plus simple est de faire (a^b)&(a^b +1) et de regarder l'indicateur de résultat nul
J'ai beaucoup réfléchi au "(N ou M) xor (N xor M)=0" de Yanneck, je comprenais pas pourquoi ça marchait et en fait ça marche pas si deux bits valent 0, la condition reste vraie alors qu'elle devrait être fausse

Edit: Pour ce point 6, il y a en fait plus simple en utilisant une fonction binaire que je n'ai pas présenté dans l'énoncé: le NOR (qui vaut 1 si et seulement si les deux opérandes sont nulles)
Du coup, le test de résultat nul après (a NOR b) XOR (a AND b) devrait faire l'affaire:

A  B  A NOR B  A AND B  (a NOR b) XOR (a AND b)
0  0     1        0                1
0  1     0        0                0
1  0     0        0                0
1  1     0        1                1

Déjà posé
Spoiler : [Afficher le message]
R1=R1+R2
R2=R2-R1
R1=R1-R2

On peut faire pareil avec XOR. Est-ce à ça que tu penses? Il y a le même nombre d'instructions et sur les processeurs récents ça doit être équivalent.
Spoiler : [Afficher le message]
R1=R1 XOR R2
R2=R2 XOR R1
R1=R1 XOR R2


Sur les processeurs ARM on doit pouvoir faire mieux en utilisant les instructions spéciales du "barrel shifter" mais c'est un peu spécifique. Sur les processeurs graphiques aussi. Sur les Intel on doit pouvoir charger 2 32bits dans un 64 et faire un swap mais la aussi ce n'est pas générique...

scarta a écrit:

6) Comment savoir si la somme de deux nombres vaut 1 de moins qu'une puissance de 2?

Pourquoi ne pas faire comme dans 5), mais inversé:
soit les 2 nombres a et b:
faire x=a+b
faire ensuite (x & (x+1))==0