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

Leave a Comment