\vfill\eject
\section{Bit-tracking}


\subsection{bit-à-bit}

Le langage C permet de réaliser des opérations
sur les bits des mots. Un exemple élégant et instructif 
de proprammation bit-à-bit est donné par le calcul 
du poids de Hamming d'un entier de la figure \ref{HW}.


\begin{figure}[h]
\begin{multicols}2
\lstinputlisting[style=gcc]{bitwise/wt.c}
\columnbreak
\lstinputlisting[style=gcc]{bitwise/wtfor.c}
\end{multicols}
\caption{\label{HW}Deux versions du calcul du poids 
de Hamming d'entier non signé, d'aprés \cite{PW60} 
Peter Wegner (1960).}
\end{figure}

\begin{exercice}
Montrer que l'algorithme \gcc{wt} calcule bien le poids de $z$. C'est
l'exercice 2.09 de la seconde édition du {\sl The C Programming Language}
par  Kernighan and Rithie.
\end{exercice}

Il est souvent utile de retrouver $v$ à partir de $2^v$,
ce calcul du logarithme à base deux peut se faire de plusieurs
fa\c cons. La méthode proposée dans Fig.~\ref{MAGIC} illustre
un mécanisme proche de ce que l'on pourrait rencontrer
dans la progammation bitboard des moteurs du jeu des échecs.

\begin{figure}
\lstinputlisting[style=gcc, firstline=1,lastline=20 ]{bitwise/pi.c}
\caption{\label{MAGIC}Une utilisation possible d'un fait
arithmétique pour calculer le logarithme à base 2 de $2^v$ : 2
est une racine primitive modulo 67.
}
\end{figure}

\begin{exercice}
Proposer différentes fonctions \gcc{int log( ullong x)} 
qui retourne le logarithme à base 2 d'un entier de 64
bit sachant que ce dernier de poids 1. 
\end{exercice}

\vfill\eject

\begin{exercice}
\par\noindent
\begin{multicols}{2}
\begin{lstlisting}[  style=gcc, numbers=left]
int pb( ullong z ) {
int r = 0;
while ( z ) {
      r+= (z % 2);
      z = z / 2;
}
return r;
}
\end{lstlisting}

\columnbreak
Soit $m$ un entier positif.
On note $I(\gamma)$ le nombre d'itérations de la
boucle de la fonction \gcc{int pb(ullong z)} pour une
instance $\gamma$ du paramètre $z$, la valeur
moyenne sur l'ensemble des entiers de $m$ bits :
$$
	\tilde I(m) = \frac1{2^m} \sum_{\gamma=0}^{2^m-1} I(\gamma).
$$
\end{multicols}
\begin{enumerate}
\item Quel est l'ensemble des instances défavorables.
\item Quel est ensemble des entiers $\gamma$ tels que $I(\gamma) = 1$ ?. 
\item Décrire l'ensemble des entiers $\gamma$ tels
que $I(\gamma) = k$. 
\item Préciser le cardinal de cet ensemble. 
\item Montrer par récurrence que $\sum_{k=0}^{m-1} k2^k = 2^m(m-2)+2$.
\item Donner une formule du nombre moyen d'itération.
\item Déterminer le nombre réel $\alpha$ tel que $\tilde I(m) \sim \alpha m$.
\end{enumerate}
\end{exercice}


\begin{exercice}
Reprendre les questions de l'exercice précédent 
avec l'algorithme de la figure Fig.~\ref{HW}.
\end{exercice}

\begin{exercice}
Ecrire un algorithme récursif pour
calculer le poids binaire d'un entier
$z$ de taille $2m$ basé sur la relation :
$$
 \wt( z ) = \wt(x) + \wt(y), \quad z = y2^m + x
$$
Reprendre les questions de l'exercice précédent
avec ce nouvel algorithme. 
\end{exercice}

\subsection{retour sur traces}


\subsection{permutation}

Un sous-ensemble de $\{0,1,\ldots,n-1\}$ avec $n<64$ 
peut être représenté par un mot binaire de 64 bits. La
boucle qui suit extrait les éléments de la partie
représentée par le mot binaire $x$: 

\begin{lstlisting}[style=gcc]
while ( x ) {
      t  = x;
      x &= (x-1);
      t ^= x;
      i  = Log( t );
}
\end{lstlisting}

Cette approche est utilisée dans la procédure
de backtracking Fig.~\ref{PERMUT} pour énumérer
les permutations de $\{0,1,\ldots,n-1\}$. Objet
que l'on représente par un tableau de $n$ valeurs
distinctes.

\begin{figure}
\lstinputlisting[style=gcc, firstline=20,title=permutation]{bitwise/pi.c}
\caption{\label{PERMUT}Un algorithme de backtracking pour énumérer
les permutations de $\{0,1,\ldots,n-1\}$.
}
\end{figure}

\subsection{les huit reines}

Le problème des $n$ dames consiste à trouver
toutes les configurations de $n$ dames placées
sur échiquier $n\times n$ sans que deux dames
ne soient sur une même rangée, colonne ou
diagonale.
 


\begin{figure}
\lstinputlisting[style=gcc, firstline=3,lastline=23]{bitwise/qbit.c}
\caption{\label{QUEEN}Un algorithme de backtracking pour énumérer
les solutions du problème des  $n$ dames.
}
\end{figure}


\subsection{cavalier d'Euler}

