TD 10 C++: Polymorphisme, Bit hacks.

Rappels


Exercice 1: Poymorphisme, encore un peu

Note: j'ai beaucoup aimé la page sur le polymorphisme de cplusplus.com. à lire si vous êtes perdu. Mais attention, l'exo 1 ci-dessous est encore plus tordu! Bonne chance.
  1. Entrez dans un fichier 1.1.txt ce que le code ci-dessous (sur 2 colonnes) affiche quand il est exécuté.

    screenshot d'un code à examiner: colonne de gauche screenshot d'un code à examiner: colonne de droite
    Exemple de contenu de 1.1.txt:
    ABCDEF
    JKLMN
    OPQRS
    TUVWX
    YZ012
    Vérifiez avec le script 1.1.sh:
    bash 1.1.sh
    RENDU: 1.1.txt

  2. Que se passe-t'il si on ajoute la ligne suivante a la fin de main()?
    ((B*)(&a))->X();
    RENDU: 1.2.txt avec une description très très succinte de ce qui se passe, et une mini explication.


Exercice 2: Un exemple acceptable de polymorphisme

  1. Teléchargez l'archive 2.tar.gz et extrayez son contenu:
    tar xf 2.tar.gz
    Télechargez et complétez les fichier 2.1.h et 2.1.cc.
    Testez votre code avec:
    make 2.1
    Indice important: vous aurez sans doute une erreur parlant de non-virtual destructor. Pour la réparer, vous devrez retoucher 2.1.h mais attention vous n'avez que le droit d'y ajouter une seule ligne!

    RENDU: 2.1.h et 2.1.cc

  2. Copiez 2.1.h et 2.1.cc dans des fichiers 2.2.h et 2.2.cc.
    Ajoutez une classe Circle, dont le nom (donné par Name()) sera Circle, en suivant le même principe que StraightSquare.
    Pour construire un cercle, on donne typiquement les coordonées (x, y) de son centre, et son rayon.

    Testez votre code avec:
    make 2.2
    RENDU: 2.2.h et 2.2.cc

  3. Copiez 2.2.h et 2.2.cc dans des fichiers 2.3.h et 2.3.cc.
    Ajoutez la fonction polymorphique Perimeter() à la classe Shape. Elle devra renvoyer 0 pour la classe de base. Bien sûr, vous devrez l'implementer dans les classes dérivées.
    Ajoutez la chaine: , perimeter=<perimeter>" à la fonction Description() (attention à la virgule avant perimeter=!).

    Testez votre code avec:
    make 2.3
    RENDU: 2.3.h et 2.3.cc

Exercice 3: Bit hacks

  1. Complétez le fichier 3.h (également inclus ci-dessous). Pas la peine de faire un 3.cc: saisissez le code directement dans le .h.
    typedef unsigned int uint32;
    
    typedef unsigned short uint16;
    typedef unsigned char uint8;
    
    // If you want to perform some precomputation when the program starts,
    // you can put it here: Init() will be called by 3.test.cc and by 3.bench.cc.
    void Init() {
    }
    
    // Returns 1 if the bit #bit of x is 1, 0 otherwise.
    // NOTE: bit #0 is the bit of lowest weight (i.e. x modulo 2).
    inline int GetBitOf(int bit, uint32 x) {
        return -1;
    }
    
    // Set bit #bit of "x" to the given value (0 if value=false, 1 if value=true)
    inline void SetBitOf(int bit, bool value, uint32* x) {
        return -1;
    }
    
    // Return x with all of its bits inversed: 1 becomes 0, 0 becomes 1.
    inline uint32 NegateBits(uint32 x) {
        return -1;
    }
    
    // Return the number of bits of x that are set.
    inline int BitWeight(uint32 x) {
        return -1;
    }
    
    // Return the bits of x, "flipped": bit #0 becomes bit #31,
    // bit #1 becomes bit #30, and so on.
    inline uint32 FlipBits(uint32 x) {
        return -1;
    }
    Indications
    Testez votre code avec 3.tar.gz:
    rm 3.tar.gz; wget --no-cache http://fabien.viger.free.fr/cpp/td10/3.tar.gz && tar xf 3.tar.gz
    g++ -std=c++11 -O2 3.test.cc && ./a.out
    RENDU: 3.h

  2. (*) Améliorez la performance de vos fonctions!
    Vous pouvez obtenir le temps de calcul moyen de vos fonctions avec 3.bench.cc:
    g++ -std=c++11 -O2 3.bench.cc && ./a.out
    ATTENTION! Votre code devra toujours être valide (cf test ci-dessus).

    RENDU: 3.h (amelioré) Note: sur ma machine (Core i7-5600U CPU @ 2.60GHz), j'arrive à descendre en dessous de 1ns pour chacune de ces opérations.

Note: la recherche "bit hacks" sur Google permet d'arriver sur une page sympa avec plein de recettes ésoteriques. Ne pompez pas sans comprendre, sinon je me fâche!