TP4 : Opérations binaires, Graphes de Bruijn, Représentation des flottants

Opérations binaires

1.

$x, y ∈ ℕ$

int x; int y;
x^=y;
y^=x;
x^=y;

• x^=y; : tous les bits où $x$ et $y$ diffèrent sont mis à $1$, les autres à $0$
• y^=x; : tous les bits où $y$ et “les bits non communs à $x$ et $y$” diffèrent sont mis à $1$, les autres à $0$ :
  • parmi les bits non communs à $x$ et $y$, les bits qui valent $0$ dans $y$ sont changés en $1$, les $1$ en $0$.
  • les autres sont inchangés
• x^=y; : tous les bits où $x$ et “les bits non communs à $x$ et $y$ switchés par rapport à $y$ (i.e les bits de $x$ non communs à $x$ et $y$)” diffèrent sont mis à $1$, les autres à $0$

⟹ $x$ et $y$ sont échangés.

2

$n ∈ ℕ$

int n;
n & (n-1);

Sur un exemple :

n   = 0111
n-1 = 0110
⇓     ____
      0110

n   = 0100
n-1 = 0011
⇓     ____
      0000

n   = 0110
n-1 = 0101
⇓     ____
      0100

⟹ met le bit égal à $1$ le plus à droite à 0 (le premier $1$ de poids faible à $0$).

3

$n ∈ ℕ$

int n;
for (int c = 0; n != 0; n &= (n-1)) {
  c++;
}

Avec ce qui précède :

⟹ compte le nombre de $1$ dans l’écriture en base 2 de $n$ (ou : $\lfloor \log_2 n \rfloor +1$)

4

void getBit(int n, int p){
  n = (n >> (p-1))&1;
}
void setBit(int n, int p){
  n |= (1 << (p-1));
}

void clearBit(int n, int p){
  n &= ~(1 << (p-1));
}

void toggleBit(int n, int p){
  n ^= (1 << (p-1));
}

Trouver le bit de poids le plus faible

1

Nombre de mots de longueur $n$ : $2^n$, donc une borne inférieure triviale est $n2^n$.

digraph graphname {
    00 -> 00 -> 01 -> 11 -> 11 -> 10 -> 00;
    10 -> 01 -> 10;

}

2 : graphe de Bruijn

digraph graphname {
    000 -> 000 -> 001 -> 010 -> 101 -> 010;
    101-> 011 -> 110 -> 101;
    111 -> 111 -> 110 -> 100 -> 000 -> 010 -> 100 -> 001->011->111;
}

digraph {
rankdir=LR;
000 -> 001;
001 -> 010;
010 -> 101;
101 -> 011;
011 -> 111;
111 -> 110;
110 -> 100;
100 -> 000;
}

Donc

$001011100$ convient

4. Séquence $s$

chaîne	index dans $s$
000	7
001	0
010	1
011	3
100	6
101	2
110	5
111	4

5. $e(j)$ et $j$

$j$	$e(j)$
0	001
1	010
2	101
3	011
4	111
5	110
6	100
7	000

$j$ est l’index de $e(j)$ dans $s$.

6. 1 de poids faible

$x\&(-x) = x\&(\lnot x +1)$ Or : le $+1$ change le zéro de poids le faible de $\lnot x$ en $1$, et laisse tous les autres bit invariants.

Donc tous les bits sont effacés, sauf le zéro de poids le faible de $\lnot x$ devenu un 1, i.e

le 1 de poids faible de $x$.

III. Virgule flottante