Discussion :

[Lord Van]

Bonjour à tous,

voilà, je suis en train d'essayer de comprendre un programme et il y a une ligne que je ne comprends pas:

sachant que code est de type int,

je voulais savoir la conséquence de cette ligne d'instruction :

(code << 1) | 0x1

Merci d'avance pour vos explications !

En fait la variable code devrait contenir un nombre binaire. J'ai donc supposé que << faisait un décalage.

Merci pr vos lumières car j'en ai grandement besoin

[progfou]

Code :

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

code

est un int,

Code :

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

code << 1

décale code de 1, donc le multiplie par 2.
le | est un ou, et tu testes par conséquent le bit de poids le plus faible (0x01==1), le ou a pour table :

Code :

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

1
2
3
4
5
 
0 0 0
0 1 1
1 0 1
1 1 1

Voila.

[Trap D]

Salut

Code :

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

(code << 1) | 0x1

code << 1 correspond à un décalage des bits vers la gauche, donc à une multiplication par 2.
le | 0x1 veut dire qu'on fait un Ou bit à bit, c'est à dire qu'on force le bit le plus à droite à 1, c-a-d dans ce cas on ajoute 1.
si code = 12, (code << 1) | 0x1 vaut 25.

[Emmanuel Delahaye]

Code :

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

(code << 1) | 0x1

code << 1 correspond à un décalage des bits vers la gauche, donc à une multiplication par 2.
le | 0x1 veut dire qu'on fait un Ou bit à bit, c'est à dire qu'on force le bit le plus à droite à 1, c-a-d dans ce cas on ajoute 1.
si code = 12, (code << 1) | 0x1 vaut 25.

Tu fais une interprétation artithmétique juste, mais qui n'a peut être rien à voir avec la réalité.

Tout ce qu'on peut dire de

Code :

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

(code << 1) | 0x1

, c'est que la valeur de code est décalée de 1 bit vers la gauche et que le bit 0 est forcé à 1.

[Lord Van]

je vous remercie pour ces explications très claires. Je vais voir si cela coincide avec le raisonnement que j'ai fait du programme. Je peux vous en dire quelques mots : il s'agit en fait d'arbre de Huffman que je parcoure. C'est à dire que chaque noeud est un nombre (représentant le nb d'occurence d'un caractère dans un fichier texte). De plus, les feuilles de cet arbre ont en plus de ce nb d'occurences, le caractère en question. Donc, en fait, je parcours l'arbre de la racine jusqu'au feuille, et de droite à gauche. Quand je vais à droite, je mets un 1 dans la variable code, et un 0 quand je vais à gauche. Ainsi quand j'arrive aux feuilles, le caractère est relié à un code binaire. Sur internet, j'ai trouvé une fonction qui réalise cela mais je ne suis pas sur de bien la comprendre, pouvez vous me l'expliqué brièvement ? surtout la ligne que j'ai déjà évoqué précédemment !

Voici la fonction :

//La fonction placera dans un tableau de 512 entrées le code de chaque caractère a la position correspondant au code ascii index longu = index code + 256
//Parcours de droite a gauche, a chaque fois que l'arbre est feuille on rempli le tableau
//La fonction doit etre apelée avec mem = 0 et lon = 0.
void parcours_arbre(int *tab_code,int mem,int lon,arbre A)
{
if(est_vide(A))
{
//On place dans le tableau tab_code(2 ligne, 256 col) le code ainsi que sa longueur
tab_code[A->lettre] = mem;
tab_code[A->lettre + 256] = lon;
}
else
{
if(A->gauche)
parcours_arbre(tab_code,mem << 1,lon + 1,A->gauche);

if(A->droit)
parcours_arbre(tab_code,(mem << 1) | 0x1,lon + 1,A->droit);
}

}


Merci de votre aide

[Emmanuel Delahaye]

sachant que code est de type int, je voulais savoir la conséquence de cette ligne d'instruction :

Code :

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

(code << 1) | 0x1

Il n'y a aucun mystère, il suffit d'ouvrir son livre de C au chapitre 'opérateurs binaires' (bitwise operators).

1. code << 1 : la valeur de code est décalée de 1 bit vers la gauche.
2. Par conséquend, le bit 0 (LSB) passe à 0.
3. xxx | 0x1 : le bit 0 est forcé à 1 par l'opérateur OU (|).

En fait la variable code devrait contenir un nombre binaire.

Une variable contient toujours un nombre binaire, vu que c'est la représentation interne éxigée par le langage C et les machines courantes.

[Trap D]

Tu fais une interprétation artithmétique juste, mais qui n'a peut être rien à voir avec la réalité.

Tout ce qu'on peut dire de

Code :

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

(code << 1) | 0x1

, c'est que la valeur de code est décalée de 1 bit vers la gauche et que le bit 0 est forcé à 1.

code étant un int, dixit Lord Van, je ne vois pas ce que tu veux dire, la réalité est cellei que j'ai décrite il me semble, son interprétation c'est autre chose.

[Lord Van]

je me suis sans doute mal exprimé, code est un nombre binaire uniquement, ce n'est pas un entier !

Merci de m'expliquer la fonction écrite préalablement car elle utilise ces instructions logiques mais je ne suis pas sur de leurs conséquences réelles.

[Emmanuel Delahaye]

Tu fais une interprétation artithmétique juste, mais qui n'a peut être rien à voir avec la réalité.

Tout ce qu'on peut dire de

Code :

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

(code << 1) | 0x1

, c'est que la valeur de code est décalée de 1 bit vers la gauche et que le bit 0 est forcé à 1.

code étant un int, dixit Lord Van, je ne vois pas ce que tu veux dire, la réalité est cellei que j'ai décrite il me semble, son interprétation c'est autre chose.

Tu as parlé de multiplication par 2, d'addition... C'est de l'interprétation. Les faits c'est le décalage, le OU etc.

Ca peut implémenter un calcul ou tout autre chose. On a pas d'indications pour en dire plus.

[Emmanuel Delahaye]

je me suis sans doute mal exprimé, code est un nombre binaire uniquement, ce n'est pas un entier !

Je répète : la représentation interne de n'importe qulle valeur (entier, flottant, adresse, caractère...) est un nombre binaire.

[Trap D]

Mouais, je ne suis pas convaincu, car à part le cas du débordement le fait de décaler d'un bit sur la gauche, correspond à une multiplication par 2.
Maintenant on peut faire un décalage sur la gauche pour une autre raison, il n'en reste pas moins que le nombre est doublé.

[Emmanuel Delahaye]

Merci de m'expliquer la fonction écrite préalablement car elle utilise ces instructions logiques mais je ne suis pas sur de leurs conséquences réelles.

Code :

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

1
2
3
4
5
6
 
if(A->gauche) 
 parcours_arbre(tab_code,mem << 1,lon + 1,A->gauche);
 
if(A->droit)
parcours_arbre(tab_code,(mem << 1) | 0x1,lon + 1,A->droit);

Visiblement, une certaine valeur (mem) est stockée dans les bits x à 1, et en bit 0 on met 0 ou 1 selon que c'est une feuille droite ou gauche.

La valeur passée à parcours_arbre() en 2ème paramètre a la structure suivante (supposons 16 bits)

Code :

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

1
2
3
 
|<-bit 15 à 1 ->|<--- bit 0--->|
|mem 14...mem 0 | droite/gauche|

Note pour Trap : c'est une structure binaire, et pas du tout le résultat d'un opération arithmétique.

[Trap D]

J'ai bien compris ce que tu voulais dire, mais ce que tu prends pour interprétation est pour moi un fait et Lycée de Versaille

[Lord Van]

Merci de m'expliquer la fonction écrite préalablement car elle utilise ces instructions logiques mais je ne suis pas sur de leurs conséquences réelles.

Code :

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

1
2
3
4
5
6
 
if(A->gauche) 
 parcours_arbre(tab_code,mem << 1,lon + 1,A->gauche);
 
if(A->droit)
parcours_arbre(tab_code,(mem << 1) | 0x1,lon + 1,A->droit);

Visiblement, une certaine valeur (mem) est stockée dans les bits x à 1, et en bit 0 on met 0 ou 1 selon que c'est une feuille droite ou gauche.

La valeur passée à parcours_arbre() en 2ème paramètre a la structure suivante (supposons 16 bits)

Code :

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

1
2
3
 
|<-bit 15 à 1 ->|<--- bit 0--->|
|mem 14...mem 0 | droite/gauche|

Note pour Trap : c'est une structure binaire, et pas du tout le résultat d'un opération arithmétique.

que voulez vous dire par x à 1, que représente x ?

[Emmanuel Delahaye]

J'ai bien compris ce que tu voulais dire, mais ce que tu prends pour interprétation est pour moi un fait et Lycée de Versaille

Tu n'as pas fait assez d'assembleur (ou de logique câblée) mon fils.

Les opérations de bases sont binaires :

NOT, AND, OR, XOR SHL, SHR et c'est tout.

Intreprétées d'une certaine façon ces opération permettent de réaliser des opérations arithmétiques de plus en plus complexes. Mais tout est basé sur ces opérateurs simples.

En informatique industrielle, on apprend à câbler une ALU simplifiée (+, - X) mais avec retenue, ça calme !

[Emmanuel Delahaye]

que voulez vous dire par x à 1, que représente x ?

15 si la largeur de l'objet est de 16 bits (bits 15 à 0)

[Trap D]

Tu n'as pas fait assez d'assembleur (ou de logique câblée) mon fils.

Les opérations de bases sont binaires :

NOT, AND, OR, XOR SHL, SHR et c'est tout.

Intreprétées d'une certaine façon ces opération permettent de réaliser des opérations arithmétiques de plus en plus complexes. Mais tout est basé sur ces opérateurs simples.

Je n'en ai même jamais fait mon père.
Je crois avoir compris ton propos, mais il n'en reste pas moins qu'au niveau du résultat, en C, sur un entier, à part les cas de débordements, (ouf) le décalage d'un bit sur la gauche entraîne une multiplication par 2, oui ou non ?

[Emmanuel Delahaye]

Je crois avoir compris ton propos, mais il n'en reste pas moins qu'au niveau du résultat, en C, sur un entier, à part les cas de débordements, (ouf) le décalage d'un bit sur la gauche entraîne une multiplication par 2, oui ou non ?

Oui, c'est une conséquence, mais ce n'est pas forcément le but recherché. La vision purement mathématique (disons plutôt arithmétique) d'un problème risque de masquer d'autres aspects plus simples.

Ici, par exemple, le but n'était ni de faire une multiplication par 2, ni d'ajouter 1, mais de placer une valeur dans les bits 15 (ou 31 etc. selon l'implémentation) à 1, et un flag (droite/gauche) dans le bit 0.

Si je dois fabriquer un masque qui doit tester le bit 5, je vais tout simplement écrire

Code :

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

unsigned bit5 = 1u << 5;

parce que c'est simple clair et évident quand on connait les opérateurs binaires (de plus, c'est une expression constante...).

Un matheux sera capable d'aller chercher une fonction d'exponentionation par 2 genre
EDITED

Code :

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

unsigned bit5 = pow(2,5);

ce qui est bien sûr une anerie de réalisation, bien mathématiquement juste... (enfin, je crois, les maths, c'est pas mon fort).

[fearyourself]

Un matheux sera capable d'aller chercher une fonction d'exponentionation par 2 genre

Code :

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

unsigned bit5 = exp(2,5);

ce qui est bien sûr une anerie de réalisation, bien mathématiquement juste... (enfin, je crois, les maths, c'est pas mon fort).

Je suppose que tu veux parler de

Code :

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

unsigned bit5 = pow(2,5);

parce que je ne connais que exp avec ce prototype:

Code :

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

double  exp ( double x );

(bien que la solution matheuse entraînera un problème de typage)

Jc

[Emmanuel Delahaye]

Je suppose que tu veux parler de

Code :

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

unsigned bit5 = pow(2,5);

Oui ! Je n'utilise que très rarement les fonctions mathématiques...

Corrigé. Merci.