1_Representation_donnees_base_diapo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## <p style=\"text-align: center;\">NSI - Représentation des données : types et valeurs de base</p>\n",
    "## <p style=\"text-align: center;\">Lycée Beaussier - F. Lagrave</p>\n",
    "\n",
    "[![Binder](https://mybinder.org/badge_logo.svg)](https://mybinder.org/v2/gh/Fklag/NSI_iere/master?filepath=1_Representation_donnees_base_diapo.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Représentation des données : types et valeurs de base"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Toute machine informatique manipule une représentation des données dont l'unité minimale est le bit $0/1$, ce qui permet d'unifier logique et calcul.  \n",
    "Les données de base sont représentées selon un codage dépendant de leur nature : **entiers, flottants, caractères et chaînes de caractères**.   \n",
    "Le codage conditionne la taille des différentes valeurs en mémoire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Que signifie numériser de l'information ?  \n",
    "Avec le numérique, les textes, les photos, les sons sont transformés en **données binaires** (suite de $0$ et $1$) et vont être stockés sur des supports indifférenciés (un dvd par exemple contient aussi bien des images, du texte, des sons...).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$\\implies$ le **bit (Binary digiT)** est la quantité élémentaire d'information représentée par $2$ valeurs ($0$ ou $1$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Le codage numérique : encodage binaire  \n",
    "\n",
    "* **Informatique**\n",
    "  - L'encodage binaire correspond à la représentation de la donnée en binaire (base 2) un bit correspond à $0$ ou $1$\n",
    "* **Électronique**  \n",
    "  - $0 \\implies$ il n'y a pas de courant $\\quad:\\quad$  $1 \\implies$ il y a du courant  \n",
    "La mémoire d'un ordinateur est constituée d'une multitude de petits circuits électroniques. Chacun de ces circuits ne peut prendre que deux états. On associe traditionnellement l'un des états à $0$ et l'autre à $1$. De ce fait **toute information doit être traduite dans un ordinateur uniquement par des $0$ et des $1$**.  \n",
    "L'état d’un circuit, composé de plusieurs circuits mémoire-un-bit, se décrit par une suite finie de $0$ et de $1$ qu'on appelle **mot**.\n",
    "\n",
    "* **Mathématiques - Algèbre de Boole** :\n",
    "  - $0 \\implies$ faux $\\quad:\\quad$  $1 \\implies$ vrai"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<div style=\"background-color:#f0f0fa;\">\n",
    "En deux mots, la mémoire vive (la « RAM ») est formée de millions de composants électroniques qui peuvent retenir ou relâcher une charge électrique. La surface d'un disque dur, d'une bande ou d'une disquette est recouverte de particules métalliques qui peuvent, grâce à un aimant, être orientées dans un sens ou dans l’autre. Et sur un CD-ROM, on trouve un long sillon étroit irrégulièrement percé de trous.\n",
    "\n",
    "Ainsi, un ordinateur, c'est une machine capable de stocker et de manipuler des informations binaires. Rien de moins, mais rien de plus.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "On symbolise une information binaire, quel que soit son support physique, sous la forme de $1$ et de $0$.  \n",
    "**Il faut bien comprendre que ce n'est là qu'une représentation, une image commode, que l'on utilise pour parler de toute information binaire**.  \n",
    "Dans la réalité physique, il n'y a pas plus de $1$ et de $0$ qui se promènent dans les ordinateurs qu'il n'y a écrit, en lettres géantes, « Océan Atlantique » sur la mer quelque part entre la Bretagne et les Antilles.  \n",
    "Le $1$ et le $0$ dont parlent les informaticiens sont des signes, ni plus, ni moins, pour désigner une information, indépendamment de son support physique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "> Si la mémoire d'un ordinateur était constituée de dix circuits à mémoire-un-bit (autrement dit : par des mots de $10$ bits), quel serait le nombre d'états possibles de la mémoire de cet ordinateur ? Et avec $1$ milliard de circuits ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "> On veut représenter les $7$ couleurs de l'arc en ciel par un mot, les sept mots devant être distincts et de même longueur (en bits).  \n",
    "Quelle est la longueur minimale de ces mots ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<div style=\"background-color:#f0f0fa;\">\n",
    "Avec un bit, on peut enregistrer deux informations différentes : $0$ ou $1$.  \n",
    "    \n",
    "Avec deux bits, on forme 4 mots différents : $00$, $01$, $10$, $11$.  \n",
    "\n",
    "Avec trois bits, on forme $2^3$ mots différents : $000$, $001$, $010$, $011$, $100$, $101$, $110$, $111$.  \n",
    "\n",
    "Il faut donc au moins une longueur $3$. Mais on doit aussi pouvoir coder la <a href=\"http://lycee.lagrave.free.fr/nsi/numerisation/Information_binaire_beamer.pdf\" target=\"_blank\">nature de l'information transmise</a> pour que le logiciel utilisant cette information sache ici que les mots concernés représentent des couleurs.\n",
    "</div>    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Bits et octets  \n",
    "Les bits sont groupés et manipulés par paquets de $8$ (ils ne sont pas stockés individuellement) :\n",
    "- $8$ bits = $1$ octet = $1$ byte\n",
    "- $1$ Kilo octet = $1$ Ko = $1 000$ octets (*avant 1998 : $1 024$ octets*)\n",
    "- $1$ Méga octet = $1$ Mo = $1 000$ Ko (...)\n",
    "- $1$ Giga octet = $1$ Go = $1 000$ Mo \n",
    "- $1$ Téra octet = $1$ To = $1 000$ Go \n",
    "\n",
    "\n",
    "(Depuis décembre 1998, l'IEC a standardisé exemple $1$ ko = $1 000$ octets...[http://physics.nist.gov/cuu/Units/binary.html](http://physics.nist.gov/cuu/Units/binary.html))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "> Combien de valeurs différentes est-il possible de coder avec un seul octet ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$2^8$ valeurs différentes comprises entre $00000000$ et $11111111$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "> Est-ce logique ?\n",
    "\n",
    "<div style=\"text-align:center;\">\n",
    "<img src=\"./images/unites.jpg\" alt=\"unites\" width=\"60%\"/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* $100$ Go est plus commercial qu'environ $93,13$ Gio. Vérifiez sur une clé USB vendue pour $8$ Go par exemple : $8 000 000 000$ octets correspondent à environ $7,45$ Gio !  \n",
    "* les fabricants de mémoire continuent d’exprimer la capacité de leurs barrettes en unités binaires ($1$ Go = $1024$ Mo), les fabricants de disques durs ou de réseaux de communication ont, eux, décidé d'adopter la définition historiquement décimale des super-unités(pour laquelle $1$ Go = $1000$ Mo). Situation kafkaïenne lorsque l'on sait qu'un disque dur stocke pourtant des fichiers dont la taille est exprimée, elle, en super-unités binaires !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<div style=\"text-align:center;\">\n",
    "<img src=\"./images/kiBGiB.jpg\" alt=\"unites\" width=\"60%\"/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Le nombre mystère\n",
    "<a href=\"http://lycee.lagrave.free.fr/isn/html/nb_mystere/indx.html\" target=\"_blank\">Testez ici :</a>\n",
    "\n",
    "<div style=\"text-align:center;\">\n",
    "<img src=\"./images/magie.png\" alt=\"Tour\" width=\"60%\"/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Le codage des nombres en base $2$  \n",
    "Le codage des nombres : de la base décimale vers la base binaire  \n",
    "   \n",
    "| Base $10$ | Base $2$ |\n",
    "|:---------:|:---------:|\n",
    "| $0$       | $0000$   |\n",
    "| $1$       | $0001$   |\n",
    "| $2$       | $0010$   |\n",
    "| $3$       | $0011$   |\n",
    "| $4$       | $0100$   |\n",
    "| $5$       | $0101$   |\n",
    "| $6$       | $0110$   |\n",
    "| $7$       | $0111$   |\n",
    "| $8$       | $1000$   |\n",
    "| $9$       | $1001$   |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "|  entiers  | $0$ à $1$ | $0$ à $3$ | $0$ à $7$ | $0$ à $15$ | $0$ à $255$ | $0$ à $1023$ | $0$ à $4$ milliards | $0$ à plus de $1,8\\times10^{20}$ |\n",
    "|:---------:|-----------|-----------|-----------|------------|-------------|--------------|---------------------|----------------------------------|\n",
    "| codés sur | $1$ bits  | $2$ bits  | $3$ bits  | $4$ bits   | $8$ bits    |  $10$ bits   | $32$  bits | $64$ bits                        |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$\\implies$ Les ordinateurs utilisent $32$ ou $64$ bits pour coder les nombres entiers.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Le poids des bits  \n",
    "Dans un nombre binaire, la valeur d'un bit, appelée **poids**, dépend de la position du bit en partant de la droite.  \n",
    "Le poids d'un bit croît d'une puissance de deux en allant de la droite vers la gauche."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<div style=\"zoom:150%;\">\n",
    "    \n",
    "| <span style=\"color:red\">Nombre binaire :</span> | <span style=\"color:red\">$1$</span> | <span style=\"color:red\">$1$</span> | <span style=\"color:red\">$0$</span> | <span style=\"color:red\">$1$</span> | |\n",
    "|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|\n",
    "| Poids :          | $2^3$            | $2^2$            | $2^1$            |  $2^0$           | |\n",
    "| décimal $=$  | $8$          | $4$              |  $0$             |  $1$             | |\n",
    "|    $\\,$      | <span style=\"color:red\">$1$</span>$\\times2^3$ | $+\\,$<span style=\"color:red\">$1$</span>$\\times2^2$ | $+\\,$<span style=\"color:red\">$0$</span>$\\times2^1$ | $+\\,$<span style=\"color:red\">$1$</span>$\\times2^0$ |\n",
    "| <span style=\"color:blue\">**Nombre décimal :**</span> | $8$          | $ + \\, 4$        | $ + \\, 0$        | $ + \\, 1$ | <span style=\"color:blue\">$= 13$</span>   |\n",
    "\n",
    "</div>\n",
    "\n",
    "**Correspond au nombre décimal :**  \n",
    "Pour retrouver un nombre à partir de son code binaire : additionner les bits, chacun multiplié par la puissance de deux qui lui correspond"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## $1$ octet = $8$ bits  \n",
    "\n",
    "<div style=\"zoom:150%;\">\n",
    "    \n",
    "| <span style=\"color:red\">bit de poids fort MSB</span> | <span style=\"color:red\">$\\rightarrow 1$</span> | <span style=\"color:red\">$1$</span> | <span style=\"color:red\">$0$</span> | <span style=\"color:red\">$1$</span> | <span style=\"color:red\">$1$</span> | <span style=\"color:red\">$1$</span> | <span style=\"color:red\">$0$</span> | <span style=\"color:red\">$1 \\leftarrow$ </span> |<span style=\"color:red\">bit de poids faible LSB</span> |\n",
    "|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|\n",
    "| Poids :          | $2^7$            | $2^6$            | $2^5$            |  $2^4$           | $2^3$            | $2^2$            | $2^1$            |  $2^0$           | |\n",
    "| décimal $=$  | $128$          | $64$              |  $0$             |  $16$             | $8$          | $4$              |  $0$             |  $1$             | <span style=\"color:blue\">$= 221$</span>   |\n",
    "\n",
    "</div>   \n",
    "\n",
    "*MSB : Most Significant Bit*  \n",
    "*LSB : Least Significant Bit*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Exemple :** Une adresse IP est codée sur $4$ octets :  \n",
    "<p style=\"text-align:center;\">$192.168.2.3$ (<b>adresse IP</b> de classe C) correspond à</p>\n",
    "<p style=\"text-align:center;\">$11000000 \\quad 10101000 \\quad 00000010 \\quad 00000011$</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Le codage des nombres en base 16\n",
    "\n",
    "La base $16$ : les **nombres hexadécimaux**\n",
    "\n",
    "<div style=\"zoom:150%;\">\n",
    "    \n",
    "| Décimal | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$ |\n",
    "|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:|\n",
    "| Hexa          | <span style=\"color:red\">$0$</span> | <span style=\"color:red\">$1$</span> | <span style=\"color:red\">$2$</span> | <span style=\"color:red\">$3$</span> | <span style=\"color:red\">$4$</span> | <span style=\"color:red\">$5$</span> | <span style=\"color:red\">$6$</span> | <span style=\"color:red\">$7$</span> | <span style=\"color:red\">$8$</span> | <span style=\"color:red\">$9$</span> | <span style=\"color:red\">$A$</span> | <span style=\"color:red\">$B$</span> | <span style=\"color:red\">$C$</span> | <span style=\"color:red\">$D$</span> | <span style=\"color:red\">$E$</span> | <span style=\"color:red\">$F$</span> |\n",
    "| Binaire  | $0000$          | $0001$  |  $0010$     |  $0011$    | $0100$    | $0101$    | $0110$     |  $0111$             | $1000$   | $1001$          | $1010$  |  $1011$     |  $1100$    | $1101$    | $1110$    | $1111$   |\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Pour convertir de la base $2$ à la base $16$, des groupes de $4$ bits sont réalisés :  \n",
    "\n",
    "$11000101$ (en binaire) correspond à  $1100 \\quad 0101 \\implies C\\,5$ (en hexadécimal)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Les entiers en $\\texttt{Python}$ ne sont pas des entiers \"machine\" sur $32$ ou $64$ bits, ce sont des entiers mathématiques \"non bornés\" : ils peuvent être arbitrairement grand (l'unique limite étant la mémoire disponible sur la machine).  \n",
    "*Pour information les nombres entiers en $\\texttt{Python}$ sont représentés comme une suite de chiffres en base $2^{30}$.*  Plus <a href=\"https://rushter.com/blog/python-integer-implementation/\" target=\"_blank\">d'informations ici</a>.  \n",
    "\n",
    "On peut cependant demander d'afficher un entier en binaire ou en hexadécimal, et saisir un entier en binaire ou en hexadécimal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('0b101010', '0x2a', 3, 17)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(42),hex(42),0b11,0x11"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Lien entre le binaire et l'hexadécimal  \n",
    "**Du binaire à l'hexadécimal**  \n",
    "Comme $16 = 2^4$ , le passage de l'écriture en base $2$ à l'écriture en base $16$ peut se faire de la façon suivante.  \n",
    "- On regroupe les bits de l'écriture en base deux par paquets de quatre en commençant par le chiffre des unités et en ajoutant des zéros à gauche si nécessaire. \n",
    "\n",
    "  Par exemple, pour $N = 110110_{\\text{deux}}=110110_{2}$ , on regroupe ainsi : $N = 0011\\quad0110_{2}$ .\n",
    "- On traduit chaque paquet de quatre en base seize. \n",
    "\n",
    "  Avec l'exemple, $0110_{2} = 6_{\\text{seize}}=6_{16}$ et $\\,0011_{2} = 3_{16}$ .  \n",
    "- On a alors obtenu l'écriture hexadécimale de l'entier qui était donné en binaire : $N =110110_{2} = 0011\\quad0110_{2} = 36_{16}$ ."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "> Les entiers suivants sont donnés sous leur forme binaire.  \n",
    "Donner leur écriture hexadécimale (sans machine).\n",
    "$N_1 = 101010_{2}$, $\\,N_2 = 1111111111_{2}$.  \n",
    "Vous vérifierez vos calculs en utilisant dans un terminal : $\\texttt{hex}(\\texttt{int}('101010',2))$ ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('0x2a', '0x3ff')"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hex(int('101010',2)),hex(int('1111111111',2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**De l'hexadécimal au binaire**  \n",
    "Pour passer de la base $16$ à la base $2$, on traduit chaque chiffre de l'écriture hexadécimale en base deux, en octroyant systématiquement quatre bits à chacun des chiffres de l'écriture hexadécimale (quitte à ajouter des '0' sur la gauche).  \n",
    "\n",
    "Exemple avec  \n",
    "$N = 215_{\\text{seize}}=215_{16} \\, ; \\, \\,5_{16} = 101_{2} = 0101_{2}\\, ; \\,\\,1_{16} = 1_{2} =0001_{2}\\, \\text{ et } \\, 2_{16} = 10_{2} = 0010_{2}$ .  \n",
    "L'écriture binaire de  \n",
    "**$N = 215_{16} \\qquad \\text{ est donc } \\qquad 0010 \\quad 0001 \\quad 0101_{2} \\qquad$ (soit $N = 1000010101_{2}$).**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0b1000010101'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(int('215',16))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Savoir passer d'une écriture binaire à une écriture hexadécimale et vice-versa.  \n",
    "> Les deux entiers suivants sont donnés sous leur forme hexadécimale : $N_1 = 1A5$, $\\,N_2 = BAC$.  \n",
    "Donner leur écriture binaire. Vérifier avec $\\texttt{bin}(\\texttt{int}('BAC',16))$ ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('0b110100101', '0b101110101100')"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(int('1A5',16)),bin(int('BAC',16))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il résulte des deux paragraphes précédents que la forme hexadécimale est une sorte de **forme \"compacte\"** de l'écriture binaire et par là, plus facile à lire pour l'être humain.  \n",
    "C'est la raison pour laquelle elle est **souvent utilisée en informatique**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Rappel : Division euclidienne  \n",
    "\n",
    "<div style=\"background-color:#f0f0fa;\">\n",
    "Pour tout couple d’entiers naturels $(a~;~b)$ avec $a \\in \\texttt{I}\\!\\! \\texttt{N}$ et $b \\in \\texttt{I}\\!\\! \\texttt{N}-\\{0\\}$, il existe un unique couple $(q~;~r)$ d'entiers tels que \n",
    "\n",
    "$a = b q + r$ et $\\, 0 \\leqslant r \\leqslant b - 1$.\n",
    "    \n",
    "$q$ est appelé <b>quotient de la division euclidienne</b> (on parle aussi de division entière) de $a$ par $b$ et $r$ <b>reste</b> de cette division.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Exemple :** $34 = 9 \\times 3 + 7$, le reste de la division euclidienne de $34$ par $9$ est donc $7$.  \n",
    "Par contre le reste de la division euclidienne de $34$ par $3$ n'est pas $7$ (car le reste dans une division euclidienne par $3$ ne peut valoir que $0$, $1$ ou $2$).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "*On rappelle qu'en $\\texttt{Python}$ le reste de la division euclidienne de $a$ (de type $\\texttt{int}$) par $b$ (de type $\\texttt{int}$) est obtenu par l'instruction $a\\, \\% \\,b$  et le quotient de $a$ par $b$ par $a \\, // \\, b$.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "n=5489"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Après avoir exécuté la cellule précédente $n=5489$.  \n",
    "Exécutez $4$ fois la cellule suivante en observant les quotients et restes successifs :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5, 0)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r,n = n%10, n//10\n",
    "r,n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "En d'autres termes, l'application de la fonction $\\texttt{Chiffre}$ suivante à l'entier $5489$ aura le même effet que l'instruction suivante $\\,[\\, \\texttt{int}(i) \\quad \\texttt{for} \\, \\, i \\,\\, \\texttt{in} \\,\\,\\texttt{list}(\\texttt{str}(5489))\\,]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 4, 8, 9]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def Chiffre(n) :\n",
    "    \"\"\"int -> list\n",
    "    hypothese : n est un entier naturel donné par son écriture décimale\n",
    "    retourne les chiffres de l'entier naturel n sous forme d'une liste, dans l'ordre usuel de lecture.\n",
    "    \"\"\"\n",
    "    L =[]\n",
    "    while n != 0 :\n",
    "        L = [n%10] + L\n",
    "        n = n//10\n",
    "    return L\n",
    "\n",
    "Chiffre(5489)\n",
    "#[int(i) for i in list(str(5489))]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### L'écriture binaire d’un entier (ou écriture en base deux)  \n",
    "Celle-ci est obtenue en remplaçant $10$ par $2$ dans le script du paragraphe précédent qui donnait les chiffres d’un entier en base $10$.  \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "> Donner, sans machine, l'écriture binaires des entiers ci-dessous. Vous vérifierez ensuite l'exactitude de votre réponse à l'aide de l'algorithme précédent ou à l'aide de la fonction $\\texttt{Python bin}()$ qui prend en paramètre un entier naturel (donné par son écriture décimale) et retourne l'écriture binaire de l'entier (précédée de $0b$ pour signaler qu'il s'agit d'une écriture binaire).  \n",
    "$N_1 = 15$, $\\,N_2 = 32$, $\\,N_3 = 7$, $N_4 = 8$.\n",
    "\n",
    "**Vous devrez savoir passer de l'écriture décimale à l'écriture binaire d'un entier (sans machine)**.\n",
    "\n",
    "On obtient $\\, 11_{10} = 1011_{2}$.\n",
    "\n",
    "<div style=\"text-align:center;\">\n",
    "<img src=\"./images/divcasc.png\" alt=\"unites\" width=\"60%\"/>\n",
    "    \n",
    "    <--------------------------------------------------\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('0b1111', '0b100000', '0b111', '0b1000')"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(15),bin(32),bin(7),bin(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "> Justifier que tout entier naturel possède une écriture binaire, c’est à dire que pour tout entier naturel donné en entrée de l’algorithme des divisions en cascade avec la base deux, l’algorithme se terminera."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Lorsqu'on divise un entier non nul $n$ par $2$, on obtient un entier strictement plus petit.  \n",
    "La suite des quotients dans l'algorithme serait donc une suite infinie d’entiers positifs distincts si $n$ ne prenait jamais la valeur $0$.  \n",
    "**Comme une suite d'entiers positifs distincts, inférieurs à un entier $n$ donné, ne contient qu'au plus $n$ termes, l'algorithme doit se terminer.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "En d'autres termes, vous obtiendrez l'écriture binaire de l'entier naturel $n$ par l'algorithme suivant (appelé *algorithme des divisions en cascade*) \n",
    "\n",
    "$\\quad$ On procède par divisions euclidiennes successives :\n",
    "> -On divise le nombre par la base,  \n",
    "> -puis le quotient par la base,  \n",
    "> -**ainsi de suite jusqu'à obtenir un quotient nul**.  \n",
    "La suite des restes obtenus correspond aux chiffres dans la base visée.\n",
    "\n",
    "> traduit en $\\texttt{Python}$ avec ici une sortie de type $\\texttt{str}$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1010101110001'"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def Conv_bin(n) :\n",
    "    \"\"\"int -> str\n",
    "    hypothese : n est un entier naturel donné par son écriture décimale\n",
    "    retourne l'écriture binaire de l'entier naturel n sous forme d'une chaîne de caractères.\n",
    "    \"\"\"\n",
    "    C =\"\"\n",
    "    while n != 0 :\n",
    "        C = str(n%2) + C\n",
    "        n = n//2\n",
    "    return C\n",
    "\n",
    "Conv_bin(5489)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "assert Conv_bin(5489) == bin(5489)[2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Il est intéressant de **visualiser** comment **l'enchaînement récursif** des opérations de quotient et reste permettent de retrouver l'écriture en base $b$ d'un nombre, en partant de la base $10$.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "!{sys.executable} -m pip install tutormagic\n",
    "%load_ext tutormagic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Méthode par division**  \n",
    "On divise par $b$ autant de fois que nécessaire pour obtenir un quotient nul et l'on écrit les restes dans l'ordre inverse où ils ont été obtenus.  \n",
    "\n",
    "Par exemple, si je veux afficher un nombre en base $3$, je peux utiliser l'algorithme suivant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "        <iframe\n",
       "            width=\"100%\"\n",
       "            height=\"350\"\n",
       "            src=\"http://pythontutor.com/iframe-embed.html#code=def%20base3%28n%29%3A%0A%20%20%20%20if%20n%20%3C%203%20%3A%0A%20%20%20%20%20%20%20%20print%28n%2C%20end%3D%27%27%29%0A%20%20%20%20else%20%3A%0A%20%20%20%20%20%20%20%20base3%28n%20//%203%29%0A%20%20%20%20%20%20%20%20print%28n%20%25%203%2C%20end%3D%27%27%29%0A%0Abase3%2842%29%0A&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&curInstr=0&&verticalStack=false&py=3&rawInputLstJSON=%5B%5D&codeDivWidth=50%25&codeDivHeight=100%25\"\n",
       "            frameborder=\"0\"\n",
       "            allowfullscreen\n",
       "        ></iframe>\n",
       "        "
      ],
      "text/plain": [
       "<IPython.lib.display.IFrame at 0x7f6c14aaa588>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%tutor\n",
    "def base3(n):\n",
    "    if n < 3 :\n",
    "        print(n, end='')\n",
    "    else :\n",
    "        base3(n // 3)\n",
    "        print(n % 3, end='')\n",
    "\n",
    "base3(42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Écriture octale d'un entier - base $8$.  \n",
    "L'écriture en base huit d'un entier est obtenue en utilisant la base $8$ dans l'algorithme de division en cascade.  \n",
    "En d'autres termes, vous obtiendrez l'écriture octale de l'entier naturel $n$ par la fonction suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'101'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def Conv_oct(n) :\n",
    "    \"\"\"int -> str\n",
    "    hypothese : n est un entier naturel donné par son écriture décimale\n",
    "    retourne l'écriture octale de l'entier naturel n sous forme d'une chaîne de caractères.\n",
    "    \"\"\"\n",
    "    C =\"\"\n",
    "    while n != 0 :\n",
    "        C = str(n%8) + C\n",
    "        n = n//8\n",
    "    return C\n",
    "\n",
    "Conv_oct(65)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert Conv_oct(72) == oct(72)[2:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "> Donner, sans machine, l'écriture en base huit des entiers ci-dessous. Vous vérifierez ensuite l'exactitude de votre réponse à l'aide de l'algorithme précédent ou à l'aide de la fonction $\\texttt{Python oct}()$ qui prend en paramètre un entier naturel (donné par son écriture décimale) et retourne l'écriture octale de l'entier (précédée de $0o$ pour signaler qu'il s'agit d'une écriture octale).  \n",
    "$N_1 = 8$, $\\,N_2 = 11$, $\\,N_3 = 16$, $N_4 = 67$, $\\,N_5 = 158$.\n",
    "\n",
    "**Vous devrez savoir passer de l'écriture décimale à l'écriture octale d'un entier (sans machine)**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('0o10', '0o13', '0o20', '0o103', '0o236')"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "oct(8),oct(11),oct(16),oct(67),oct(158)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Savoir passer du binaire à l'octal.**  \n",
    "Le système octal possède l'avantage de ne pas requérir de symbole supplémentaire pour ses chiffres.  \n",
    "À partir de la numération binaire, on groupe les chiffres consécutifs en triplets.  \n",
    "Ainsi, la représentation binaire du nombre décimal $74$ est $1001010_{2}$, que l'on\n",
    "groupe en $(00)1\\quad 001 \\quad 010_{2}$ s'écrit $112_{8}$ en octal ou encore : $0112_{8}$\n",
    "\n",
    "> Convertir $0x67=67_{\\text{seize}}=67_{16}$ en octal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0o147'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "oct(0x67)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "$67_{16}=0110 \\quad 0111_{2}= (0)01 \\quad 100 \\quad 111_{2}= 147_{8}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Écriture hexadécimale d'un entier - base $16$.  \n",
    "L'écriture en base seize d'un entier est obtenue en utilisant la base $16$ dans l'algorithme de division en cascade.  \n",
    "En d'autres termes, vous obtiendrez l'écriture hexadécimale de l'entier naturel $n$ par la fonction suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'215'"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def Conv_hex(n) :\n",
    "    \"\"\"int -> str\n",
    "    hypothese : n est un entier naturel donné par son écriture décimale\n",
    "    retourne l'écriture hexadécimale de l'entier naturel n sous forme d'une chaîne de caractères.\n",
    "    \"\"\"\n",
    "    C =\"\"\n",
    "    while n != 0 :\n",
    "        C = str(n%16) + C\n",
    "        n = n//16\n",
    "    return C\n",
    "\n",
    "Conv_hex(47)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-22-d4eef24d5735>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0mConv_hex\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m47\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0mhex\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m47\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mupper\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "assert Conv_hex(47) == hex(47)[2:].upper()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "> Pour écrire un nombre en base $16$, on utilise les $10$ chiffres usuels et les lettres $A, B, C, D, E, F$.   Pourquoi ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Représentation des nombres**  (Voir <a href=\"http://lycee.lagrave.free.fr/nsi/numerisation/TD_Representation_Information.pdf\" target=\"_blank\">DM  Représentation de l'information</a>)\n",
    "On représente les nombres grâce à des symboles :\n",
    "* **Représentation unaire** : un symbole de valeur unique  \n",
    "  * $I = 1 \\quad II = 2 \\quad III = 3 \\quad IIIIIIIIII = 10$ ;\n",
    "  * Le calcul est facile : $\\,I + III = IIII \\quad ; \\quad II \\times III = II \\,\\, II \\,\\, II = IIIIII$  ;\n",
    "  * mais cela devient vite incompréhensible.  \n",
    "* **Chiffres Romains** : plusieurs symboles ayant des valeurs différentes  \n",
    "  * $I = 1 \\quad V = 5  \\quad X = 10 \\quad L = 50$, le nombre de symboles est théoriquement infini. \n",
    "  * Le calcul est impossible.\n",
    "  \n",
    "* **Système positionnel** : symboles dont la valeur dépend de la position\n",
    "  * $999 = 900 + 90 + 9$\n",
    "  * À Babylone, système sexagésimal $(60)$ (IIe millénaire av J-C).\n",
    "  * Transmission de l'orient vers l'occident de cette représentation et du zéro (env. $825$ ap. J-C)\n",
    "  \n",
    "**Système positionnel : Utilisation d'une base**  \n",
    "Le plus souvent la valeur d'un chiffre dépend du nombre de symboles : la **base**.  \n",
    "\n",
    "En base $b$, les nombres sont représentés à l'aide de $b$ symboles distincts.   \n",
    "Un nombre $x$ est représenté par une suite de symboles :  $x = a_{n} a_{n-1} \\cdots a_{1} a_{0}$ .    \n",
    "**Décimale $\\quad \\, \\,$ ($b = 10$)**, $\\, a_i \\in \\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \\}$  \n",
    "**Binaire $\\qquad \\,$ ($b = 2$)**, $\\, \\, a_i \\in \\{0, 1\\}$  \n",
    "**Hexadécimale ($b = 16$)**, $\\, a_i \\in \\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F \\}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "*Pour écrire un entier en base $b$ (où $b$ est un entier au moins égal à $2$), on utilise l'algorithme des divisions en cascade... Toutefois, lorsque $b$ est supérieur ou égal à $10$, de nouveaux symboles devront être introduits pour les restes obtenus supérieurs ou égaux à $10$.*\n",
    "\n",
    "> Modifier le programme précédent de façon à ce que $10$ soit remplacé par la lettre $A$, $11$ par la lettre $B$, $12$ par la lettre $C$, $13$ par la lettre $D$, $14$ par la lettre $E$, $15$ par la lettre $F$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'2F'"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def Conv_hex(n) :\n",
    "    \"\"\"int -> str\n",
    "    hypothese : n est un entier naturel donné par son écriture décimale\n",
    "    retourne l'écriture hexadécimale de l'entier naturel n sous forme d'une chaîne de caractères.\n",
    "    \"\"\"\n",
    "    dico = dict()\n",
    "    for i in range(10) : dico[i]=i\n",
    "    for i in range(10,16) : dico[i]= chr(i+55)\n",
    "    #dico = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 'A', 11: 'B', 12: 'C', 13: 'D', 14: 'E', 15: 'F'}\n",
    "    C =\"\"\n",
    "    while n != 0 :\n",
    "        C = str(dico[n%16]) + C\n",
    "        n = n//16\n",
    "    return C\n",
    "\n",
    "Conv_hex(47)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "assert Conv_hex(47) == hex(47)[2:].upper()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "> Donner, sans machine, l'écriture en base seize des entiers ci-dessous. Vous vérifierez ensuite l'exactitude de votre réponse à l'aide de l'algorithme précédent ou à l'aide de la fonction $\\texttt{Python hex}()$ qui prend en paramètre un entier naturel (donné par son écriture décimale) et retourne l'écriture hexadécimale de l'entier (précédée de $0x$ pour signaler qu'il s'agit d'une écriture hexadécimale).  \n",
    "$N_1 = 17$, $\\,N_2 = 155$, $\\,N_3 = 16$.\n",
    "\n",
    "**Vous devrez savoir passer de l'écriture décimale à l'écriture hexadécimale d'un entier (sans machine)**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('0x11', '0x9b', '0x10')"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hex(17),hex(155),hex(16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Combinaisons linéaires des puissances de la base."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Cas de la base $10$**.  \n",
    "Considérons l'entier $N = 4567$.  \n",
    "Les chiffres de cette écriture décimale peuvent être obtenus par l'algorithme des divisions en cascade.  \n",
    "Appliquons le étape par étape.  \n",
    "- $N = 10 \\times 456 + 7$.  \n",
    "- $456 = 10 \\times 45 + 6$, d'où $\\,N = 10 \\times (10 \\times 45 + 6) + 7$, soit $\\, N = 10^2 \\times 45 + 10 \\times 6 + 7$.  \n",
    "- $45 = 10 \\times 4 + 5$ d'où $\\,N = 10^2 \\times (10 \\times 4 + 5) + 10 \\times 6 + 7$ et $\\,N = 10^3 \\times 4 + 10^2 \\times 5 + 10 \\times 6 + 7$.  \n",
    "On retrouve ainsi les notions d’unité, dizaine, centaine, millier $\\ldots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Du binaire au décimal**  \n",
    "En procédant de la même façon que ci-dessus, on obtient les notions d'**unité, deuzaine, quatraine, huitaine $\\ldots$** pour la base deux.  \n",
    "L'écriture $N = 1101_{\\text{deux}}= 1101_{2}$ donne par exemple $\\,N = 1 \\times 2^3 + 1 \\times 2^2 + 0 \\times 2^1 + 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Savoir passer du binaire au décimal.**  \n",
    "> Donner l'écriture en base dix des entiers suivants (sans machine) : $N_1 = 1101_{2}$ , $\\,N_2 = 10100_{2}$.  \n",
    "Vous vérifierez la validité de vos réponses à l'aide de $\\texttt{int}('1101',2)$ , $\\,\\texttt{int}('10100',2)$ ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(13, 20)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int('1101',2),int('10100',2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**De l'octal au décimal**  \n",
    "De la même façon que précédemment, l'écriture $457_{\\text{huit}}=457_{8}$ désigne en fait l'entier $\\,4 \\times 8^2 + 5 \\times 8 + 7$.\n",
    "\n",
    "> Donner, sans machine, les écritures décimales de $N_1 = 77_{8}$ et $N_2 = 145_{8}$.  \n",
    "Vous vérifierez ensuite vos calculs à l'aide de $\\texttt{int}('77',8)$ , $\\,\\texttt{int}('145',8)$ ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(63, 101)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int('77',8),int('145',8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**De l'hexadécimal au décimal**  \n",
    "> Donner, sans machine, les écritures décimales de $N_1 = AA_{\\text{seize}}=AA_{16}$ et $\\,N_2 = B7A_{16}$.  \n",
    "Vous vérifierez ensuite vos calculs à l'aide de $\\texttt{int}('AA',16)$, $\\,\\texttt{int}('B7A',16)$ ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(170, 2938)"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int('AA',16),int('B7A',16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Relations entre les bases $2$, $8$ et $16$\n",
    "\n",
    "**Conversion de la base $2$ vers la base $8$**  \n",
    "<script>document.write(groupementsDeBits(335, 2, 8));</script>\n",
    "<table><tbody><tr><td class=\"groupement\">$101$</td><td class=\"groupement\">$001$</td><td class=\"groupement\">$111$</td></tr><tr><td><center><span class=\"green\"><b>⬇</b></span></center></td><td><center><span class=\"green\"><b>⬇</b></span></center></td><td><center><span class=\"green\"><b>⬇</b></span></center></td></tr><tr><td class=\"groupement\">$5$</td><td class=\"groupement\">$1$</td><td class=\"groupement\">$7$</td></tr><tr><td colspan=\"3\">&nbsp;</td></tr>\n",
    "    <tr><td class=\"resultat\" colspan=\"3\">$101001111_{2} = 517_{8}$</td></tr></tbody></table>\n",
    "\n",
    "Si la représentation binaire ne contient pas un nombre de bits multiple de $3$, on effectue les regroupements à partir de la droite.\n",
    "<script>document.write(groupementsDeBits(172, 2, 8));</script>\n",
    "<table><tbody><tr><td class=\"groupement\">$10$</td><td class=\"groupement\">$101$</td><td class=\"groupement\">$100$</td></tr><tr><td><center><span class=\"green\"><b>⬇</b></span></center></td><td><center><span class=\"green\"><b>⬇</b></span></center></td><td><center><span class=\"green\"><b>⬇</b></span></center></td></tr><tr><td class=\"groupement\">$2$</td><td class=\"groupement\">$5$</td><td class=\"groupement\">$4$</td></tr><tr><td colspan=\"3\">&nbsp;</td></tr>\n",
    "    <tr><td class=\"resultat\" colspan=\"3\">$10101100_{2}  = 254_{8}$</sub></td></tr></tbody></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Conversion de la base $2$ vers la base $16$**  \n",
    "<script>document.write(groupementsDeBits(178, 2, 16));</script>\n",
    "<table><tbody><tr><td class=\"groupement\">$1011$</td><td class=\"groupement\">$0010$</td></tr><tr><td><center><span class=\"green\"><b>⬇</b></span></center></td><td><center><span class=\"green\"><b>⬇</b></span></center></td></tr><tr><td class=\"groupement\">$B$</td><td class=\"groupement\">$2$</td></tr><tr><td colspan=\"2\">&nbsp;    \n",
    "             </td></tr><tr><td class=\"resultat\" colspan=\"2\">$10110010_{2}= B2_{16}$</td></tr></tbody></table>\n",
    "<div class=\"remarque\">\n",
    "Si la représentation binaire ne contient pas un nombre de bits multiple de $4$, on effectue les regroupements à partir de la droite.\n",
    "<script>document.write(groupementsDeBits(335, 2, 16));</script><table><tbody><tr><td class=\"groupement\">$1$\n",
    "    </td><td class=\"groupement\">$0100$</td><td class=\"groupement\">$1111$</td></tr><tr><td><center><span class=\"green\"><b>⬇</b></span></center></td><td><center><span class=\"green\"><b>⬇</b></span></center></td><td><center><span class=\"green\"><b>⬇</b></span></center></td></tr><tr><td class=\"groupement\">$1$</td><td class=\"groupement\">$4$</td><td class=\"groupement\">F</td></tr><tr><td colspan=\"3\">&nbsp;    \n",
    "             </td></tr><tr><td class=\"resultat\" colspan=\"3\">$101001111_{2} = 14F_{16}$</td></tr></tbody></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Conversion de la base $8$ vers la base $2$**  \n",
    "<script>document.write(groupementsDeBits(335, 8, 2));</script>\n",
    "<table><tbody><tr><td class=\"groupement\">$5$</td><td class=\"groupement\">$1$</td><td class=\"groupement\">$7$</td></tr><tr><td><center><span class=\"green\"><b>⬇</b></span></center></td><td><center><span class=\"green\"><b>⬇</b></span></center></td><td><center><span class=\"green\"><b>⬇</b></span></center></td></tr><tr><td class=\"groupement\">$101$</td><td class=\"groupement\">$001$</td><td class=\"groupement\">$111$</td></tr><tr><td colspan=\"3\">&nbsp;</td></tr>\n",
    "    <tr><td class=\"resultat\" colspan=\"3\">$517_{8} = 101001111_{2}$</td></tr></tbody></table>\n",
    "\n",
    "\n",
    "**Conversion de la base $16$ vers la base $2$**  \n",
    "<script>document.write(groupementsDeBits(335, 16, 2));</script>\n",
    "<table><tbody><tr><td class=\"groupement\">1</td><td class=\"groupement\">4</td><td class=\"groupement\">$F$</td></tr><tr><td><center><span class=\"green\"><b>⬇</b></span></center></td><td><center><span class=\"green\"><b>⬇</b></span></center></td><td><center><span class=\"green\"><b>⬇</b></span></center></td></tr><tr><td class=\"groupement\">$1$</td><td class=\"groupement\">$0100$</td><td class=\"groupement\">$1111$</td></tr><tr><td colspan=\"3\">&nbsp;</td></tr>\n",
    "    <tr><td class=\"resultat\" colspan=\"3\">$14F_{16} = 101001111_{2}$</td></tr></tbody></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Hexadécimal, octal : utilité\n",
    "\n",
    "La correspondance directe entre groupements de bits et chiffres en octal/hexadécimal permet d'avoir une écriture plus concise d'une information de nature binaire.\n",
    "\n",
    "**exemple d'utilisation de l'octal : les droits d'accès sous Linux**  \n",
    "Chacun des $9$ droits d'accès est stocké sur $1$ bit : si le bit vaut $1$, le droit correspondant est accordé. Si le bit vaut $0$, le droit correspondant est refusé.  \n",
    "<table>\n",
    "        <tbody><tr><th>exemple :</th><td style=\"padding-left : 32px\"></td><td>$r$</td><td>$w$</td><td>$x$</td><td>$r$</td><td>$-$</td><td>$x$</td><td>$r$</td><td>$-$</td><td>$-$</td></tr>\n",
    "            <tr><th>représentation binaire</th><td style=\"padding-left : 32px\"></td><td>$1$</td><td>$1$</td><td>$1$</td><td>$1$</td><td>$0$</td><td>$1$</td><td>$1$</td><td>$0$</td><td>$0$</td></tr>\n",
    "            <tr><th>représentation octale</th><td style=\"text-align : center; padding-left : 32px\"></td><td colspan=\"3\">$7$</td><td colspan=\"3\">$5$</td><td colspan=\"3\">$4$\n",
    "        </td></tr></tbody></table>\n",
    "\n",
    "    \n",
    "> La commande $\\, \\texttt{chmod}\\,$ accepte les arguments en octal. \n",
    "  Ainsi $\\, \\texttt{chmod}\\,\\, 754\\,\\,  \\texttt{fichier}$ modifiera en une fois les $9$ droits d'accès avec les valeurs de l'exemple ci-dessus.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**exemple d'utilisation de l'hexadécimal : codage des couleurs**  \n",
    "Une couleur est souvent représentée par $3$ valeurs de $8$ bits, les composantes <span class=\"red\"><b>rouge</b> (R)</span>, <span class=\"green\"><b>verte</b> (V)</span> et <b>bleue</b> (B).  \n",
    "Ainsi, le **blanc** est défini par les valeurs ( <span class=\"red\"><b>$255$</b></span> , <span class=\"green\"><b>$255$</b></span> , <b>$255$</b> ), le **noir** par ( <span class=\"red\"><b>$0$</b></span> , <span class=\"green\"><b>$0$</b></span> , <b>$0$</b> ).  \n",
    "Entre les deux, on trouve les couleurs du spectre visible et leurs nuances : jaune ( <span class=\"red\"><b>$255$</b></span> , <span class=\"green\"><b>$255$</b></span> , <b>$0$</b> ), mauve ( <span class=\"red\"><b>$255$</b></span> , <span class=\"green\"><b>$0$</b></span> , <b>$255$</b> ), etc $\\ldots$\n",
    "\n",
    "**Rappel** en langage $\\texttt{CSS}$, les couleurs peuvent être exprimées de plusieurs façons :\n",
    "        <ul>\n",
    "        <li> <b>nom</b> : black, yellow...\n",
    "        </li><li> <b>composantes $\\texttt{RVB}$ en base $10$</b> : rgb(<span class=\"red\"><b>$255$</b></span>, <span class=\"green\"><b>$123$</b></span>, <span class=\"blue\"><b>$34$</b></span>)\n",
    "        </li><li> <b>composantes $\\texttt{RVB}$ en base $16$</b> : $\\#$ <span class=\"red\">$FF$</span><span class=\"green\">$7B$</span><span class=\"blue\">$22$</span>\n",
    "\t</li><li> Expérimentez avec ce sélecteur de couleurs : <input type=\"color\" value=\"#FF7B22\">\n",
    "        </li></ul>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Plus grand entier représentable en binaire sur $n$ bits.  \n",
    "**Somme de termes en progression géométrique**  \n",
    "\n",
    "Soit $q \\neq 1$. $\\, 1 + q + q^2 + \\cdots + q^{n-1} = \\dfrac{q^n -1}{q-1} \\qquad$ **En particulier** \\, $1 + 2 + 2^2 + 2^3 + \\cdots + 2^{n-1} = 2^{n}- 1$.\n",
    "\n",
    "*Preuve.*  \n",
    "On note $S = 1 + q + q^2 + \\cdots + q^{n-1}$  \n",
    "Alors \\, $qS - S = q\\left(1 + q + q^2 + \\cdots + q^{n-1}\\right) - \\left(1 + q + q^2 + \\cdots + q^{n-1}\\right)\n",
    "$  \n",
    "soit \\, $S\\left(q - 1\\right) = q + q^2 + \\cdots + q^{n-1} + q^n - 1 - q - q^2 - \\cdots  - q^{n-1}$  \n",
    "et \\, $S\\left(q - 1\\right) = q^n -1$\n",
    "\n",
    "\n",
    "**Sur un mot de $n$ bits, on peut représenter en binaire les entiers compris entre $0$ et $\\,2^{n}-1$.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "> 1. Quels entiers naturels peut-on écrire en binaire sur un octet ?  \n",
    "> 2. Quels entiers naturels peut-on écrire en binaire sur un mot de $32$ bits ?\n",
    "> 3. Quels entiers naturels peut-on écrire en binaire sur un mot de $64$ bits ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Opérations en binaire.   \n",
    "**Si l'on dispose de l'écriture d'un entier $n$ en base dix, il suffit d'ajouter un $0$ à sa droite pour avoir l’écriture de l’entier $10n$.**\n",
    "\n",
    "> On dispose de l'écriture d'un entier $n$ en base $b$, on ajoute un $0$ à la droite de cette écriture.  \n",
    "À quelle opération cela correspond-il ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Si $\\qquad n = x_{k} b^{k} + x_{k-1} b^{k-1} + \\cdots + x_{1} b + x_{0}$  \n",
    "$\\text{alors } \\,b \\, n = \n",
    "x_{k} b^{k+1} + x_{k-1} b^{k} + \\cdots + x_{1} b^{2} + x_{0}b + 0$ .  \n",
    "**L'ajout d'un $0$ à droite de l'écriture revient donc à multiplier par la base $b$.**  \n",
    "\n",
    "**En $\\texttt{Python}$, une opération de décalage des bits.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0b1010'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = 0b101\n",
    "a = a<<1\n",
    "bin(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Pour ajouter des entiers écrits en binaire**, on procède comme en base $10$, en n'oubliant pas les retenues.  \n",
    "\n",
    "Il suffit de se rappeler le résultat des additions suivantes pour pouvoir poser toutes les additions : $\\,0_{2} + 0_{2} = 0_{2} \\qquad ; \\qquad 0_{2} + 1_{2} = 1_{2} + 0_{2} = 1_{2} \\qquad ; \\qquad 1_{2} + 1_{2} = 10_{2} \\qquad ;$  \n",
    "$\\,1_{2} + 1_{2} + 1_{2} = 11_{2}$.  \n",
    "\n",
    "> Poser les additions suivantes (comme à l'école élémentaire !), sans traduire les entiers dans la base\n",
    "dix.  \n",
    "$S_1 = 1011_{2} + 111011_{2}  \\qquad ; \\qquad S_2 = 110111_{2} + 111000_{2}$.  \n",
    "Vérifier avec une instruction telle que $\\texttt{bin}(\\texttt{int}('1011',2)+\\texttt{int}('111011',2))$ ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0b1000110'"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(int('1011',2)+int('111011',2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style media=\"screen\" type=\"text/css\">\n",
       "    .entete {\n",
       "        color: blue;\n",
       "    }\n",
       "    .bloc {\n",
       "        color: #f80;\n",
       "    }\n",
       "    .comment {\n",
       "        color: gray;\n",
       "    }\n",
       "    .indt {\n",
       "        padding-left: 1cm;\n",
       "        border-left: dotted 1px black;\n",
       "    }\n",
       "</style>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%html\n",
    "<style media=\"screen\" type=\"text/css\">\n",
    "    .entete {\n",
    "        color: blue;\n",
    "    }\n",
    "    .bloc {\n",
    "        color: #f80;\n",
    "    }\n",
    "    .comment {\n",
    "        color: gray;\n",
    "    }\n",
    "    .indt {\n",
    "        padding-left: 1cm;\n",
    "        border-left: dotted 1px black;\n",
    "    }\n",
    "</style>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Addition de deux entiers naturels représentés en binaire  sur $n$ bits  \n",
    "L'algorithme suivant n'est rien d'autre que l'addition telle qu'on l'a apprise à l'école, c'est à dire posée.\n",
    "Cet algorithme naı̈f nécessite de répéter $n$ fois les opérations \"retenue\" et \"reste\".  \n",
    "\n",
    "<table style=\"line-height:17.4545px;border-collapse:collapse;border-color:rgb(136,136,136);border-width:1px\" cellspacing=\"0\" bordercolor=\"#888\" border=\"1\" bgcolor=\"white\">\n",
    "<tbody>\n",
    "<tr>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$a_i$</td>\n",
    "<td style=\"text-align:center;width:37.1818px;height:16.1818px\">$b_i$</td>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$r$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">Retenue&nbsp;</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">Reste&nbsp;</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:37.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$0$</td>    \n",
    "</tr>\n",
    "<tr>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:37.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$1$</td>    \n",
    "</tr>\n",
    "<tr>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:37.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$1$</td>    \n",
    "</tr>\n",
    "<tr>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:37.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$0$</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:37.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$1$</td>    \n",
    "</tr>\n",
    "<tr>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:37.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$0$</td>    \n",
    "</tr>\n",
    "<tr>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:37.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$0$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$0$</td>    \n",
    "</tr>\n",
    "<tr>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:37.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:36.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$1$</td>\n",
    "<td style=\"text-align:center;width:61.1818px;height:16.1818px\">$1$</td>    \n",
    "</tr>\n",
    "</tbody>\n",
    "</table>\n",
    "</center>\n",
    "</td>\n",
    "</tr>\n",
    "</tbody>\n",
    "</table>\n",
    "\n",
    "<div style=\"background-color:#f0f0fa;\">\n",
    "<div class=\"comment\">#Définir la fonction Addition(a, b)</div>\n",
    "<div class=\"entete\">Addition(a, b) :</div>\n",
    "<div class=\"indt comment\">\"\"\"str -> str</div>\n",
    "<div class=\"indt comment\">hypothese : les chaînes en binaire, $a=a_{n-1}a_{n-2}\\cdots a_0$   et  $b=b_{n-1}b_{n-2}\\cdots b_0$</div>\n",
    "<div class=\"indt comment\">retourne la chaîne en binaire $c = c_nc_{n-1}c_{n-2}\\cdots c_0$ représentant la somme $c=a+b$</div>\n",
    "<div class=\"indt comment\">\"\"\"</div>    \n",
    "<div class=\"indt\">$r \\longleftarrow 0$</div>\n",
    "<div class=\"indt entete\">Pour $i$ allant de $0$ à $n-1$ faire :</div>\n",
    "<div class=\"indt\"><div class=\"indt\">$r = \\texttt{retenue}(a_i + b_i + r)$</div></div>\n",
    "<div class=\"indt\"><div class=\"indt\">$c_i = \\texttt{reste}(a_i + b_i + r)$</div></div>\n",
    "<div class=\"indt\"><div class=\"indt comment\"># Fin du bloc Pour</div></div>\n",
    "<div class=\"indt\">$c_n \\longleftarrow r$</div>\n",
    "<div class=\"indt\">$\\texttt{renvoyer}(c_n c_{n-1} \\cdots c_0 )$</div>\n",
    "</div>\n",
    "\n",
    "**En sommant deux représentations sur $n$ bits, on peut avoir besoin de $n+1$ bits pour représenter\n",
    "le résultat tel que le bit de poids fort soit non nul.** \n",
    "\n",
    "Par exemple $11_{2} + 01_{2} = 100_{2}$ . Dans ce cas, on dira que le résultat est sur $n$ bits, le $n + 1$ ième bit étant appelé la retenue (*carry*).  \n",
    "\n",
    "Par exemple le résultat sur $2$ bits de $11_{2} + 01_{2}$ est $00_{2}$ avec une retenue $r = 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Pour aller plus loin :**  \n",
    "> Algorithme d'addition : TP $\\,\\texttt{Python}$ <a href =\"http://lycee.lagrave.free.fr/nsi/numerisation/ISN_TP_addition_binaire.pdf\"  target=\"blank\">addition binaire</a>\n",
    "\n",
    "> Voir aussi le <a href=\"https://sites.google.com/site/sciencesdunumerique/algorithmique/Addition\" target=\"_blank\">lien avec une *fonction booléenne*</a> à trois arguments. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Multiplication de deux entiers naturels représentés en binaire  sur $n$ bits   \n",
    "En binaire, la multiplication est encore plus simple puisqu'elle repose uniquement sur des décalages et des\n",
    "additions.  \n",
    "En effet $\\,11_{2} \\times 1_{2} = 11_{2}$, $\\,11_{2} \\times 10_{2} = 110_{2}$  \n",
    "Ainsi : $\\, 11_{2} \\times 11_{2} = 11_{2} \\times 1_{2} + 11_{2} \\times 10_{2} = 11_{2} + 110_{2} = 1001_{2}$ (on retrouve bien $3 \\times 3 = 9$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "La multiplication se fait en formant un **produit partiel pour chaque digit du multiplicateur** (seuls les bits non nuls donneront un résultat non nul). Lorsque le bit du multiplicateur est nul, le produit partiel est nul, lorsqu'il vaut un, le produit partiel est constitué du multiplicande décalé du nombre de positions égal au poids du bit du multiplicateur.\n",
    "\n",
    "\n",
    "<table border=\"0\"><tbody><tr><td></td><td></td><td>$0$</td><td>$1$</td><td>$0$</td><td>$1$</td><td>multiplicande</td></tr><tr><td>$\\times$</td><td></td><td>$0$</td><td>$0$</td><td>$1$</td><td>$0$</td><td>multiplicateur</td></tr><tr><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td></td></tr><tr><td></td><td></td><td>$0$</td><td>$0$</td><td>$0$</td><td>$0$</td></tr><tr><td></td><td>$0$</td><td>$1$</td><td>$0$</td><td>$1$</td><td></td><td></td></tr><tr><td>$0$</td><td>$0$</td><td>$0$</td><td>$0$</td><td></td><td></td></tr><tr><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td></td></tr><tr><td></td><td>$0$</td><td>$1$</td><td>$0$</td><td>$1$</td><td>$0$</td><td></td></tr></tbody></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Le **nombre de bits requis** pour représenter le produit de deux entiers naturels en binaire est égal à la\n",
    "somme du nombre de bits des opérandes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Dépassements lors des calculs**  \n",
    "Que se passe-t-il lorsque le résultat d'un calcul est supérieur à la valeur maximale que l'on peut stocker avec le type de donnée utilisé ? **le résultat du calcul est faux**  \n",
    "\n",
    "<table>\n",
    "<tbody><tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"></span>\n",
    "</td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">171\n",
    "</td></tr><tr><td>+</td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "</td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">+ 205\n",
    "</td></tr><tr><td class=\"res\">=</td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px; padding-top : 16px;\">\n",
    "<input type=\"button\" value=\"1\" style=\"background-color : red; color : white\"><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span>\n",
    "</td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px;\">= 120\n",
    "</td></tr></tbody></table>\n",
    "\n",
    "Le bit additionnel produit lors du calcul ne peut pas être stocké et est donc tout simplement perdu : le résultat du calcul est donc limité aux $8$ bits de poids faible du résultat de l'addition et, par conséquent, faux. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Représentation binaire d'un entier relatif   \n",
    "**Le binaire signé** : Représentation signe-valeur absolue.  \n",
    "Nous avons vu que le codage des entiers naturels par une série de bits se fait simplement en prenant\n",
    "l'écriture binaire... <a href=\"http://lycee.lagrave.free.fr/nsi/numerisation/Codage_binaire_nombres_beamer.pdf\" target=\"_blank\">quid des entiers négatifs ?</a> La plus élémentaire, jamais utilisée en pratique, consiste à\n",
    "utiliser l'un des bits (le premier) pour représenter le signe. Si l'on prend l'exemple d'un octet, on a alors un bit de signe et sept bits pour coder la valeur absolue (un nombre indépendamment de son signe).\n",
    "\n",
    "*Exemple :* Sur $8$ bits on peut représenter des nombres signés de $-127$ à $+127$.  \n",
    "Lorsque le bit le plus à gauche est un $0$, le nombre est positif $\\, 0 \\,1 1 1 1 1 1 1$.  \n",
    "Ici le résultat est $+127$ comme en binaire pur.  \n",
    "Lorsque le bit le plus à gauche est un $1$, le nombre est négatif $\\, 1 \\,1 1 1 1 1 1 1$.  \n",
    "Ici le résultat est $-128$.\n",
    "\n",
    "<table width=\"100%\"><tbody><tr>\n",
    "<td>\n",
    "    <div class=\"calcul\">\n",
    "        <b>Opposé de l'opposé d'un nombre</b><br><br>\n",
    "        <table class=\"multiplication\">\n",
    "            <tbody><tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "            <input type=\"button\" value=\"0\" style=\"color : red\"><script>document.write(passiveRegister(7, 42))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">+42\n",
    "            </td></tr><tr><td></td><td style=\"padding : 8px; padding-left : 16px;text-align : left;\">&nbsp;<span class=\"green\"><b>⬇</b></span> <span class=\"green\">inversion</span>\n",
    "            </td></tr><tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "            <input type=\"button\" value=\"1\" style=\"color : red\"><script>document.write(passiveRegister(7, 42))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">-42\n",
    "            </td></tr><tr><td></td><td style=\"padding : 8px; padding-left : 16px;text-align : left;\">&nbsp;<span class=\"green\"><b>⬇</b></span> <span class=\"green\">inversion</span>\n",
    "            </td></tr><tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "            <input type=\"button\" value=\"0\" style=\"color : red\"><script>document.write(passiveRegister(7, 42))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">+42\n",
    "        </td></tr></tbody></table>\n",
    "        <span>-(-a) = a</span>\n",
    "    </div>\n",
    "</td><td height=\"100%\">\n",
    "    <div class=\"calcul\">\n",
    "        <b>Somme d'un nombre et de son opposé</b><br><br>\n",
    "        <table class=\"multiplication\">\n",
    "            <tbody><tr><td></td><td style=\"padding : 16px;\">\n",
    "            <input type=\"button\" value=\"0\" style=\"color : red\"><script>document.write(passiveRegister(7, 42))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding : 16px;\">+42\n",
    "            </td></tr><tr><td>+</td><td style=\"padding : 16px;\">\n",
    "            <input type=\"button\" value=\"1\" style=\"color : red\"><script>document.write(passiveRegister(7, 42))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding : 16px;\">+ (-42)\n",
    "            </td></tr><tr><td class=\"res\">=</td><td class=\"res\" style=\"padding : 16px;\">\n",
    "            <input type=\"button\" value=\"1\" style=\"color : red\"><script>document.write(passiveRegister(7, 84))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding : 16px;\">= -84\n",
    "        </td></tr></tbody></table>\n",
    "        <span>a + (-a) != 0</span>\n",
    "    </div>\n",
    "</td></tr></tbody></table>\n",
    "<div class=\"calcul\">\n",
    "<center><b>représentation(s) de zéro</b><br><br>\n",
    "<input type=\"button\" value=\"0\" style=\"color : red\"><script>document.write(passiveRegister(7, 0))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span>&nbsp;&nbsp;&nbsp;&nbsp;<input type=\"button\" value=\"1\" style=\"color : red\"><script>document.write(passiveRegister(7, 0))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span><br><br>\n",
    "On a donc 2 représentations possibles de 0.</center>\n",
    "</div>\n",
    "\n",
    "* **L'inconvénient c'est que le zéro a deux représentations $00000000 \\quad \\text{ et } 10000000$**    \n",
    "* Lors des calculs, ce bit de signe ne peut être considéré tel quel par la machine mais doit faire l'objet d'un traitement particulier sous peine de conduire à des résultats plutôt surprenants, $\\ldots 6_{10} + -6_{10} = -12_{10}$   \n",
    "C'est pour remédier à ces problèmes que l'on utilise la notation en **complément à deux**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Complément à 2  \n",
    "Les nombres positifs sont représentés comme attendu, en revanche les nombres négatifs sont obtenus de la manière suivante :\n",
    "- On inverse les bits de l'écriture binaire de sa valeur absolue (opération binaire NON), on fait ce qu'on appelle le complément à $1$ ;   \n",
    "- On ajoute $1$ au résultat (les dépassements sont ignorés).  \n",
    "\n",
    "Cette opération correspond au calcul de $2^n -\\left|x\\right|$, où $n$ est la longueur de la représentation et $\\left|x\\right|$ la valeur absolue du nombre à coder.  \n",
    "Ainsi $-1$ s'écrit comme $256-1=255=11111111_{2}$ , pour les nombres sur $8$ bits.  \n",
    "\n",
    "Ceci est à l'origine du nom de cette opération : \"complément à $2$ puissance $n$\", quasi-systématiquement\n",
    "tronqué en \"complément à $2$\".  \n",
    "*La même opération effectuée sur un nombre négatif donne le nombre positif de départ: $2^n - \\left(2^n -x\\right) = x$.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Pour coder $(−4)$ :  \n",
    "* On prend le nombre positif $4$ : $\\, 00000100$  \n",
    "* On inverse les bits : $\\qquad \\quad \\, \\, \\, 11111011$  \n",
    "* On ajoute $1$ : $\\qquad \\qquad \\quad \\, \\, \\; 11111100$  \n",
    "\n",
    "Le bit de signe est automatiquement mis à $1$ par l'opération d'inversion. On peut vérifier que cette fois\n",
    "l'opération $3$ + $(-4)$ se fait sans erreur :  \n",
    "\n",
    "$\\, \\,\\,\\,00000011$  \n",
    "$+ 11111100$\n",
    "\n",
    "$=\\!\\!11111111$  \n",
    "\n",
    "<table class=\"multiplication\">\n",
    "            <tbody><tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"></span>\n",
    "            </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$+ 43$\n",
    "            </td></tr><tr><td></td><td style=\"padding : 8px; padding-left : 16px; padding-right : 16px;text-align : center;\"><span class=\"green\"><b>⬇</b></span> <span class=\"green\">inversion</span> <span class=\"green\"><b>⬇</b></span>\n",
    "            </td></tr><tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">\n",
    "            </td></tr><tr><td>+</td><td style=\"padding : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "            </td><td style=\"padding : 16px;\"><span class=\"green\"><b>$+ 1$</b></span>\n",
    "            </td></tr><tr><td class=\"res\">=</td><td class=\"res\" style=\"padding : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "            </td><td style=\"padding : 16px;\">$\\rightarrow\\,$ <span class=\"green\"><b>$- 43$</b></span>\n",
    "        </td></tr></tbody></table>\n",
    "        \n",
    "**Le résultat de l'addition usuelle de nombres représentés en complément à deux est le codage en complément à deux du résultat de l'addition des nombres**. Ainsi les calculs peuvent s'enchaîner naturellement.  \n",
    "*Le complément à deux de $11111111$ est $\\,00000001$ soit $1$ en décimal, donc $11111111 = (-1)$ en décimal.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<table width=\"100%\"><tbody><tr>\n",
    "<td rowspan=\"2\" width=\"50%\">\n",
    "    <div class=\"calcul\">\n",
    "        <b>Opposé de l'opposé d'un nombre</b><br><br>\n",
    "        <table class=\"multiplication\">\n",
    "            <tbody><tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">+42\n",
    "            </td></tr><tr><td></td><td style=\"padding : 8px; padding-left : 16px; padding-right : 16px;text-align : center;\"><span class=\"green\"><b>⬇</b></span> <span class=\"green\">inversion</span> <span class=\"green\"><b>⬇</b></span>\n",
    "            </td></tr><tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "            </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">\n",
    "            </td></tr><tr><td>+</td><td style=\"padding : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "            </td><td style=\"padding : 16px;\"><span class=\"green\"><b>+ 1</b></span>\n",
    "            </td></tr><tr><td class=\"res\">=</td><td class=\"res\" style=\"padding : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding : 16px;\">-› <b>-42</b>\n",
    "            </td></tr><tr><td></td><td style=\"padding : 8px; padding-left : 16px; padding-right : 16px;text-align : center;\"><span class=\"green\"><b>⬇</b></span> <span class=\"green\">inversion</span> <span class=\"green\"><b>⬇</b></span>\n",
    "            </td></tr><tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "            </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">\n",
    "            </td></tr><tr><td>+</td><td style=\"padding : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "            </td><td style=\"padding : 16px;\"><span class=\"green\"><b>+ 1</b></span>\n",
    "            </td></tr><tr><td class=\"res\">=</td><td class=\"res\" style=\"padding : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding : 16px;\">-› <b>+42</b>\n",
    "        </td></tr></tbody></table>\n",
    "        <div class=\"remarque\">\n",
    "            <span class=\"red\">$-(-a) = a$</span>\n",
    "        </div>\n",
    "    </div>\n",
    "</td><td>\n",
    "    <div class=\"calcul\">\n",
    "        <b>Somme d'un nombre et de son opposé</b><br><br>\n",
    "        <table class=\"multiplication\">\n",
    "            <tbody><tr><td></td><td style=\"padding : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding : 16px;\">+42\n",
    "            </td></tr><tr><td>+</td><td style=\"padding : 16px;\">\n",
    "            <span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding : 16px;\">+ (-42)\n",
    "            </td></tr><tr><td class=\"res\">=</td><td class=\"res\" style=\"padding : 16px;\">\n",
    "            <input type=\"button\" value=\"1\" style=\"background-color : red; color : white\"><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding : 16px;\">= 0\n",
    "            </td></tr><tr><td></td><td style=\"padding : 8px; padding-left : 16px;text-align : left;\">&nbsp;<span class=\"green\"><b>⬇</b></span>\n",
    "        </td></tr></tbody></table>\n",
    "        <span class=\"red\">le \"$1$\" produit par le dépassement lors du calcul n'est pas pris en compte</span>\n",
    "        <div class=\"remarque\">\n",
    "            <span class=\"red\">$a + (-a) = 0$</span>\n",
    "        </div>\n",
    "    </div>\n",
    "</td></tr><tr><td><div class=\"calcul\">\n",
    "<center><b>représentation(s) de zéro</b><br><br>\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span><br>\n",
    "une seule représentation de 0</center>\n",
    "</div>\n",
    "</td></tr></tbody></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<div style=\"background-color:#f0f0fa;\">\n",
    "Plus généralement, avec des mots de $n$ bits, on écrit $2^n$ entiers relatifs compris entre $-2^{n-1}$ et $\\,2^{n-1}-1$ :  \n",
    "    \n",
    "* un entier relatif $x$ positif ou nul compris entre $0$ et $\\,2^{n-1}-1$ est représenté par l'entier naturel $x$ compris entre $0$ et $\\,2^{n-1}-1$  ;  \n",
    "* un entier relatif $x$ strictement négatif compris entre $-2^{n-1}$ et $\\,-1$ est représenté par l'entier naturel $x + 2^n$ compris entre $2^{n-1}$ et $2^n - 1$.\n",
    "</div>\n",
    "\n",
    "> Comment coderiez-vous l'entier $-60_{10}$ sur un octet par la méthode du complément à $2$ ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Sur un octet, la représentation binaire signée de $\\, -60 = 11000100_{2}$ est la même que la représentation binaire non-signée de $256-60=196$\n",
    "\n",
    "\n",
    "$11000100$ Le nombre $+60_{10}$ est codé par l'octet  :\n",
    "$00111100$. Afin d'obtenir facilement le complément à $2$ de ce nombre, et, donc, le codage binaire de son\n",
    "opposé, il suffit de recopier les bits de droite à gauche jusqu’au premier \"$1$\" inclus, puis de continuer en\n",
    "inversant cette fois les bits restants."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'111100'"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def naturel2bin(d,nb=0):\n",
    "    \"\"\"int-> str\n",
    "    hypothese : d nombre entier positif ou nul en décimal\n",
    "    retourne la conversion de d en une chaîne binaire de longueur nb (complète à gauche par des zéros)\"\"\"\n",
    "    return bin(d)[2:].zfill(nb)\n",
    " \n",
    "# naturel2bin(60,8)  # affiche: \"00111100\" \n",
    "naturel2bin(60)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'111111000100'"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def relatif2bin(d,nb=0):\n",
    "    \"\"\"int-> str\n",
    "    hypothese : d nombre entier relatif en décimal\n",
    "    retourne la conversion de d en une chaîne binaire de longuer nb\"\"\"\n",
    "    if d >= 0 : return naturel2bin(d,nb)\n",
    "    else :      return naturel2bin(2**nb-abs(d),nb)\n",
    "\n",
    "relatif2bin(-60,12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "De même, sur un octet, la représentation binaire signée de $\\, -91 = 10100101_{2}$ est la même que la représentation binaire non-signée de $256-91=165$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-3"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bin2decs(C):\n",
    "    \"\"\"str -> int\n",
    "    hypothese : C est une chaîne binaire signée de longueur quelconque\n",
    "    retourne la conversion de C en un nombre entier signé\"\"\"\n",
    "    #Si 1er chiffre '0' => le résultat sera positif ; Sinon 1er chiffre '1' => le résultat sera négatif\n",
    "    if C[0]==\"0\": return int(C,2)\n",
    "    else:         return int(C,2)-(1<<len(C))\n",
    " \n",
    "#bin2decs(\"111110100101\") \n",
    "bin2decs(\"10100101\")\n",
    "bin2decs(\"1101\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(256, 256)"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1<<8,int('100000000',2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Dépassements lors des calculs**  \n",
    "Que se passe-t-il lorsque le résultat d'un calcul est supérieur à la valeur maximale que l'on peut stocker avec le type de donnée utilisé ?\n",
    "\n",
    "*encore une fois, le résultat du calcul est* **faux**\n",
    "\n",
    "<table>    \n",
    "<tbody><tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "</td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$45$\n",
    "</td></tr><tr><td>+</td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span>\n",
    "</td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$+ 100$\n",
    "</td></tr><tr><td class=\"res\">=</td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px; padding-top : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "</td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px;\">= <span class=\"red\"><b>$-111$</b></span>\n",
    "</td></tr></tbody></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Dépassement de capacité**  \n",
    "En représentation en complément à deux sur $n$ bits, l'addition de deux entiers $x$ et $y$ peut produire un entier qui sort de la plage représentable. On appelle ceci un dépassement de capacité (**overflow**).  \n",
    "\n",
    "* **Fait 1.** Si $x$ est négatif et $y$ est positif, $x + y$ appartient toujours à la plage représentable.  \n",
    "* **Fait 2.** Il ne peut y avoir dépassement de capacité que si $x$ et $y$ sont de même signe.  \n",
    "    *Règle :* il y a dépassement de capacité si et seulement si le bit de poids fort de $x + y$ est différent du bit de poids fort de $x$ (et donc de $y$).  \n",
    "\n",
    "Exemple sur $4$ bits :  \n",
    "<table>    \n",
    "<tbody><tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span>\n",
    "</td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$+ 4$\n",
    "</td></tr><tr><td>+</td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "</td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$+ 5$\n",
    "</td></tr><tr><td class=\"res\">=</td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px; padding-top : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "</td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px;\">= <span class=\"red\"><b>$-7$</b></span>\n",
    "</td></tr></tbody></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Retenue de sortie**  \n",
    "En représentation en complément à deux sur $n$ bits, on dit que l'addition de deux entiers $x$ et $y$ produit une retenue de sortie si l'addition des bits de poids forts de $x$ et de $y$ renvoie une retenue de sortie $(R)$ à $1$ .\n",
    "Exemple sur $4$ bits d'une addition qui engendre une retenue de sortie.    \n",
    "<table>    \n",
    "<tbody><tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span>\n",
    "</td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$- 4$\n",
    "</td></tr><tr><td>+</td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "</td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$+ 5$\n",
    "</td></tr><tr><td class=\"res\">=</td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px; padding-top : 16px;\"><input type=\"button\" value=\"1\" style=\"background-color : red; color : white\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "</td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px;\">= <span class=\"red\"><b>$+ 1$</b></span>\n",
    "</td></tr></tbody></table>\n",
    "\n",
    "**Attention : ce n'est pas parce qu'une addition provoque une retenue de sortie qu'il y a dépassement de capacité.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Le dépassement de capacité $(D)$ et la retenue de sortie $(R)$ sont deux choses disjointes**.  \n",
    "En effet, il peut exister les quatre cas de figure suivants :\n",
    "\n",
    "<table>    \n",
    "<tbody><tr><td>non $(D)$ et non $(R)$ :</td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td>non $(D)$ et $(R)$ :</td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td></tr>\n",
    "    <tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span>\n",
    "    </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$- 8$ </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "    </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$+ 6$ \n",
    "</td></tr><tr><td>+</td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "</td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$+ 2$ </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td>+</td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span>\n",
    "    </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$- 4$ \n",
    "</td></tr><tr><td class=\"res\">=</td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px; padding-top : 16px;\"><input type=\"button\" value=\"0\" style=\"background-color : red; color : white\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "</td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px;\">= <span class=\"red\"><b>$- 6$</b></span></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td class=\"res\">=</td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\"><input type=\"button\" value=\"1\" style=\"background-color : red; color : white\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "    </td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px;\">= <span class=\"red\"><b>$+ 2$</b></span>\n",
    "</td></tr></tbody></table>\n",
    "\n",
    "\n",
    "*Dépassements lors des calculs, le résultat est faux !*\n",
    "<table>    \n",
    "<tbody><tr><td>$\\phantom{non}$ $(D)$ et non $(R)$ :</td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(D)$ et $(R)$ :</td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td></tr>\n",
    "    <tr><td></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "    </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$+ 6$ </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "    </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$- 6$ \n",
    "</td></tr><tr><td>+</td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"></span>\n",
    "</td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$+ 7$ </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td>+</td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span>\n",
    "    </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">$- 8$ \n",
    "</td></tr><tr><td class=\"res\">=</td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px; padding-top : 16px;\"><input type=\"button\" value=\"0\" style=\"background-color : red; color : white\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span>\n",
    "</td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px;\">= <span class=\"red\"><b>$- 3$</b></span></td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td class=\"res\">=</td><td style=\"padding-left : 16px; padding-right : 16px;\"></td><td style=\"padding-left : 16px; padding-right : 16px;\"><input type=\"button\" value=\"1\" style=\"background-color : red; color : white\">\n",
    "<span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span>\n",
    "    </td><td class=\"res\" style=\"padding-left : 16px; padding-right : 16px;\">= <span class=\"red\"><b>$+ 2$</b></span>\n",
    "</td></tr></tbody></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<a href=\"http://www.courstechinfo.be/MathInfo/CalculsBinaires.html\" target=\"_blank\">Sur un octet</a>, il y a donc moyen de représenter\n",
    "\n",
    "* $128$ codes avec le bit de signe à $1$ ; ce sont $128$ nombres négatifs ( de $-1$ à $-128$)  \n",
    "* $128$ codes avec le bit de signe à $0$ ; le nombre $0$ et $127$ nombres positifs ( de $1$ à $+127$)\n",
    "\n",
    "l'intervalle de codage permis $\\left[-128~;~127\\right]$ est, par conséquent, asymétrique - le procédé permettant le codage d'une valeur négative de plus que le nombre de valeurs positives codables.\n",
    "\n",
    "<div style=\"margin-left: 20px; padding: 3px; background-color: #fFfCf8;\">\n",
    "\t\t\t\t<table style=\"border-width: 1px; border-style: solid; border-color: #333333;\" cellspacing=\"0\" cellpadding=\"0\" border=\"1\">\n",
    "\t\t\t\t\t<tbody><tr>\n",
    "\t\t\t\t\t\t<th colspan=\"4\" align=\"center\">Nombre de 8 bits</th>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<th>Lu en hexadécimal</th>\n",
    "\t\t\t\t\t\t<th>Lu en binaire</th>\n",
    "\t\t\t\t\t\t<th>Lu en décimal signé</th>\n",
    "\t\t\t\t\t\t<th class=\"NonSigne\">&nbsp;&nbsp;Lu en décimal non signé</th>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>7F </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>111 1111 </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>127 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">127 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>7E </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>111 1110 </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>126 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">126 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>... </td>\n",
    "\t\t\t\t\t\t<td style=\"border-color: #FF0000;\">... </td>\n",
    "\t\t\t\t\t\t<td style=\"border-color: #FF0000;\">... </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">... </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>10 </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>001 0000 </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>16 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">16 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>0F </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>000 1111 </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>15 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">15 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>0E </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>000 1110</td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>14 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">14 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>0D </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>000 1101 </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>13 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">13 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>0C </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>000 1100</td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>12 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">12 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>0B <p></p></td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>000 1011 </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>11 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">11 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>0A </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>000 1010</td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>10 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">10 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>09 </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>000 1001 </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>9 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">9 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>08 </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>000 1000</td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>8 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">8 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>... </td>\n",
    "\t\t\t\t\t\t<td style=\"border-color: #FF0000;\">... </td>\n",
    "\t\t\t\t\t\t<td style=\"border-color: #FF0000;\">... </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">... </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>02</td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>000 0010</td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>2</td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">2</td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>01</td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>000 0001 </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>1</td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">1</td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>00</td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">0</span>000 0000 </td>\n",
    "\t\t\t\t\t\t<td class=\"P\"><span class=\"Positif\">+</span>0</td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">0</td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>FF </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>111 1111 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>1 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">255 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>FE</td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>111 1110 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>2 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">254 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>FD</td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>111 1101 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>3 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">253 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>FC </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>111 1100 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>4 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">252 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>FB </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>111 1011 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>5 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">251 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>FA </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>111 1010 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>6 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">250 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>F9 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>111 1001 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>7 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">249 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>... </td>\n",
    "\t\t\t\t\t\t<td style=\"border-color: #0000FF;\">... </td>\n",
    "\t\t\t\t\t\t<td style=\"border-color: #0000FF;\">... </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">... </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>86 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>000 1001 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>122 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">134 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>85 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>000 0101 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>123 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">133 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>84 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>000 0100 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>124 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">132 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>83 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>000 0011 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>125 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">131 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>82 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>000 0010 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>126 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">130 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>81 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>000 0001 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>127 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">129 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t\t<tr align=\"center\">\n",
    "\t\t\t\t\t\t<td>80 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">1</span>000 0000 </td>\n",
    "\t\t\t\t\t\t<td class=\"N\"><span class=\"Negatif\">-</span>128 </td>\n",
    "\t\t\t\t\t\t<td class=\"NonSigne\">128 </td>\n",
    "\t\t\t\t\t</tr>\n",
    "\t\t\t\t</tbody></table>\n",
    "\t\t\t</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* Pour les nombres non signés, le nombre de bits requis pour représenter le produit est égal à la somme du nombre de bits des opérandes.\n",
    "*  Pour les nombres signés, il faut $1$ bit de moins que pour le cas non signé.\n",
    "\n",
    "| Représentation | Grandeur maximale ($N$ bits) | Produit maximal | Exemple avec $N$ = 3 bits |\n",
    "|:--------------:|:----------------------------:|:---------------:|:-------------------------:|\n",
    "| Non signée     | $2^N - 1$                    | Il faut $2N$ bits | Valeur max: $7$ ; Produit max: $49$ ($6$ bits) |\n",
    "\n",
    "$\\left(2^N - 1\\right)\\times\\left(2^N - 1\\right) = 2^{2N} - 2 \\times 2^N + 1$ ; Il faut $2N$ bits\n",
    "\n",
    "| Représentation | Grandeur maximale ($N$ bits) | Produit maximal | Exemple avec $N$ = 3 bits |\n",
    "|:--------------:|:----------------------------:|:---------------:|:-------------------------:|\n",
    "|Signée          | $- 2^{N-1}$                  | Il faut $2N - 1$ bits | Valeur max: $-4$ ; Produit max: $+16$ ($5$ bits) |\n",
    "\n",
    "$\\left(- 2^{N-1} \\right) \\times \\left(- 2^{N-1} \\right) = 2^{2N-2}$ ; Il faut $2N - 1$ bits "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Comment décodez-vous l'octet $\\, 10000001$ en base $10$ ?\n",
    "\n",
    "* $-127 \\quad $ Certes. Mais pourquoi pas $129$ en numération binaire positionnelle ?\n",
    "* $+1 \\qquad\\!$ Effectivement. Mais pourquoi pas $-1$ en représentation signe-valeur absolue ?\n",
    "* $+129 \\quad$ Bien sûr, bien sûr. Mais pourquoi pas $-127$ en codage par complément à $2$ ?\n",
    "* Aucune idée  \n",
    "  Et vous faites rudement bien car il est foncièrement impossible de décoder un octet si l'on ignore le codage qui a servi pour le créer. \n",
    "  \n",
    "En d'autres termes, un octet peut virtuellement coder n'importe quel entier ! C'est au processeur de connaître en permanence le type de codage qui a été utilisé pour coder les nombres qu'il manipule.\n",
    "\n",
    "**En programmation, cela revient à typer les variables manipulées par le programme**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "NR = valeur Non Représentable  \n",
    "\n",
    "<div style=\"text-align:center;\">\n",
    "<img src=\"./images/recap.jpg\" alt=\"unites\" width=\"60%\"/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Les bits en biais  \n",
    "**Représentation biaisée:**  \n",
    "Une autre possibilité de codage des entiers signés existe: la **représentation biaisée**, également appelée **représentation par excès**.  (*Codage par offset*)\n",
    "Celle-ci, très simple, consiste à considérer tout nombre binaire codé comme un entier non signé auquel on soustrait une constante, ou *biais*, définie selon le domaine de validité des entiers codés que l'on recherche."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Cette représentation est utilisée pour le codage des exposants des nombres flottants. Avec $k$ bits, cette représentation permet de représenter tous les entiers de l'intervalle $\\left[-2^{k-1} ~;~ 2^{k-1}-1\\right]$.  \n",
    "Chaque entier $n$ de cet intervalle est codé par le codage de $n + 2^{k-1}$ comme un entier positif (*l'ajout de cette constante donne le nom de codage par offset*).  \n",
    "Il consiste à représenter l'entier le plus négatif par $\\underbrace{000\\cdots 0}_{k \\text{bits}}$ et l'entier le plus positif par $\\underbrace{111\\cdots 1}_{k \\text{bits}}$.\n",
    "\n",
    "**Représentation biaisée (avec un biais de $4$) sur $3$ bits**\n",
    "<div style=\"text-align:center;\">\n",
    "<img src=\"./images/biased.png\" alt=\"unites\" width=\"60%\"/>\n",
    "    Codage par offset $\\qquad \\qquad  000 \\,\\, | \\,\\, 001 \\,\\, | \\,\\, 010 \\,\\, | \\,\\, 011 \\,\\, | \\,\\, 100 \\,\\, | \\,\\, 101 \\,\\, | \\,\\, 110 \\,\\, | \\,\\, 111$\n",
    "</div>\n",
    "\n",
    "**En codage par offset, l'entier $n = 0$ est toujours représenté par un $1$ sur le bit de poids fort et des zéros sinon.**  \n",
    "L'addition avec des représentations par offset nécessite un circuit différent de l'addition des représentations non signées."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Comparaison des représentations**\n",
    "\n",
    "<table cellspacing=\"0\" cellpadding=\"2\" border=\"1\" align=\"center\">\n",
    "  <tbody><tr>\n",
    "    <th>Représentation</th>\n",
    "    <th>Avantages</th>\n",
    "    <th>Inconvénients</th>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td>avec bit de signe</td>\n",
    "    <td>représentation naturelle<br>\n",
    "        intervalle symétrique<br>\n",
    "\tchangement de signe facile</td>\n",
    "    <td>$2$ représentations pour $0$<br>\n",
    "\tcomparaison difficile<br>\n",
    "\taddition difficile</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td>biaisée</td>\n",
    "    <td>comparaison facile<br>\n",
    "        véritable différence</td>\n",
    "    <td>représentation de $0$<br>\n",
    "        intervalle non symétrique<br>\n",
    "\taddition difficile</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td>en complément à $2$</td>\n",
    "    <td>représentation de $0$<br>\n",
    "        bit de signe<br>\n",
    "\tcomparaison facile<br>\n",
    "        addition et soustraction semblables</td>\n",
    "    <td>intervalle non symétrique</td>\n",
    "  </tr>\n",
    "</tbody></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "> Expliquez ce rêve étrange\n",
    "\n",
    "<div style=\"text-align:center;\">\n",
    "<img src=\"./images/cant_sleep.png\" alt=\"unites\" width=\"60%\"/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Dans une représentation en complément à deux sur $n$ bits, le successeur de $\\, 2^{n-1}-1\\, $ est égal à $\\, -2^{n-1}\\,$.  Dans ce rêve $\\, n=16$\n",
    "\n",
    "<div style=\"text-align:center;\">\n",
    "<img src=\"./images/repnbcirc.png\" alt=\"unites\" width=\"40%\"/>\n",
    "</div>\n",
    "Autrement dit, les entiers relatifs représentés par complémentation à deux sont pourvus d'une structure cyclique.\n",
    "<div style=\"text-align:center;\">\n",
    "<img src=\"./images/cycle1.png\" alt=\"unites\" width=\"40%\"/>\n",
    "\n",
    "<img src=\"./images/cycle2.png\" alt=\"unites\" width=\"40%\"/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Représentation des nombres à virgule   \n",
    "**Il existe deux formats de représentations des nombres à virgule :**\n",
    "* **Format virgule fixe** : Utilise par les premières machines, possède une partie 'entière' et une partie 'décimale' séparés par une virgule. La position de la virgule est fixe d'ou le nom.  \n",
    "*Exemple :* $54,25_{10}$ ; $10,001_{2}$ ; $A1,F0B_{16}$  \n",
    "* **Format virgule flottante** (actuellement sur machine)  \\, défini par : $\\, \\pm m . b^e$\n",
    "    * un signe $+$ ou $-$\n",
    "    * une mantisse $m$ (en virgule fixe)\n",
    "    * un exposant $e$ (un entier relatif)\n",
    "    * une base $b$ $(2,8,10,16,\\ldots)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Le format à virgule fixe**, est certainement le système de représentation des nombres réels le plus simple, on étend le système de numération en autorisant les puissances négatives de la base. un séparateur (la virgule, le point) à droite de l'unité (exposant $0$), marque la limite entre exposants positifs et négatifs. **Le nombre de chiffres des parties entières et fractionnaires est fixe**.\n",
    "\n",
    "Le codage à virgule fixe consiste à représenter un nombre à virgule en deux parties $\\rightarrow$ **codage en virgule fixe** **\"$n,m$\"**  où les entiers $n$ et $m$ sont fixés.\n",
    "1. sa *troncature*, sur $n$ bits ;\n",
    "2. sa *partie décimale*, sur $m$ bits.\n",
    "\n",
    "La *troncature* est codée en utilisant la représentation en complément à deux. Chaque bit de la partie décimale correspond à l'inverse d'une puissance de deux.\n",
    "\n",
    "Par exemple, si on utilise $8$ bits pour représenter un nombre, on peut choisir de placer la virgule entre le quatrième et le cinquième bit. Les huit bits $\\underbrace{b_3 b_2 b_1 b_0}_{} \\underbrace{d_1 d_2 d_3 d_4}_{}$ représenteront alors un nombre dont la **partie entière** est égale à $b_3 b_2 b_1 b_0$ et la **partie fractionnelle** à $d_1 d_2 d_3 d_4$ .  \n",
    "\n",
    "$0101,0110_{2}$  \n",
    "$= \\underbrace{0\\times2^3+1\\times2^2+0\\times2^1+1\\times2^0}_{} + \\underbrace{0\\times2^{-1}+1\\times2^{-2}+1\\times2^{-3}+0\\times2^{-4}}_{}$  \n",
    "$= \\qquad \\qquad \\quad 5 \\qquad \\qquad + \\quad 0,25 + 0,125 = 5,375$\n",
    "\n",
    "La représentation en virgule fixe est donc plus simplement une représentation entière mise à l’échelle par une puissance (le plus souvent négative) de $2$ :  \n",
    "$0101,0110_{2} =01010110 \\times 2^{-4} = 86 \\times 2^{-4} = 5,375$  \n",
    "\n",
    "Notez quand même que $256$ combinaisons s'avèrent un peu léger-léger afin de coder l'infinité des réels compris entre ces deux valeurs. La probabilité est donc immense qu'un réel ne puisse être exactement codé par huit petits bits."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Les nombres représentables en virgule fixe sont régulièrement espacés de $2^{-m}$\n",
    "\n",
    "Rappelons qu'un nombre décimal est un rationnel qui peut s'écrire sous la forme $\\dfrac{x}{10^N}$ où $x$ est un entier relatif, par exemple $\\dfrac{25}{4}$ est un nombre décimal car il peut aussi s'écrire $\\dfrac{625}{100}$ et son écriture décimale est $6, 25$.\n",
    "\n",
    "De la même façon, un **nombre dyadique** est un rationnel qui peut s'écrire sous la forme $\\dfrac{x}{2^N}$  où $x$ est un entier relatif  \n",
    "(*peut s'écrire sous forme de fraction avec pour dénominateur une puissance de deux*),  \n",
    "et son développement dyadique s'obtient en plaçant une virgule séparant les $N$ chiffres les plus à droite des autres.\n",
    "\n",
    "Par exemple, $\\dfrac{25}{4}$ est un nombre dyadique et son développement dyadique est $110, 01_{2}$.  \n",
    "En effet, $25 = 11001_{2}$ et $\\dfrac{25}{4} \\, (110, 01)_{2} = 1 \\times 2^2 + 1 \\times 2^1 + 0 \\times 2^0 \\quad + \\quad 0 \\times 2^{-1} + 1 \\times 2^{-2}$  \n",
    "On ne peut **représenter exactement** que des nombres dyadique, le nombre $0,1$ est un decimal en base $10$ mais pas en base $2$.  \n",
    "L'égalité entre nombres flottants n'a pour ainsi dire aucun sens puisque le développement dyadique d'un nombre décimal peut être infini :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0.1 + 0.2 == 0.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Decimal('0.1000000000000000055511151231257827021181583404541015625')"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#On peut connaitre la valeur précise qu'on manipule avec le module decimal de Python :\n",
    "import decimal\n",
    " \n",
    "decimal.Decimal.from_float(1.1)\n",
    "decimal.Decimal.from_float(1.1+1.1)\n",
    "decimal.Decimal.from_float(2.2)\n",
    "decimal.Decimal.from_float(1.1+1.1+1.1)\n",
    "decimal.Decimal.from_float(3.3)\n",
    "decimal.Decimal.from_float(0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Marge d'erreur** : quand on utilise le type $\\texttt{float}$, il est rarissime (hormis dans un but pédagogique) d'utiliser l'égalité de valeur $==$  \n",
    "On fera toujours intervenir une marge d'erreur (absolue ou relative).\n",
    "\n",
    "Das l'exemple ci-dessous, on choisit une marge d'erreur absolue en considérant que toute quantité inférieure ou égale à $10^{-10}$ est nulle :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "abs(0.1 + 0.2 - 0.3) <= 1e-10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<table class=\"liste\" style=\"background-color:#FFFF80\">\n",
    "    <tbody><tr><th>valeur</th><th>puissances<br>de 2</th><th>puissances<br>de 8</th><th>puissances<br>de 16\n",
    "    </th></tr><tr><td>1</td><td>2<sup>0</sup></td><td>8<sup>0</sup></td><td>16<sup>0</sup>\n",
    "    </td></tr><tr><td>2</td><td>2<sup>1</sup></td><td></td><td>\n",
    "    </td></tr><tr><td>4</td><td>2<sup>2</sup></td><td></td><td>\n",
    "    </td></tr><tr><td>8</td><td>2<sup>3</sup></td><td>8<sup>1</sup></td><td>\n",
    "    </td></tr><tr><td>16</td><td>2<sup>4</sup></td><td></td><td>16<sup>1</sup>\n",
    "    </td></tr><tr><td>32</td><td>2<sup>5</sup></td><td></td><td>\n",
    "    </td></tr><tr><td>64</td><td>2<sup>6</sup></td><td>8<sup>2</sup></td><td>\n",
    "    </td></tr><tr><td>128</td><td>2<sup>7</sup></td><td></td><td>\n",
    "    </td></tr><tr><td>256</td><td>2<sup>8</sup></td><td></td><td>16<sup>2</sup>\n",
    "    </td></tr><tr><td>512</td><td>2<sup>9</sup></td><td>8<sup>3</sup></td><td>\n",
    "    </td></tr><tr><td>1024</td><td>2<sup>10</sup></td><td></td><td>\n",
    "    </td></tr></tbody></table><br>\n",
    "    <table class=\"liste\" style=\"background-color:#FFFF80\">\n",
    "    <tbody><tr><th>valeur</th><th>puissances<br>de 2</th><th>puissances<br>de 8</th><th>puissances<br>de 16\n",
    "    </th></tr><tr><td>0.5</td><td>2<sup>-1</sup></td><td></td><td>\n",
    "    </td></tr><tr><td>0.25</td><td>2<sup>-2</sup></td><td></td><td>\n",
    "    </td></tr><tr><td>0.125</td><td>2<sup>-3</sup></td><td>8<sup>-1</sup></td><td>\n",
    "    </td></tr><tr><td>0.0625</td><td>2<sup>-4</sup></td><td></td><td>16<sup>-1</sup>\n",
    "    </td></tr><tr><td>0.03125</td><td>2<sup>-5</sup></td><td></td><td>\n",
    "    </td></tr><tr><td>0.015625</td><td>2<sup>-6</sup></td><td>8<sup>-2</sup></td><td>\n",
    "    </td></tr><tr><td>0.0078125</td><td>2<sup>-7</sup></td><td></td><td>\n",
    "    </td></tr><tr><td>0.00390625</td><td>2<sup>-8</sup></td><td></td><td>16<sup>-2</sup>\n",
    "    </td></tr><tr><td>0.001953125</td><td>2<sup>-9</sup></td><td>8<sup>-3</sup></td><td>\n",
    "    </td></tr></tbody></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Propriété du codage : signe par complément à $2$ sans modification du format**  \n",
    "<table>\n",
    "        <tbody><tr><td></td><td style=\"border-right : dashed red 2px; text-align : right\"><script>document.write(passiveRegister(4,2))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"></span></td><td style=\"text-align : left\"><script>document.write(passiveRegister(4,11))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"></span></td><td> +2,6875\n",
    "            </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">\n",
    "            </td></tr><tr><td></td><td style=\"padding : 8px; padding-left : 16px; padding-right : 16px;text-align : center;\" colspan=\"2\"><span class=\"green\"><b>⬇</b></span> <span class=\"green\">inversion</span> <span class=\"green\"><b>⬇</b></span>\n",
    "            </td></tr><tr><td></td><td style=\"border-right : dashed red 2px; text-align : right\"><script>document.write(passiveRegister(4,13))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span></td><td style=\"text-align : left\"><script>document.write(passiveRegister(4,4))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span>\n",
    "            </td><td style=\"padding-left : 16px; padding-right : 16px; padding-bottom : 16px;\">\n",
    "            </td></tr><tr><td style=\"padding : 16px;\">+</td><td style=\"border-right : dashed red 2px; text-align : right\"><script>document.write(passiveRegister(4,0))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span></td><td style=\"text-align : left\"><script>document.write(passiveRegister(4,1))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span></td><td>\n",
    "        </td></tr><tr><td class=\"res\" style=\"padding : 16px;\">=</td><td class=\"res\" style=\"border-right : dashed red 2px; text-align : right\"><script>document.write(passiveRegister(4,13))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span></td><td class=\"res\" style=\"text-align : left\"><script>document.write(passiveRegister(4,5))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span></td><td> -2,6875\n",
    "        </td></tr></tbody></table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "%%html\n",
    "<style media=\"screen\" type=\"text/css\">\n",
    "    .entete {\n",
    "        color: blue;\n",
    "    }\n",
    "    .bloc {\n",
    "        color: #f80;\n",
    "    }\n",
    "    .comment {\n",
    "        color: gray;\n",
    "    }\n",
    "    .indt {\n",
    "        padding-left: 1cm;\n",
    "        border-left: dotted 1px black;\n",
    "    }\n",
    "</style>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "La valeur décimale d'un nombre binaire $0,d_1d_2d_3 \\ldots d_n$ est donnée par : $\\dfrac{d_1}{2}+ \\dfrac{d_2}{4}+ \\dfrac{d_3}{8}+\\ldots+ \\dfrac{d_n}{2^n}$.  \n",
    "Pour convertir un nombre décimal à virgule en binaire, on distingue la partie entière du nombre et sa partie fractionnaire. Ensuite, on procède en deux étapes : on commence par convertir la partie entière comme d'habitude, puis on traite la partie fractionnaire avec l'algorithme suivant :  \n",
    "\n",
    "\n",
    "<div style=\"background-color:#f0f0fa;\">\n",
    "<div class=\"entete\">Tant que la partie fractionnaire n'est pas nulle :</div>\n",
    "<div class=\"indt\">> la multiplier par $2$</div>\n",
    "<div class=\"indt\">> garder la partie entière obtenue</div>\n",
    "<div class=\"indt\">> recommencer avec la nouvelle partie fractionnaire</div>\n",
    "<div class=\"comment\"># Fin du bloc Tant que</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Exemple :**   \n",
    "Convertir $6,625_{10}$ en binaire.  \n",
    "\n",
    "Codons d'abord la partie entière :  $\\,6_{10}=110_2$  \n",
    "\n",
    "* $0,625 \\times 2 = 1,250 \\rightarrow$ on garde $1$ et on continue avec $0,250$  \n",
    "* $0,250 \\times 2 = 0,50 \\rightarrow$ on garde $0$ et on continue avec $0,50$  \n",
    "* $0,50 \\times 2 = 1,0 \\rightarrow$ on garde $1$   \n",
    "* et on s'arrête car la partie fractionnaire est $0$  \n",
    "Finalement  $\\, 6,625_{10}=110,101_2$\n",
    "\n",
    "L'avantage d'une telle représentation est que les additions et les multiplications sont simples.  \n",
    "On additionne deux nombres en virgule fixe de la même manière que deux nombres entiers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Conversion de la base 10 vers la base 2**  \n",
    "<script>document.write(multiplicationsSuccessives(\"6,625\", 2));</script>\n",
    "<table><tbody><tr><td></td><td>6,625</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">6</span></td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">(110)<sub>2</sub></span></td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,625</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">1,25</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">1</span></td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,25</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">0,5</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">0</span></td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,5</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">1</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">1</span></td></tr><tr><td>&nbsp;</td></tr><tr><td colspan=\"4\" class=\"resultat\">(6,625)<sub>10</sub> = (110,101)<sub>2</sub></td></tr></tbody></table>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Il n'y a pas forcément de solution exacte dans le codage et le nombre de puissances négatives dépend des capacités de la machine et de la précision souhaitée.\n",
    "\n",
    "**Important : représentation de $(0,4)_{10}$ en base $2$**\n",
    "<table><tbody><tr><td></td><td>0,4</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">0</span>\n",
    "\n",
    "</td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,4</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">0,8</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">0</span>\n",
    "</td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,8</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">1,6</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">1</span>\n",
    "</td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,6</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">1,2</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">1</span>\n",
    "</td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,2</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">0,4</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">0</span>\n",
    "\n",
    "</td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,4</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">0,8</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">0</span>\n",
    "</td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,8</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">1,6</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">1</span>\n",
    "</td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,6</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">1,2</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">1</span>\n",
    "</td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,2</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">0,4</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">0</span>\n",
    "\n",
    "</td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,4</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">0,8</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">0</span>\n",
    "</td></tr><tr><td></td><td><span class=\"green\"><b>⬇</b></span></td></tr><tr><td></td><td><span class=\"red\">0,8</span></td></tr><tr><td style=\"text-align : left\">×</td><td>2</td></tr><tr><td colspan=\"2\" class=\"res\">1,6</td><td style=\"padding-left : 16px; padding-right : 16px;\"><span class=\"green\"><b>➡</b></span></td><td><span class=\"red\">1</span>\n",
    "</td></tr><tr><td colspan=\"2\">...</td></tr></tbody></table>\n",
    "\n",
    "$(0,4)_{10} = (0,0110\\quad 0110\\quad 0110\\ldots)_2$\n",
    "\n",
    "Sur cet exemple, on observe une séquence qui se répète indéfiniment. On en conclut donc qu'il n'est pas possible de représenter le nombre $\\,(0,4)_{10}$ en base $2$ avec un nombre fini de bits. **Ceci est également vrai pour de nombreuses valeurs autres que $0,4$**\n",
    "\n",
    "Bien entendu, ces erreurs sont propagées et éventuellement amplifiées lors des calculs :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.19999999999999998"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v = 0.3 - 0.1\n",
    "v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "La précision dépend de la position de la virgule : il faut connaître à l'avance (lors de l'écriture du programme) l'ordre de grandeur des nombres à manipuler afin de positionner au mieux la virgule.\n",
    "\n",
    "Exemples :  codage en virgule fixe **\"$4,4$\"**  \n",
    "\n",
    "<table>\n",
    "        <tbody><tr><td style=\"border-right : dashed red 2px; text-align : right\"><script>document.write(passiveRegister(4,0))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"></span></td><td style=\"text-align : left\"><script>document.write(passiveRegister(4,1))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span></td><td> 0,0625\n",
    "        </td></tr><tr><td style=\"border-right : dashed red 2px; text-align : right\"><script>document.write(passiveRegister(4,15))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"></span></td><td style=\"text-align : left\"><script>document.write(passiveRegister(4,15))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"></span></td><td> 15,9375\n",
    "        </td></tr></tbody></table>\n",
    "        \n",
    "        \n",
    "codage en virgule fixe **\"$1,7$\"**  \n",
    "\n",
    "<table>\n",
    "        <tbody><tr><td style=\"border-right : dashed red 2px; text-align : right\"><script>document.write(passiveRegister(1,0))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"></span></td><td style=\"text-align : left\"><script>document.write(passiveRegister(7,1))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"0\"><input type=\"button\" value=\"1\"></span></td><td> 0,0078125\n",
    "        </td></tr><tr><td style=\"border-right : dashed red 2px; text-align : right\"><script>document.write(passiveRegister(1,1))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"></span></td><td style=\"text-align : left\"><script>document.write(passiveRegister(7,127))</script><span style=\"white-space : nowrap;\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"><input type=\"button\" value=\"1\"></span></td><td> 1,9921875\n",
    "        </td></tr></tbody></table>\n",
    "\n",
    "Connaître à l'avance la précision nécessaire, et donc l'ordre de grandeur des nombres à manipuler, est un inconvénient majeur : ce type de connaissance a priori existe pour certaines applications, mais dans le cas général ce n'est pas le cas. Un autre inconvénnient de la virgule fixe, c'est qu'on ne peut pas représenter à la fois de très grands et de très petits nombres. Pour pallier à ce manque de flexibilité, le concept de virgule flottante a été introduit. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### La norme IEEE-754  \n",
    "Cette norme est actuellement le standard pour la représentation des nombres à virgule flottante en binaire.  \n",
    "Nous allons en donner une description (incomplète) pour une architecture $64$ bits.  \n",
    "\n",
    "Un nombre dyadique non nul possède une représentation normalisée de la forme $\\,\\pm (1, b_1 \\cdots b_k )_{2} \\times 2^e$, où $e$ est un entier relatif.  \n",
    "Par exemple,  \n",
    "$\\,6, 25 = (110, 01)_{2}$ a pour représentation normalisée $\\,(1, 1001)_{2} \\times 2^2$  \n",
    "$\\,-0, 375 =-(0, 011)_{2}$ la représentation normalisée $\\, \\quad  -(1, 1)_{2} \\times 2^{-2}$ \n",
    "\n",
    "La suite de bits $\\,b_1 \\cdots b_k$  est appelée la **mantisse** du nombre, et la puissance de $2$, l'**exposant**.  \n",
    "Dans cette norme, les nombres dyadiques sont codés sur $64$ bits en réservant :  \n",
    "- $1$ bit pour le signe ;  \n",
    "- $11$ bits pour l'exposant ;  \n",
    "- $52$ bits pour la mantisse.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "L'exposant est un entier relatif, mais pour permettre une comparaison plus aisée des nombres flottants, il n'est\n",
    "pas codé suivant la technique de complément à deux mais suivant la technique du décalage : l'exposant $e$ est\n",
    "représenté en machine par l'entier positif $e' = e + 2^{10}- 1$.  \n",
    "Un entier naturel codé sur $11$ bits est compris entre $0$ et $2^{11}- 1$ donc a priori : $\\,0 \\leqslant e' \\leqslant  2^{11}- 1 \\iff 1 - 2^{10} \\leqslant  e \\leqslant 2^{10}$  \n",
    "soit $\\,- 1023 \\leqslant e \\leqslant 1024$.  \n",
    "Cependant, les valeurs extrêmes ($e'= 0$ et $e' = 2^{11}- 1$) sont réservées à la <a href=\"https://iut-info.univ-reims.fr/users/nourrit/codages/page12.html\" target=\"_blank\">représentation de certaines valeurs\n",
    "particulières</a>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Conclusion  \n",
    "<a href=\"https://iut-info.univ-reims.fr/users/nourrit/codages/\" target=\"_blank\">Ce qu'il faut savoir faire</a> à l'issue de cette partie :  \n",
    "* Passer de la représentation d'une base dans une autre.\n",
    "* Décrire l'algorithme de division en cascade.\n",
    "* Évaluer le nombre de bits nécessaires à l'écriture en base $2$ d'un entier, de la somme ou du produit de deux nombres entiers.\n",
    "* Utiliser le complément à $2$.\n",
    "* Calculer sur quelques exemples la représentation de nombres réels"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Diaporama",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  },
  "rise": {
   "autolaunch": true,
   "enable_chalkboard": true,
   "scroll": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}