\section{Représentation des nombres entiers}



\begin{Def}[Principe de la numération de position]
\index{Principe de la numérotation de position}
Il consiste à choisir une base $b$ de numération, et $b$ symboles qui constitueront les chiffres dans la représentation d'un entier positif en base $b$.
Celle-ci s'écrira alors
$$n=n_{p}b^p+n_{p-1}b^{p-1}+\cdots+n_{1}b^1+n_{0}$$ 

Cette écriture est abrégée en ${\left(\overline{n_{p}n_{p-1}\ldots n_{0}}\right)}_{b}$.
\end{Def}

En informatique, on utilise couramment les bases 2, 8 et 16.





L'algorithme pour obtenir la représentation en base $b$ d'un entier est :

\begin{enumerate}
 \item Effectuer la division euclidienne de cet entier par $b$, division qui donne un premier quotient et un premier reste.
 \item Le quotient est à sont tour divisé par $b$ pour donner un second quotient et un second reste, et ainsi de suite jusqu'à obtenir un quotient nul.
\item Les restes successifs (tous strictement inférieurs à $b$), et en commençant par le dernier, constituent la représentation en base $b$ de l'entier donné.
\end{enumerate}

\begin{Exo}
Donner la représentation de 23 en base 2.
\end{Exo}



\begin{Exo}[Numération, changements de base]
\begin{enumerate}
\item Chercher les entiers dont le carré a, en représentation décimale, 
le même chiffre pour les dizaines et les unités. 
\item On pose $a=2p-1$, $b=2p+1$, $c=2p+3$; trouver l'entier $p$ de manière que $a^2+b^2+c^2$ soit de la forme $\sur{xxxx}_{10}$.
\item L'entier $n$ s'écrit $\sur{341}_{10}$ et $\sur{2331}_a$. Trouver $a$.
\item Montrer que, dans toute base $b$ supérieure ou égale à 3, l'entier qui s'écrit $\sur{11211}_b$ n'est pas  premier.
\item Soit $n\geqslant 7$. Donner l'écriture de $(n+1)^4$ en base $n$.
\end{enumerate}
\end{Exo}



\begin{Exo}[Développement décimal]
On considère le nombre réel $x$ dont le dé\-ve\-lop\-pe\-ment décimal s'écrit $x=0,012\ 345\ 679\ 012\ 345\ 679\ \ldots\ \ldots\ \ldots$ (la séquence $012\ 345\ 679$ est reproduite indéfiniment). Ce développement décimal est périodique, de période 9.
\begin{enumerate}
\item Montrer que $x$
vérifie une équation de la forme $10^kx=n+x$, où $k$ et $n$ sont
des entiers à déterminer. En résolvant cette équation,
montrer que $x$ est un nombre rationnel, et le mettre sous la forme
$x= \fr pq$ , où $p$ et $q$ sont premiers entre eux.
\item Appliquer
la même méthode au ``nombre" $y$ dont le développement
décimal est $y= 0,999\ 999\ 999\ 999\ \ldots$ (périodique de période
1). Quelle conclusion peut-on en tirer?
\item Démontrer que tout nombre réel dont le développement
décimal est fini ou périodique à partir d'un certain rang
est un nombre rationnel.
\item Réciproquement, on se propose de démontrer que le
développement décimal de tout nombre rationnel est fini ou
périodique à partir d'un certain rang. Pour cela, on
considère un rationnel $x=\fr pq$ , avec $q>0$, $p\in
\Z$, $p$ et $q$ premiers entre eux, et on étudiera successivement
les cas suivants:
\begin{itemize}
\item $x$ est entier (c'est à dire $q=1$).
\item $x$ est rationnel non entier, et $q$ est premier avec 10 (On
pourra montrer que, si $q$ est premier avec 10, il existe un entier
$k$, non nul, tel que $10^k\equiv 1\ [q]$).
\item $x$ est rationnel non entier, mais $q$ n'est pas premier avec 10.
\end{itemize}
\end{enumerate}

\end{Exo}



\section{Arithmétique en informatique}


La plupart des langages de programmation utilisés en informatique disposent d'un type de données pour représenter ce que les informaticiens appellent les entiers signés (les entiers relatifs) et possèdent des opérateurs pour effectuer les calculs classiques sur ces nombres.

\subsection{Division entière}

En C ou java, par exemple, le symbole $/$ représente le quotient dans la \og division entière\fg{} et le symbole $\%$ représente ce que les informaticiens appellent improprement le modulo (le reste dans leur \og division entière\fg{} ).


Pour des raisons pratiques de réalisation des micro-circuits des processeurs qui réalisent ces opérations, la \og division entière\fg{} ne donne pas exactement le même résultat que la division euclidienne.



Considérons par exemple les 4 cas possibles de division euclidienne de $a$ par $b$ lorsque $|a|=29$ et $|b|=7$ (en n'oubliant pas que le reste d'une division euclidienne ne peut être que positif)


\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$a$ & $b$ & division euclidienne & $q$ & $r$ & $a/b$ & $a\%b$ \\ \hline
$29$ &$7$ & $29=4\times 7+1$ & $4$ & $1$ & $4$ & $1$ \\ \hline
$29$ &$-7$ & $29=(-4)\times (-7)+1$ & $-4$ & $1$ & $-4$ & $1$ \\ \hline
$-29$ &$7$ & $-29=(-5)\times 7+6$ & $-5$ & $6$ & $-4$ & $-1$ \\ \hline
$-29$ &$-7$ & $-29=5\times (-7)+6$ & $5$ & $6$ & $4$ & $-1$ \\ \hline
\end{tabular}
\end{center}



Autrement dit, mathématiquement, le quotient est positif lorsque les deux nombres ont le même signe et le reste est toujours positif, et, pour que le reste soit toujours positif, le quotient peut ne pas être le quotient des valeurs absolues.


Informatiquement, le \og quotient\fg{} est positif lorsque les nombres ont le même signe, le \og reste\fg{} a le signe du dividende, et la valeur absolue du \og quotient\fg{} est toujours le quotient des valeurs absolues.


Dans les applications de calcul arithmétique, par exemple un calcul de PGCD, ce n'est pas gênant parce que les restes \og informatiques\fg{} sont congrus aux restes mathématiques modulo la valeur absolue du
diviseur, et qu'il ne s'agit alors que du choix d'un représentant de la classe concernée (addition et multiplication étant compatibles avec la congruence modulo $n$).

Mais il faut quand même savoir que l'on peut obtenir un \og reste\fg{} négatif et prendre ses dispositions le cas échéant...


\subsection{Arithmétique modulo $2^n$}

 

Les calculs sur les entiers, dans un ordinateur, se font dans $\Z/2^n\Z$, où $n$ est le nombre de bits utilisés dans la représentation de ces nombres.


Dans la plupart des microprocesseurs, les entiers sont représentés sur 64 bits, les calculs se font donc dans $\Z/2^{64}\Z$.


Disposer d'entiers signés ou d'entiers non signés est uniquement une question de choix du représentant dans les classes d'équivalence, mais
la représentation physique est la même.


Comme il nous est difficile de représenter ici la liste compléte de tous ces entiers, nous allons illustrer ce propos en supposant que les entiers sont représentés sur 4 bits.
Pour des mots de 4 bits, il y a alors 16 entiers représentables : (a.s.= arithmétique signée, a.n.s. = arithmétique non signée)

\begin{center}\begin{tabular}{|c|c|c|c|} \hline
code binaire & & a.s. & a.n.s. \\ \hline
0000 & interprété par & 0 & 0 \\ \hline
0001 & interprété par & 1 & 1 \\ \hline
0010 & interprété par & 2 & 2 \\ \hline
0011 & interprété par & 3 & 3 \\ \hline
0100 & interprété par & 4 & 4 \\ \hline
0101 & interprété par & 5 & 5 \\ \hline
0110 & interprété par & 6 & 6 \\ \hline
0111 & interprété par & 7 & 7 \\ \hline
1000 & interprété par & 8 & -8 \\ \hline
1001 & interprété par & 9 & -7 \\ \hline
1010 & interprété par & 10 & -6 \\ \hline
1011 & interprété par & 11 & -5 \\ \hline
1100 & interprété par & 12 & -4 \\ \hline
1101 & interprété par & 13 & -3 \\ \hline
1110 & interprété par & 14 & -2 \\ \hline
1111 & interprété par & 15 & -1 \\ \hline
\end{tabular}\end{center}\vskip 10pt


Pourquoi ce choix ? Pourquoi ne pas avoir, en a.s., représenté les entiers dans l'ordre croissant de 0000 (-8) à 1111 (7)?

\begin{itemize}
 \item Tout simplement pour des raisons d'efficacité : 0 doit toujours être représenté par le code \og nul\fg{} 0000.
\item Ensuite, il faut pouvoir comparer efficacement ces codes entre eux, ce qui explique que 0 doit être suivi de 1, arithmétique signée ou pas.
\end{itemize}

\bigskip

Ces principes ont ainsi conduit à placer les codes interprétés comme entiers négatifs après ceux qui représentent les entiers positifs.


Par ailleurs, on s'aperçoit que, de cette manière, les codes des entiers
négatifs commencent tous par 1.
On parle improprement de \og bit de signe\fg{}\index{bit de signe}: s'il s'agissait d'un véritable bit de signe, le code 1001 devrait être celui de -1, or c'est celui de -7.
Mais il n'en reste pas moins que tous les entiers négatifs commencent par 1).


Ainsi, il est facile de déduire la comparaison signée de la comparaison non signée : les codes qui commencent par 1 sont \og plus petits\fg{} que ceux qui commencent par 0, et, s'ils commencent par le même bit, c'est la comparaison non signée qui peut être utilisée.





Pour l'addition et la soustraction, les opérations et les tests de validité des résultats sont les mêmes en arithmétique signée et non signée.
Pour la multiplication, l'instruction n'est pas la même (le dépassement de capacité doit être ignoré en a.s. dans le dernier exemple).

\begin{Ex}

Premiers résultats, corrects :

 \begin{center}
\begin{tabular}{r | r | r}
Opération binaire & Entiers non signés & Entiers signés \\
\hline
0010 & 2 & 2 \\
\underline{+ 1001} & \underline{+ 9} & \underline{+(-7)} \\
1011 & 11 & (-5) \\
\end{tabular}
 \end{center}
\end{Ex}


\begin{Ex}
 Un résultat correct en arithmétique non \break signée, et négatif en arithmétique signée, mais correct modulo 16 (-6 et 10 sont dans la même classe, mais cette classe  est représentée par 10 en a.n.s. et par -6 en a.s.) :
\begin{center}
\begin{tabular}{r | r | r}
Opération binaire & Entiers non signés & Entiers signés \\
\hline
0100 & 4 & 4 \\
\underline{+ 0110} & \underline{+ 6} & \underline{+ 6} \\
1010 & 10 & (-6) \\
\end{tabular}
\end{center}
\end{Ex}


\begin{Ex}
Un dépassement de capacité dans les deux cas, mais  le résultat est correct modulo 16 : les classes de 21, de -11 et de 5 sont les mêmes :
 \begin{center}
\begin{tabular}{r | r | r}
Opération binaire & Entiers non signés & Entiers signés \\
\hline
1100 & 12 & (-4) \\
\underline{+ 1001} & \underline{+ 9} & \underline{+(-7)} \\
(1)0101 & 5 & 5 \\
\end{tabular}
 \end{center}
Le résultat (correct modulo 16) est disponible dans tous les cas, les \og dépassement de capacité\fg{} et \og résultat négatif\fg{} sont signalés par le positionnement d'un bit dans un registre spécial.
\end{Ex}




\begin{Ex}
Un résultat correct en a.n.s., résultat négatif en a.s., mais correct modulo 16 :
 \begin{center}
\begin{tabular}{r | r | r}
Opération binaire & Entiers non signés & Entiers signés \\
\hline
0101 & 5 & 5 \\
\underline{$\times$ 0010} & \underline{$\times$ 2} &
\underline{$\times$ 2} \\ 1010 & 10 & (-6) \\
\end{tabular}
 \end{center}
\end{Ex}


\begin{Ex}
Dépassement de capacité dans les deux cas, résultat négatif en a.s., mais résultat correct modulo 16, compte tenu du choix des représentants dans les deux arithmétiques:
 \begin{center}
\begin{tabular}{r | r | r}
Opération binaire & Entiers non signés & Entiers signés \\
\hline
0101 & 5 & 5 \\
\sou{$\times$ 0110} & \sou{$\times$ 6} & \sou{$\times$ 6} \\
(1)1110 & 14 & (-2) \\
\end{tabular} 
 \end{center}
\end{Ex}




\begin{Ex}
Dépassement de capacité dans les deux cas,  résultat correct en a.s., correct modulo 16 en a.n.s.
 \begin{center}
\begin{tabular}{r | r | r}
Opération binaire & Entiers non signés & Entiers signés \\
\hline
1101 & 13 & (-3) \\
\sou{$\times$ 1110} & \sou{$\times$ 14} & \sou{$\times$
(-2)} \\ (1011)0110 & 6 & 6 \\
\end{tabular} 
\end{center}
\end{Ex}
\centerline{\x{Fin du Chapitre}}