Que fait ce programme ?

**babar56** · 12/01/2006, 17h25

Bonjour,

J'aimerais savoir ce que fais le programme suivant. Je l'ai eu en contrôle, et j'ai bloqué sur les syntaxes du genre if(a&1) ou a>>=1 que j'ai jamais utilisé dans des programmes qui servent à quelque chose ... Voila merci.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
int xxx (int a, int b)
{
int y=0;
 
while(a)
{
if (a&1)
y+=b;
b+=b;
a>>=1;
}
return y;
}

Edité par Anomaly : Merci de mettre des titres clairs afin que les membres aient envie de lire ton message

**DaZumba** · 12/01/2006, 17h32

Les operateurs bit-a-bit (bitwise operators) & | ~ << >> sont documentes dans ton livre de C et dans la plupart des tutoriels disponibles sur l'Internet.

**Emmanuel Delahaye** · 12/01/2006, 18h29

Envoyé par babar56

a&1 désolé mais là comme ça j'ai pas la moindre idée de ce que ça représente.

& est un des bitwise operators. Le détail se trouve dans ton livre de C. Si tu n'as pas de livre, je te conseille ces liens :

http://publications.gbdirect.co.uk/c_book/
ou
http://www-clips.imag.fr/commun/bernard.cassagne/Introduction_ANSI_C.html

Et un bit non plus.

Binary digIT : Chiffre binaire : Unité élémentaire d'information valant 0 ou 1.

Mais je m'en vais de ce pas lire ton lien. Et je te ferais enfin remarquer qu'on a bien du mal à faire une recherche quand on se sait pas ce qu'il faut chercher (va tapper a&1 sur google tu m'en diras des nouvelles!).

C'est pour ça qu'on t'a indiqué le mot magique bitwise operator.

Alors un peu d'indulgence et merci de pas forcément prendre les gens de hauts, évident pour toi ne signifie pas évident de façon universelle.

Merci de ne pas aussi nous prendre pour des automates (bénévoles, je le rappèle).

Nota. Il y a un prérequis pour comprendre les bitwise operators, c'est la connaissance de l'Algèbre de Boole.

http://fr.wikipedia.org/wiki/Alg%C3%A8bre_de_Boole_%28logique%29

**babar56** · 12/01/2006, 19h27

Apparemment, on a l'impression que a&1 vaut a (0 si a est nul et 1 sinon). Le if(a&1) n'aurait donc pas de sens utile puisqu'on se trouve déjà dans une boucle while(a). Je suis persuadé que je me trompe. Ensuite, je ne trouve pas la signification de a>>=1. >> représente un décalage à droite (des valeurs binaires de a ?) et comment interpréter le 1 ?

:

**bigquick** · 12/01/2006, 19h36

pour répondre à ta question, en regardant rapidement, je ne vois pas ce qu'il fait de particulier. Mais "en gros", il regarde le nombre de bits à 1 dans le nombre "a". Ensuite, il retourne b + 2*b + 4*b + .... (selon le nombre de bits à 1). Enfin corrigez moi le cas échéant, j'ai regardé ça rapidement.

* a&1 retourne 1 si a est impair, puisque tu compares par exemple 0x00101101 avec 0x00000001 (mais avec 32 bits

)
* a = a >> 1 décale tous les bits de a d'un cran vers la droite (et remplit avec un 0 tout à gauche)

Donc while(a) s'arrêtera quand tu auras tout décalé, puisque "a" ne contiendra plus que des 0, et vaudra donc 0.

**babar56** · 12/01/2006, 19h54

Par rapport à ta question je me permets de corriger, à ta demande : il semblerait (après compilation et quelques tests) que le programme renvoie a*b ! Etonnant non ?

**bigquick** · 12/01/2006, 20h33

pour le coup de a*b, ça m'étonne puisque le code ne fait intervenir "a" que pour:
- arrêter la boucle quand il vaut 0
- augmenter la valeur de y et b quand son bit le plus à droite est à 1
- décaler ses bits

Donc, à priori (ou alors je suis fatigué...), la position des bits à 1 n'influe pas sur le programme. Donc il aura le même comportement pour a = 0x0000001 (1) et 0x00000010 (2) par exemple.

Qu'en penses-tu ?
(je n'ai pas de compilateur avec moi pour vérifier)

**Médinoc** · 12/01/2006, 20h35

bigquick: Tu fais une erreur, due à l'absence d'indentation du code:
L'opération sur y est conditionnelle, mais le doublement de b est inconditionnel: b est doublé, que le bit testé de a soit à 1 ou non.

**Médinoc** · 13/01/2006, 09h19

Ben c'est simple, il renvoit A*B, car pour chaque puissance N de 2 contenue dans A, il additionne B*2^N.
En fait, il calcule A*B bit de A par bit de A.

**Emmanuel Delahaye** · 13/01/2006, 09h33

Ce que tu demande est du reverse engineering. En dehors du fait que c'est une activité qui pourrait très bien être illégale, c'est une tout autre spécialité qui demande d'autres connaissances et une autre expérience.

On peut en effet facilement expliquer/commenter les instructions une par une,

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
29
 
#include <stdio.h>
 
int xxx (int a, int b)
{
  /* le resultat (valeur retournee) est a 0 par defaut 
      (semble logique, car c'est un accumulateur) */
   int y = 0;
 
   /* tant que a ne vaut pas 0 */
   while (a)
   {
      /* si le bit 0 de a est a 1 (a est impair ? ou 'une fois sur 2...' ) */
      if (a&1)
         /* on accumule b dans y */
         y += b;
 
      /* a chaque tout : b est double'  
          b = b + b  
          ou 
          b = b x 2 
       */
      b += b;
 
     /* a chaque tour : decalage de a vers la droite de 1 bit */
      a >>= 1;
   }
   return y;
}

mais celà ne nous donnera pas comme par magie le fonctionnement global de la fonction ni les intentions du programmeur[1], ce qui fait souvent dire qu'un code non documenté est un code inutile. En effet, le premier devoir du programmeur est d'autodocumenter son code, c'est à dire de donner à la fonction un nom moins abscons que 'xxx()'.

Ceci dit, il est possible de soumettre la fonction à une série de stimulis et d'en observer les réactions. Ca peut donner une indication.

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
29
30
31
32
33
34
35
 
#include <stdio.h>
 
int xxx (int a, int b)
{
   int y = 0;
 
   while (a)
   {
      if (a&1)
         y += b;
      b += b;
      a >>= 1;
   }
   return y;
}
 
int main (void)
{
   int x;
 
   for (x = 0; x < 4; x++)
   {
      int y;
 
      for (y = 0; y < 4; y++)
      {
         int z = xxx(x, y);
 
         printf ("f(%d, %d) = %d\n", x, y, z);
      }
   }
 
   return 0;
}

ce qui donne:

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
 
f(0, 0) = 0
f(0, 1) = 0
f(0, 2) = 0
f(0, 3) = 0
f(1, 0) = 0
f(1, 1) = 1
f(1, 2) = 2
f(1, 3) = 3
f(2, 0) = 0
f(2, 1) = 2
f(2, 2) = 4
f(2, 3) = 6
f(3, 0) = 0
f(3, 1) = 3
f(3, 2) = 6
f(3, 3) = 9

ce qui ressemble à une multiplication. Maintenant, expliquer pourquoi cet algorithme est celui d'une multiplication n'est pas dans mes compétences. Si c'est ça que tu voulais prouver, c'est réussi.

---------------------
[1] Certains spécialistes des mathématiques, dont je ne suis pas, reconnaitront peut être un des algorithmes de la multiplication entière, mais on sort du domaine de la programmation pour entrer dans celui de l'application. Je rappelle que l'informatique est un outil au service de la réalisation d'applications dans des domaines diverses, comme par exemple, les mathématiques.

**DaZumba** · 13/01/2006, 10h37

Envoyé par Emmanuel Delahaye

Ce que tu demande est du reverse ingeneering.

engineering would be a better spelling, wouldn't it?

**bigquick** · 13/01/2006, 10h44

bigquick: Tu fais une erreur, due à l'absence d'indentation du code:
L'opération sur y est conditionnelle, mais le doublement de b est inconditionnel: b est doublé, que le bit testé de a soit à 1 ou non.

Oooops ! .... Désolé

Donc effet ça ressemble à une multiplication. Je ne connaissais pas cette manière de procéder, mais comme dit Emmanuel Delahaye une serie de test peut nous mettre sur la voie.

Par contre c'est vrai qu'on peut y voir une similitude avec la multiplication en base 10 (ça peut faire un point de départ pour une reflexion plus poussée):

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
int mul_base_10 (int a, int b)
{
   y = 0;
 
   tant que (toujours des chiffres à traiter dans a)
   {
       y += chiffre_de_droite_de_a * b;     (*)
       b = b*10;
       décaler les chiffres de a vers la droite
   }
 
   return y;
}
 
ex ->  2084 * 3  =  4*3 + 8*30 + 2*3000 = 6252

(*) note : ici le test (chiffre_de_droite != 0) est facultatif puisqu'on multiplie de toute façon b par celui-ci. Ce n'était pas le cas dans le code original, mais ça aurait pu l'être puisque je pense que c'ést équivalent de faire:

Code :

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

1
2
if (a&1)
   y += b;

et

Code :

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

y += (a&1) * b;

**Emmanuel Delahaye** · 13/01/2006, 11h20

Envoyé par DaZumba

Envoyé par Emmanuel Delahaye

Ce que tu demande est du reverse ingeneering.

engineering would be a better spelling, wouldn't it?

Indeed ! Fixed.

**Biosox** · 13/01/2006, 12h27

je crois comprendre pourquoi c'est une multiplication.
Il faut observer a dans sa notation binaire

je m'explique avec un exemple:
faisons la multiplication a*b ou a=41 et b est un nombre quelconque.
alors si on regarde la notation binaire de a on a:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
a = 41 = 32 + 0 + 8 + 0 + 0 + 1  --> notation binaire 101001
(je pense que je n'apprends rien a personne jusqu'ici^^)
 
ainsi:
a * b = 41 * b = " (1 0 1 0 0 1) * b "
soit:
a * b = 41 * b = 32b + 0 + 8b + 0 + 0 + b
je l'écris dans "l'autre sens":
a * b = b + 0 + 0 + 8b + 0 + 32b
ou encore: 
a * b = 41 * b = (2^5)b + 0 + (2^3)b + 0 + 0 + b

or la boucle "while a " fait exactement ça:
le b += b sert a "fabriquer les (2^n)b:
et la condition if(a&1) sert à savoir si on doit additionner le (2^n)b courant ou pas!
cqfd, non?

dans notre cas on a:

passage 1: 101001 --> on additionne b
passage 2: 101001 --> on additionne PAS 2b
passage 3: 101001 --> on additionne PAS 4b
passage 4: 101001 --> on additionne 8b
passage 5: 101001 --> on additionne PAS 16b
passage 6: 101001 --> on additionne 32 2b

**babar56** · 13/01/2006, 14h52

Envoyé par Emmanuel Delahaye

Ce que tu demande est du reverse engineering. En dehors du fait que c'est une activité qui pourrait très bien être illégale, c'est une tout autre spécialité qui demande d'autres connaissances et une autre expérience.

Héhé elle est pas mal celle là, je ne la connaissais pas. "Non monsieur, cet exercice relève du reverse engineering. Votre examen est par conséquent parfaitement illégal !". J'aurais dû le tenter

Plus sérieusement Emmanuel : n'es-tu pas satisfait de l'explication de Biosox ? Une description clair de la mécanique de la fonction comme il l'a fait n'est pas une bonne chose selon toi ? Est-ce vraiment un mal que de demander à des gens qui ont les capacités pour comprendre un programme, qu'ils nous transmettent leur savoir ? Enfin, pour blamer encore un peu plus les explications expéditives, et bien on constate bien sur ce fil que même lorsqu'elles sont correctes comme celle de Médinoc (voir ci-dessus) elles passent inaperçu parce que pour quelqu'un qui n'est pas extrêmement à l'aise avec le sujet, l'explication parait incomplète, voir incompréhensible.

**Emmanuel Delahaye** · 13/01/2006, 15h16

Envoyé par babar56

Plus sérieusement Emmanuel : n'es-tu pas satisfait de l'explication de Biosox ?

Je sais pas. C'est un problème de math, pas de C. Les maths, je connais mal.

**diogene** · 14/01/2006, 11h27

Voilà mon grain de sel constructif

:
Cette fonction ne renvoie pas toujours a*b. Si c'est son objectif, elle est buggée

**babar56** · 14/01/2006, 14h44

En toute franchise, ça n'a rien de constructif. C'est tout au plus énigmatique. Prouve-le moi

**diogene** · 14/01/2006, 18h03

Prouve-le moi

Fait calculer xxx (-5, 5) par exemple. Ce code ne tolère pas que le premier nombre soit négatif : alors, il tourne éternellement , la condition a==0 n'étant jamais satisfaite!
A noter que ce code suppose que le codage des int est en complément à 2.