Les opérations

Les opérations

Introduction à l’informatique Les entiers

Les opérations Addition et codage
Les champs de bits

Jean-Christophe Dubacq

IUT de Villetaneuse

S1 2016

« Introduction à l’informatique »
Les opérations — A

Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 1 / 24 Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 4 / 24

Les opérations Les entiers Les opérations Les entiers

Exercices Addition dans les systèmes positionnels

De la fonction à l’algorithme Exemple (Addition en base 2)

La numération grecque (simple) est proche de la numération romaine que vous connaissez : on note les
nombres comme suit :
Méthode (Addition) 1 1 10 1
1 5 10 50 100 500 1 000 5 000 10 000 50 000
Ι Γ ∆ Γ∆ Η ΓΗ Χ ΓΧ Μ ΓΜ L’addition en base B se fait de la droite vers la 1 0 0
gauche, colonne par colonne, en utilisant le fait
+ 1 0 1 1 0
C’est à la différence près que l’on a pas de règle soustractive : le nombre 4 s’écrit ΙΙΙΙ, pas ΙΓ. La position que la somme de chiffres s’écrit sous la forme
des chiffres n’a théoriquement aucune importance, mais on les classait dans l’ordre décroissant de valeur. s + Br, où s est la somme partielle (un chiffre + 1 1 1 1
unique) et r est la retenue. Le poids de r est B
Q1 Ce système est-il un système de numération positionnelle ? fois plus important, et r est donc remise dans la 1 0 1 0 0 1
colonne d’à côté.
Q2 Écrivez votre âge et votre date de naissance en numération grecque.
On peut aussi marquer la retenue 10 avec 0 dans
Q3 Écrivez un algorithme d’addition des nombres représentés en numération grecque. Est-ce que cet la colonne suivante et 1 dans la colonne d’ordre
algorithme est le même qu’en décimal ? encore supérieur.
Q4 Faites l’addition de votre âge et de votre année de naissance avec votre algorithme (vous devriez
obtenir ΧΧ∆ΙΙΙΙ ou ΧΧ∆ΙΙΙ). De quelle représentations partez-vous ? Truc : pour additionner une colonne, on peut bien sûr le faire en décimal, à condition de repasser au
Q5 Faites la même chose en décimal. De quelles représentations partez-vous ? Est-ce que l’algorithme binaire pour le reste et les retenues.
est le même ? Est-ce que la fonction calculée est la même ?

Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 6 / 24 Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 7 / 24
 Les opérations Les entiers Les opérations Les entiers

Multiplication Négatifs et réels

Par analogie avec les techniques maîtrisées en base 10, il est possible de faire également :
Méthode (Multiplication) É Des soustractions : lorsque le chiffre duquel on soustrait n’est pas suffisant, on ajoute 1 au chiffre à
soustraire dans la colonne d’ordre immédiatement supérieur, et en compensation, on ajoute la base
À l’instar de l’addition, la multiplication se fait comme pour les 1 1 0 dans la colonne courante.
nombres décimaux. Les tables sont justes différentes (il faut les × 1 0 1
écrire dans la bonne base !).
É Des divisions : en fait, on fait plein de multiplications enchaînées avec des soustractions.
1 1 0
En binaire, c’est très facile : on multiplie par 0 ou par 1, donc on se (+ 0 ) É Additionner un négatif, c’est soustraire un positif.
contente d’additionner des copies du multiplicande décalées là où le + 1 1 0 É Des opérations en virgule fixe : les règles de placement de la virgule sont les mêmes qu’en base 10.
multiplicateur a des 1. 1 1 1 1 0 É Des décalages qui sont des multiplications ou divisions par une puissance de la base.
Très important : décaler à gauche de n colonnes un nombre, c’est
le multiplier par Bn . Le décaler à droite, c’est le diviser par Bn . É Pour la virgule flottante, les multiplications sont simples ; les additions nécessitent de recoder en
virgule fixe.

« Introduction à l’informatique »
Les opérations — B

Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 8 / 24 Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 9 / 24

Les opérations Les entiers Les opérations Addition et codage

Exercices Les algorithmes d’addition

É L’addition de codage se fait par un algorithme (représentation/information). Si l’algorithme fait ce

Calcul en binaire et hexadécimal qu’on attend de lui (identique à la fonction), il est correct.
Q6 Faites les additions en binaire : 0b1101 0101+0b1110 0101 ; É Tous les nombres ne sont pas représentables. Si le résultat de l’addition (fonction) donne un nombre
0b1,1+0b110+0b100,1+0b111,1+0b1010,1+0b100,1. non représentable, l’algorithme ne peut pas être correct.
Q7 Faites les opérations suivantes en hexadécimal : 0122 + 0233 ; 087 + 054 ; É L’algorithme d’addition pour NAT et C2 est très similaire à la méthode usuelle (décrite avant) ; on
018 + 09 ; 0ED + 0ED ; 0100 − 03. coupe juste le résultat à la taille du codage.
Q8 Faites la multiplication suivante : 17 × 129 à la fois en décimal et en binaire.
Théorème
Q9 Faites la multiplication suivante en binaire : 110110 × 1101.
En C2 et NAT, si le résultat est représentable, l’addition (classique) est correcte.

Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 10 / 24 Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 12 / 24
 Les opérations Addition et codage Les opérations Addition et codage

Addition correcte ou pas ? Notes sur la multiplication et l’hexadécimal

Exemple (Addition en NAT)

code
131 + 85 =⇒ 1000 0011NAT + 0101 0101NAT
algo
Correct ! =
decode É La multiplication est extrêmement simple en binaire. Elle se comporte comme une série d’additions.
216 ⇐= 1101 1000NAT
code
É La multiplication est rarement correcte si on a autant de chiffres en entrée qu’en sortie. La plupart
187 + 101 =⇒ 1011 1011NAT + 0110 0101NAT des ordinateurs multiplient en mettant le résultat dans deux mots de code distincts (partie haute et
algo partie basse).
Incorrect ! =
decode
32(6= 288) ⇐= 0010 0000NAT

É En C1 et en VA+S, il suffit de mettre un négatif pour opération incorrecte

É En plus, problème du double zéro pour C1 et VA+S.
É C2 : comme si le bit de poids fort était de poids −2n−1 au lieu de 2n−1 , arithmétique modulo 2n .

« Introduction à l’informatique »
Les opérations — C

Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 13 / 24 Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 14 / 24

Les opérations Addition et codage Les opérations Les champs de bits

Exercices La logique booléenne

É Il est possible d’interpréter les deux valeurs binaires comme représentant respectivement vrai (1) ou
faux (0).
Limites de la multiplication É On peut définir des opérations correspondantes à la conjonction (et), la disjonction (ou) et la
Expliquez pourquoi le résultat d’une multiplication de deux nombres représentés dans l’un des 4 codes négation (opposé de).
classiques est toujours représentable à condition de doubler la taille du code.
Ce ne sont pas des opérations arithmétiques classiques.

Addition en C2 c = b ou c =  ∧ b pour le et (en C :  = b&c)

Q10 Faites les opérations suivantes en transformant les nombres au préalable en codage C2 sur 8 bits
(résultat aussi en C2 sur 8 bits) : c =  + b ou c =  ∨ b pour le ou (en C :  = b|c)
É 45+17
É 45-17 (soit 45+(-17)) b =  ou b = ¬ pour le non (en C :  =∼ c)
É -17-17
É 17-45
É 221+45 Exemple (chemin sous UNIX)
Dites aussi si le résultat obtenu est correct et s’il est représentable. Soit A(p) la propriété « p est un chemin existant » et B(p) la propriété « p est un chemin qui désigne
un répertoire ». Si on suppose qu’il n’y a que deux type d’objets (répertoires et fichiers), la propriété C(p)
« p est un chemin qui désigne un fichier » s’exprime par A(p)B(p).

Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 15 / 24 Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 17 / 24
 Les opérations Les champs de bits Les opérations Les champs de bits

Les opérateurs booléens Les opérateurs booléens

AND et OR XOR et NOT

AND XOR
L’opérateur binaire AND, noté  × b, renvoie 1 si et seulement si ses deux arguments sont égaux à 1. L’opérateur binaire XOR, noté  ⊕ b, renvoie 1 si et seulement si ses deux arguments sont différents.
L’opérateur général AND renvoie 1 si et seulement si tous ses arguments sont égaux à 1. Ils sont équivalents à la fonction différent.
Ils sont équivalents à la fonction minimum.
NOT
OR L’opérateur unaire NOT, noté , renvoie 0 si et seulement si son argument est égal à 1.
L’opérateur binaire OR, noté  + b, renvoie 0 si et seulement si ses deux arguments sont égaux à 0. Il est équivalent à la fonction complémentation.
L’opérateur général OR renvoie 0 si et seulement si tous ses arguments sont égaux à 0. Il y a aussi les opérateurs généraux NOR et NAND qui sont en fait NOT(OR(...)) et NOT(AND(...)). Ils sont
Ils sont équivalents à la fonction maximum. rarement implémentés dans les langages de programmation.

« Introduction à l’informatique »
Les opérations — D

Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 18 / 24 Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 19 / 24

Les opérations Les champs de bits Les opérations Les champs de bits

Exercices Les champs de bits

É La notion de variable booléenne stockant une valeur vraie ou faux est très souvent intégrée
directement dans les langages
Tables de vérité
Ce n’est pas le cas dans le langage C
Q11 Faites une table qui montre toutes les paires d’arguments possibles pour les opérateurs AND, OR,
XOR et qui montre le résultat à côté.
É On appelle parfois ces variables des flags (drapeaux).
É Quand on réunit plusieurs de ces variables dans une même entité, on appelle le résultat un champ
A B A×B A B A+B A B A⊕B de bits (anglais bit field).
0 0 0 0 0 0 É Ces champs de bits peuvent être stockés dans une seule variable (selon leur nombre). On les
0 1 0 1 0 1 considère comme un entier codé en NAT ou C2.
1 0 1 0 1 0 É On définit des opérations sur les champs de bits : le et bit-à-bit, le ou bit-à-bit, le not bit-à-bit et le xor
1 1 1 1 1 1 bit-à-bit.

Il s’agit de faire sur les bits de même position dans deux champs de bits (un pour la négation)
l’opération booléenne correspondante.

Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 20 / 24 Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 21 / 24
 Les opérations Les champs de bits Les opérations Les champs de bits

Exercices Masquage
Lorsqu’un champ de bits est représenté par un entier, on peut accéder à un bit particulier en procédant à
un ET :
b = (B&(1 << )) >> 
Opérations booléennes On obtient 1 si le bit numéro  est à 1, 0 sinon.
On peut aussi mettre à 1 le bit numéro  :
Q12 Que vaut 0b10000110 AND 0b11101001 ?
Q13 Que vaut 0b10000110 OR 0b11101001 ? B = B|(1 << )
Q14 Que vaut 0b10000110 XOR 0b11101001 ? ou à zéro :
Q15 Que se passe-t-il si on calcule ( est une variable booléenne) :  + 0 ?  + 1 ?  × 0 ?  × 1 ? B = B&(∼ (1 << ))
+ ? + + + + + ?
On peut aussi inverser le bit numéro  :
Q16 Démontrez que  + b =  ;
Q17 Démontrez que  + bc = ( + b)( + c) ; B = B ⊕ (1 << )
Q18 Démontrez que  + b =  + b ; On peut tester si par exemple le bit 1 ou 3 sont à 1 : if (a&0b1010 != 0) ...
L’ensemble de ces techniques pour manipuler un champ de bits sous la forme d’un entier est appelé
masquage.

« Introduction à l’informatique »
Souvent, les valeurs (1 << ) sont nommées pour qu’on puisse simplement utiliser leur nom au lieu de
se souvenir de leur position.
Les opérations — E

Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 22 / 24 Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 23 / 24

Les opérations Les champs de bits

Exercices

Analyse d’un masquage

Dans un champ de bits qui contient  = 0b11001001, on veut faire les choses suivantes :
Q19 On veut vérifier si le bit 0 est actif ou non. Décomposez l’opération.
Q20 On veut changer le bit 1 en 1 et le bit 3 en 0. Décomposez les opérations qui permettent de le faire.
Q21 Changez le bit 5, en expliquant les valeurs intermédiaires.

Analyse de touches
Dans un système, la fonction keyEvent() renvoie une valeur entière sur 16 bits (dont 5 ignorés) :
É Les 8 premiers bits correspondent au numéro de la touche sur le clavier (pour les touches ordinaires)
É Le 9e bit correspond à la touche SHIFT (1 : pressée, 0 : pas pressée)
É Le 10e bit correspond à la touche CONTROL (1 : pressée, 0 : pas pressée)
É Le 11e bit correspond au fait d’appuyer sur une touche (1) ou de l’avoir juste relachée (0)

Q22 Écrivez un programme qui appelle cette fonction (a=keyEvent()) puis qui en fonction de a
affiche un texte du genre : « Vous venez de lâcher la touche 27 en ayant SHIFT appuyé et CONTROL
lâché »

Jean-Christophe Dubacq (IUTV) Introduction à l’informatique S1 2016 24 / 24