[Débutant] signification de "(code << 1) | 0x1&qu

Version imprimable

02/04/2006, 21h54
Lord Van

[Débutant] signification de "(code << 1) | 0x1&qu

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
02/04/2006, 22h08
progfou
Code:

code

est un int,

Code:

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:

1 2 3 4 5 0 0 0 0 1 1 1 0 1 1 1 1
Voila.
02/04/2006, 22h11
Trap D

Salut

Code:

(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.
02/04/2006, 22h15
Emmanuel Delahaye

Citation:

Envoyé par Trap D

Code:

(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:

(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.
02/04/2006, 22h20
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
02/04/2006, 22h21
Emmanuel Delahaye

Re: [Débutant] signification de "(code << 1) | 0x
Citation:

Envoyé par Lord Van

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

Code:

(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 (|).
Citation:

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.
02/04/2006, 22h29
Trap D

Citation:

Envoyé par 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:

(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.
02/04/2006, 22h32
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.
02/04/2006, 22h37
Emmanuel Delahaye

Citation:

Envoyé par Trap D

Citation:

Envoyé par 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:

(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.
02/04/2006, 22h38
Emmanuel Delahaye

Citation:

Envoyé par Lord Van

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.
02/04/2006, 22h42
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é.
02/04/2006, 22h48
Emmanuel Delahaye
Citation:
Envoyé par 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:

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:

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.
02/04/2006, 22h59
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 :lol:
02/04/2006, 23h09
Lord Van
Citation:
Envoyé par Emmanuel Delahaye

Citation:

Envoyé par 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:

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:

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 ?
02/04/2006, 23h18
Emmanuel Delahaye

Citation:

Envoyé par 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 :lol:

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 !
02/04/2006, 23h19
Emmanuel Delahaye

Citation:

Envoyé par Lord Van

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)
03/04/2006, 08h17
Trap D

Citation:

Envoyé par Emmanuel Delahaye

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 ?
03/04/2006, 08h46
Emmanuel Delahaye

Citation:

Envoyé par Trap D

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:

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:

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).
03/04/2006, 09h20
fearyourself

Citation:

Envoyé par Emmanuel Delahaye

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

Code:

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:

unsigned bit5 = pow(2,5);

parce que je ne connais que exp avec ce prototype:

Code:

double exp ( double x );

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

Jc
03/04/2006, 10h49
Emmanuel Delahaye

Citation:

Envoyé par fearyourself

Je suppose que tu veux parler de

Code:

unsigned bit5 = pow(2,5);

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

Corrigé. Merci.
03/04/2006, 17h28
Lord Van

Sinon, avez vous par hasard, un programme de compression de fichier texte selon la méthode de l'arbre de Huffman ?

merci d'avance
03/04/2006, 17h30
fearyourself

:google: devrait pouvoir t'aider...

Jc
03/04/2006, 19h29
Lord Van

okay !