Discussion :

[diogene]

bigquick :

A force de faire des bit shift à droite, "a" va quand même finir par être égal à 0 non ?

Non , a est un int, pas un unsigned int et il va décaler avec extension du signe. Si a est négatif, c'est un 1 qui va rentrer

[Jean-Marc.Bourguet]

Si a est négatif, c'est un 1 qui va rentrer

Non, c'est du comportement spécifié par l'implémentation.

La règle numéro 1 quand on utilise les manipulations de bits, c'est de n'utiliser que des unsigned.

[diogene]

Non, c'est du comportement spécifié par l'implémentation.

Tout dans ce code est fonction de l'implémentation , c'est pourquoi j'ai précisé :

A noter que ce code suppose que le codage des int est en complément à 2.

[Jean-Marc.Bourguet]

Non, c'est du comportement spécifié par l'implémentation.

Tout dans ce code est fonction de l'implémentation , c'est pourquoi j'ai précisé :

A noter que ce code suppose que le codage des int est en complément à 2.

Ce code me semble avoir un comportement défini pour autant que a soit positif et qu'il n'y ait pas de dépassement de capacité (pour les 3 représentations admises par C99, j'ai pas envie de replonger dans les détails de C90 pour voir si c'est différent).

Il a un comportement dépendant de l'implémentation si a est négatif et qu'il n'y a pas de dépassement de capacité.

Il a un comportement indéfini s'il y a un dépassement de capacité.

Le comportement dépendant de l'implémentation sur les décalages à droite des valeurs négatives est formellement indépendant de la représentation des entiers et ça ne m'étonnerait pas que les 6 possibilités ait pu être le comportement "naturel" d'architectures ayant existé si on avait pris la peine de faire un compilateur C pour elles; en ce qui concerne le complément à 2, il me semble me souvenir que le Cray 1 n'a pas de décalage à droite avec conservation de signe.

[diogene]

Il a un comportement dépendant de l'implémentation si a est négatif

Comme a est déclaré comme int ....le code est dépendant de l'implementation
J'ai déjà souligné ce point ( probablement mineur dans le contexte de la question posée),
Je ne pense pas que le code soit correct dans aucune des 3 représentions admises par C99 pour des int

Le comportement dépendant de l'implémentation sur les décalages à droite des valeurs négatives est formellement indépendant de la représentation des entiers et ça ne m'étonnerait pas que les 6 possibilités ait pu être le comportement "naturel" d'architectures ayant existé si on avait pris la peine de faire un compilateur C pour elles;

il me semble me souvenir que le Cray 1 n'a pas de décalage à droite avec conservation de signe.

Je ne sais pas, je n'ai pas de Cray dans mon salon pour vérifier. verifie sur le tien

Pour revenir au sujet, à ton avis, le code est bon ou il est incorrect ?

[Jean-Marc.Bourguet]

il me semble me souvenir que le Cray 1 n'a pas de décalage à droite avec conservation de signe.

Je ne sais pas, je n'ai pas de Cray dans mon salon pour vérifier. verifie sur le tien

Je n'ai pas de Cray dans mon salon (il est trop petit) mais si tu veux réellement une vérification dans ma bibliothèque j'ai Computer Architecture, Concept and Evolution de Blaaw et Brooks et le tableau a la page 297 confirme :-)

Pour revenir au sujet, à ton avis, le code est bon ou il est incorrect?

Ce n'est certainement pas du bon code. La règle numéro 1 des manipulations de bits, c'est d'utiliser des unsigned; la règle numéro 2, c'est de ne pas faire de manipulations de bits quand on veut faire des opérations arithmétiques et je ne crois pas que la règle 0 (toute règle a des exceptions) s'applique ici.

J'aurais voulu implémenter l'algo, je n'aurais pas fait ça mais plutôt quelque chose comme:

Code :

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

1
2
3
4
5
6
7
8
9
int mult(int a, int b) {
   int result = 0;
   while (a != 0) {
      result += (a%2) * b;
      a /= 2;
      b += b;
   }
   return result;
}

qui a un comportement défini tant qu'on n'a pas de dépassement de capacité, ce qui n'arrive que si le résultat n'est pas représentable (en C99, C90 laisse à l'implémentation le soin de définir le comportement de a /= 2 pour a négatif). Si on veut absolument éviter les multiplications, alors

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
int mult(int a, int b) {
   int result = 0;
   if (a < 0) {
      if (b == 1) {
         return a;
      }
      a = -a;
      b = -b;
   }
   while (a != 0) {
      if (a % 2 != 0) {
         result += b;
      }
      a /= 2;
      b += b;
   }
   return result;
}

Si par correct, tu veux dire "strictement conforme", non.

Si par correct tu veux dire "conforme", oui puisqu'il y a au moins une implémentation conforme sur lequel il a le comportement qu'on devine voulu.

Si par correct, tu veux dire "a le comportement demandé par les specs", j'aimerais bien avoir ces dernières pour avant de répondre. Je ne peux que répéter ce que j'ai déjà écrit:

Il y a un comportement non défini s'il y a un dépassement de capacité. J'ai rarement vu des programmes se blindant contre ça.

Si a est positif, dans les trois représentations autorisée des entiers, a & 1 a le même effet que a %2 != 0 et a >>= 1 est bien une division tronquante par deux, donc on a bien une multiplication.

Si a est négatif, on a deux sources de comportements définis par l'implémentation: le décalage à droite qui peut ou non conserver le signe et a & 1 qui va avoir une interprétation arithmétique différente en complément à 1 que dans les deux autres représentations.

[babar56]

Je n'ai pas vraiment compris tout ce qui vient d'être dit, mais à priori en mettant unsigned int a en paramètres de la fonction le problème de a négatif est réglé (après quelques tests effectués). La fonction n'est toujours pas correcte comme ça ? Je ne connais pas ce unsigned donc je sais pas trop quoi d'autre en dire.

De toutes façons, même sans unsigned on aurait pu s'en sortir avec un if sur le signe de a et b dès le début de la fonction. Si a négatif et b positif on inverse les deux valeurs, si a et b négatifs on fait le calcul avec |a| et |b|, et sinon ben c'est bon.

[PRomu@ld]

unsigned te permet tout simplement d'interdire les valeurs négatives d'un type entier. Ce mot clé ne fonctionne pas avec les types réels.

Généralement ça se traduit par une plage de valeur décalée (les valeurs indiquées ne sont qu'un exemple) :

char -> -128 ; 127
unsigned char -> 0 ; 255

[diogene]

De toutes façons, même sans unsigned on aurait pu s'en sortir avec un if sur le signe de a et b dès le début de la fonction. Si a négatif et b positif on inverse les deux valeurs, si a et b négatifs on fait le calcul avec |a| et |b|, et sinon ben c'est bon.

Oui, on aurait pu aussi faire précédé le code par qq chose du genre

Code :

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

1
2
3
4
5
if(a<0)
{
   a = -a;
   b = -b;
}

Ce qui fait que a >0 et le produit a*b est inchangé;
Même ainsi, il reste 1 cas embêtant , celui de la plus petite valeur (négative) des int qui en complément à 2 est son propre opposé ( autrement dit , dans cet unique cas, |a| est "incorrect") et reste "négative". Si on veut traiter aussi cet unique cas, cette solution est insuffisante.

[babar56]

il reste 1 cas embêtant , celui de la plus petite valeur (négative) des int qui en complément à 2 est son propre opposé ( autrement dit , dans cet unique cas, |a| est "incorrect") et reste "négative".

Je ne suis pas certain d'avoir bien saisi, peux-tu me donner cette valeur en binaire pour voir concrètement à quoi ça ressemble une valeur qui est égale à son propre opposé ?

Autre question : on a déclaré int a. Mais le fait d'utiliser l'opérateur & de cette façon : a&1, signifie qu'on utilise la représentation binaire de a et de 1. Que renvoie exactement a&5 par exemple ? Un entier ou un booléen ?

[Trap D]

a & 5 renvoie un entier qu1 peut être 0, 1, 4 ou 5 :
5 en binaire s'écrit 101, donc a&5 renvoie un nombre dont tous les bits sont à zéros sauf les bits 1 et 3 (à partir de la droite) qui sont les bits correspondants de a.

[Médinoc]

il reste 1 cas embêtant , celui de la plus petite valeur (négative) des int qui en complément à 2 est son propre opposé ( autrement dit , dans cet unique cas, |a| est "incorrect") et reste "négative".

Je ne suis pas certain d'avoir bien saisi, peux-tu me donner cette valeur en binaire pour voir concrètement à quoi ça ressemble une valeur qui est égale à son propre opposé ?

Sur un signed char: -128 = 0x80 = 0b10000000
Son opposé, 128 = 0x80 = 0b10000000 (ne tient pas sur un signed char, il faut au mons un unsigned char pour le coder).

[diogene]

Comme l'explique Medinoc sur un exemple, la plus petite valeur représentable en complément à 2 est 1 suivi de zéros. Elle est son propre opposé parce que l'arithmétique utilisée est une arithmétique binaire modulo 2^N. : seuls les N bits de poids faibles sont conservés, les autres bits de poids forts sont abandonnés. La plus forte valeur est 0 suivi de 1. -1 est codé comme tous les bits à 1, etc...
Tout ceci montre combien les cas "marginaux" sont embêtants et comme ils peuvent compliquer une solution à priori simple si on veut les prendre en compte.
Il y aurait sans doute encore à réfléchir si on voulait que le code se comporte exactement comme a*b dans tous les cas. Mais je suppose que ça dépasse le cadre de cet exercice