Manipuler de grands nombres

Résolu

Bonjour,

J'ai un exercice très long dans lequel on me demande de manipuler de grands entiers. Je n'arrive pas à faire le début de l'exercice et donc il est m'est impossible de faire le reste.

Je veux juste comprendre le début pour bien démarrer et ensuite je pourrais faire la suite (du moins j'espère).Votre aide me sera précieuse

On m'a donné ceci et il faut que je le complète :

tall_integer *ge_cree(void) {
  return NULL;
}

void free(tall_integer *e) {
}

tall_integer *set_bit(tall_integer *e, uint32_t x) {
  return NULL;
}

tall_integer *clr_bit(tall_integer *e, uint32_t x) {
  return NULL;
}

char get_bit(tall_integer *e, uint32_t x) {
  return 0;
}

int nb_bits(tall_integer *e) {
  return 0;
}

tall_integer *add(tall_integer *b, tall_integer *a) {
  return NULL;
}

tall_integer *shift(tall_integer *a, int nb_bits) {
  return NULL;
}

tall_integer *mul(tall_integer *b, tall_integer *a) {
  return NULL;
}

La question 1 concerne les fontions creer et liberer .

Pour creer, on me demande de créer dans le tas un grand entier de 32 bits débutant à la valeur 0 et de renvoyer un pointeur sur ce dernier. La fonction renvoie NULL si l'entier n'a pas pu être créé.

Pour liberer, c'est pour juste libérer l'entier créé. 

Mon problème surtout est qu'on me demande de définir moi même le type tall_integer et c'est ça mon problème et qui m'empêche d'avancer et comment créer un entier

Pour libérer je suppose que je dois juste mettre free(...)

...=entier à libéré

Moi je pensais en C il fallait juste écrire int entier et hop on a créé un entier mais vu les questions de mon exercice je me dis que ça doit pas être ça qu'on me demande...

27 réponses

  • Votes
  • Date
  • Date décroissante
Résumé de la discussion

Problème central : définir et manipuler un grand entier stocké sur le tas en C, avec des fonctions de création et de libération, et le type tall_integer à spécifier. Des réponses suggèrent d'allouer un bloc 32 bits initialisé à zéro et de renvoyer un pointeur, tandis que la libération nécessite d'appeler free sur le pointeur valide. Réponses utiles préconisent soit un typedef simple comme tall_int pour représenter un entier, soit une structure tamponnée avec data et size pour permettre une généralisation et une gestion mémoire sûre. L'exemple proposé prévoit l'utilisation de malloc et calloc, avec simplification possible en typedef uint32_t tall_int et, si nécessaire, une approche plus complexe utilisant une structure pour encapsuler les données.

Bobot (l’IA à votre service)
  1. Modérateur

    Bonjour,

    Le tas correspond à toutes les allocations dynamiques, donc faites par malloc (comme le souligne [Dal] dans #5) ou calloc. Tu as dû en entendre parler puisque tu connais la fonction free (celle-ci ne peut et ne doit s'utiliser que conjointement qu'avec une allocation dynamique réussie, c'est à dire telle que malloc (ou calloc) ait renvoyé un pointeur non NULL).

    Le tas est à mettre en opposition avec la pile, qui mémorise (notamment) toutes les variables locales et paramètres des fonctions en cours d'appel ainsi que la variable. 

    Pour ton exercice, un type se déclare avec typedef. Cela permet de créer un alias sur un type arbitraire (y compris s'il s'agit d'un type de pointeur). Si tu veux définir un type plus compliqué, tu peux définir un typedef sur une structure de donnée (struct) ou une union.

    Sous sa forme actuelle, l'exercice est un peu étrange car il suffit en effet d'écrire :

    typedef uint32_t tall_int;

    ... pour pouvoir poursuivre tout l'exercice. Et du coup, il n'y a pas vraiment de raison que mul, add (etc) retourne un tall_int * au lieu d'un tall_int.

    Si on veut rendre l'exercice plus pimenté, on peut imaginer définir une structure de donnée qui créer un buffer de taille arbitraire. Par contre ça rend l'exercice subitement beaucoup plus compliqué car typiquement tu ne peux plus vraiment utiliser directement les opérateurs natifs du C. La signature de ge_cree ne prévoit d'ailleurs pas de donner la taille dudit buffer. Mais en admettant que ce soit ce qu'on attende de toi, ça pourrait ressembler à :

    #include <stdint.h> // uint*_t
    #include <stdlib.h> // malloc, free
    #include <string.h> // calloc
    
    typedef struct tall_int {
        uint8_t * data;
        size_t size;
    } tall_int;
    
    tall_int * ge_alloc() {
        tall_int * ge = malloc(sizeof(tall_int));
        if (!ge) return NULL;
        ge->size = 10;  // entier sur 10 octets
        ge->data = (uint8_t *) calloc(sizeof(uint8_t), ge->size);
        if (!ge->data) {
            free(ge);
            return NULL;    
        }
        return ge;
    }
    
    void ge_free(tall_int * ge) {
        if (ge) {
            if (ge->data) free(ge->data);
            free(ge);
        }
    }
    
    int main() {
        tall_int * pge = ge_alloc();
        // ...
        ge_free(pge);
        return 0;
    }

    On pourrait également regretter que dans le squelette de ton exercice, la fonction free entre directement en collision avec la fonction de la librairie standard, et devrait donc probablement être renommée ge_free() ou ge_libere().

    Bonne chance

    1. Bonjour je voulais savoir si je passe de 32 a 1024 bit comment modifier les fonctions suivantes svp

      grand_entier_t *ge_set_bit(grand_entier_t *e, uint32_t x) {
           //e->size=4;
          e->data[x/32] |= (1 << (x % 32));
          return e;
      }
      
      
      grand_entier_t *ge_clr_bit(grand_entier_t *e, uint32_t x) {
           //e->size=4;
          e->data[x/32] &= ~(1 << (x% 32));
         
          return e;
      }
      
      
      char ge_get_bit(grand_entier_t *e, uint32_t x) {
         //e->size=4;
        return (e->data[x/32] >> (x%32)) & 1;// return (e->data[x/32] & (1 << (x % 32)))
        
      }
      
      int ge_nb_bits(grand_entier_t *e) {
        
        return e->size*32;
      }
      1. Contributeur

        C'est le cœur même de ton exercice.

    2. @all

      Merci pour  tout oh vos retours????,ça m'a beaucoup aide a avancer et a comprendre.

      Je pense que c'est bon,on a repondu a mes questions et de toute facon si j'en ai d'autres je créerai un autre sujet 

      Merci ????

      1. Ok merci je comprends.En fait je me suis dit vu que c'est 1 seul exo avec tous les codes que j'ai presente au debut de la conversation pas la peine de crer un autre sujet vu que en quelque sorte moi je devais implemanter toutes ces fonctions.

        Pour se faire il fallait que je definisse le type tall_int,la base sans cela je pouvais pas avancer

        merci j'ai regarde votre code,je l'analyse toujours jusqu'a ce que je comprends pour enfin donner une bonne implementation qui marche

        1. Modérateur

          Bonjour,

          @all

          Pour commencer, je pense que les personnes qui participent aux réponses n'inondent le fil de discussion en donnant de petits indices. Je conçois que ça a un intérêt pédagogique, et ce serait parfait dans une salle de cours. Je suis également d'accord sur le fait qu'on ne veut pas faire les exercices des étudiants à leur place. Le problème c'est que cela conduit à des fils de discussions complètement illisibles.

          Donc ce que je propose, c'est que vous ayez ce genre d'échanges via des message privés (sous réserve bien sûr que la personne qui a posé le problème ait un compte CCM, sinon ça va être compliqué de lui envoyer des messages privés).

          Il faut en particulier garder à l'esprit que d'autres internautes peuvent être intéressés par cette discussion mais ne seront pas intéressés par ces échanges.

          Retour au problème

          Raisonne octet par octet. Si tu sais faire une addition sur un octet et que tu sais propager une retenue, alors tu sauras faire une addition sur plusieurs octets.

          Il faut donc que cette fonction auxiliaire prenne deux uint8_t en paramètre, retourne leur addition et l'éventuelle retenue.

          Si on raisonne sur un bit, l'idée du xor que tu proposes est intéressante (voir message #38) :

          • 0 ^ 0 = 0
          • 0 ^ 1 = 1
          • 1 ^ 0 = 1
          • 1 ^ 1 = 0 (mais ici il ne faut pas oublier la retenue)

          Si on raisonne sur un octet par contre, il faut que l'on propage à chaque fois l'éventuelle retenue. Par exemple, en binaire, il faut s'assurer que 01111111 + 00000001 = 10000000.

          On s'aperçoit donc qu'il faut aussi être capable d'extraire le i-ème bit d'un octet. Cela a été évoqué dans plusieurs messages de cette discussion, tu extraies le i-ème bit d'un octet x en appliquant un ET logique avec un octet faisant office de masque, tel que dans cet octet, seul le i-ème bit vaut 1. Si après application de ce ET logique, le résultat est nul, alors c'est que le i-ème bit de x était nul, sinon il était égal à 1.

          uint8_t bit_5 = ((x & (i << 5)) != 0);

          Selon ce principe on peut écrire une fonction pour afficher un buffer en binaire.

          #include <stdio.h>
          #include <stdint.h>
          
          uint8_t get_ith_bit(const uint8_t * buffer, size_t bit_index) {
              uint8_t byte = buffer[bit_index / 8];
              return (byte & (1 << (bit_index % 8))) != 0;
          }                      
          
          void print_bin(const uint8_t * buffer, size_t size) {
              for (size_t i = 0; i < 8 * size; ++i) {
                  size_t i_rev = 8 * size - i - 1;
                  printf("%d", get_ith_bit(buffer, i_rev));
              }               
          }                   
                              
          int main() { 
              uint32_t x = 78;
              print_bin((const uint8_t *) &x, sizeof(x));
              printf("\n");
              return 0;       
          }

          Nommons x et y les deux opérandes (de type tall_int) de l'addition.

          Si maintenant, on est capable d'extraire le i-ème bit d'un buffer de taille arbitraire (ici depuis un buffer de 32 bits dans mon extrait de code précédent) alors on est capable :

          • d'extraire le i-ème bit de x
          • d'extraire le i-ème bit de y
          • de déduire avec xor quel sera le ième bit du résultat de l'addition (c'est ce que tu as proposé)
          • de déduire si le i-ème bit des de x et y vaut 1, s'il faut propager une retenue
          retenue = get_ith_bit(x, i) && get_ith_bit(y, i);
          

          Pour modifier le i-ème bit d'un buffer, on suit le même raisonnement que pour get_ith_bit, mais on modifie en place le buffer en lui appliquant un OU logique avec le masque adéquat.

          #include <stdio.h>
          #include <stdint.h>
          
          uint8_t get_ith_bit(const uint8_t * buffer, size_t bit_index) {
              uint8_t byte = buffer[bit_index / 8];
              return (byte & (1 << (bit_index % 8))) != 0;
          }                      
          
          void print_bin(const uint8_t * buffer, size_t size) {
              for (size_t i = 0; i < 8 * size; ++i) {
                  size_t i_rev = 8 * size - i - 1;
                  printf("%d", get_ith_bit(buffer, i_rev));
              }               
          }                   
          
          void set_ith_bit_to_0(uint8_t * buffer, size_t bit_index) {
              buffer[bit_index / 8] &= ~(1 << (bit_index % 8));
          }
          
          void set_ith_bit_to_1(uint8_t * buffer, size_t bit_index) {
              buffer[bit_index / 8] |= (1 << (bit_index % 8));
          }
          
          void set_ith_bit(uint8_t * buffer, size_t bit_index, uint8_t zero_or_one) {
              if (zero_or_one == 0) {
                  set_ith_bit_to_0(buffer, bit_index);
              } else {
                  set_ith_bit_to_1(buffer, bit_index);
              }
          }
                              
          int main() { 
              uint32_t x = 0;
              uint8_t * buffer = (uint8_t *) &x;
              print_bin(buffer, sizeof(x));
              printf("\n");
                   
              set_ith_bit(buffer, 7, 1);
              print_bin(buffer, sizeof(x));
              printf("\n");
                   
              set_ith_bit(buffer, 7, 0);
              print_bin(buffer, sizeof(x));
              printf("\n");
              return 0;
          }

          À toi ensuite d'écrire la boucle qui va réaliser l'addition. Pour faire simple je te conseille de considérer que x et y font la même taille en mémoire. Pour chaque valeur de i allant de 0 à 8 *sizeof(x), tu extrais le i-ème bit de x et y, fait le xor de ces deux opérandes, puis fait le xor de ce résultat avec la retenue, et en déduis le i-ème bit du résultat et son éventuelle retenue.

          Si quand tu arrives au dernier bit, il te reste une retenue a propagé, c'est que la somme des deux entiers dépasse la valeur maximale qu'il est impossible d'encoder dans ton tall_int. C'est un problème parfaitement "normal" qui se pose avec des entiers standards aussi (voir cette discussion). Je ne sais pas ce que ton exercice attend dans ce genre de situation, mais en C++ il faudrait lever une exception, et en C, probablement quitter le programme avec exit après avoir affiché un message d'erreur.

          Bonne chance

          1. Contributeur

            Je pensais que la charte décourageait l'aide via des message privés.

            Peut-être préférable, alors, de proposer de migrer la discussion vers un autre forum, plus approprié?  Une suggestion?

          2. Contributeur
            @yg_be

            Bonjour,

            Je m'oppose également que les MP servent et deviennent comme cela ne manquerait pas de se produire de moyen de manifester sa volonté affirmée de ne pas respecter les règles du forum ou à transposer à l'abri d'un anonymat bien permissif des interpellations irrespectueuses en vigueur sur les réseaux dits sociaux.
             

            C'est grâce à des échanges parfois confus mais oh combien instructifs que j'ai pu pour ma part progresser dans la découverte des arcanes de la programmation.
             

            Il est vrai que sur d'autres forums, le contrôle strict des dérives garantit que l'on ne divague pas au gré des velléités libertaires de certains visiteurs vindicatifs.

          3. Contributeur
            @georges97

            A titre personnel, je ne suis pas pour non plus. Je comprends aussi le souci de mamiemando en tant que modératrice de vouloir conserver une lisibilité aux fils, surtout que la question posée est intéressante et la réponse pourrait servir à d'autres à l'avenir. Il me semble qu'il y a des outils sur CCM pour faire cela : en plussant le contenu le plus pertinent pour qu'il remonte et se retrouve à proximité de la question.

            Cela dit, là le topic bascule en discussion hors sujet pour le pauvre Theo_0055... à savoir les "discussions visant à faire avancer la réflexion des PO doivent-elles être être traitées en MP ou pas" et peut-être que s'il faut avoir une discussion sur ce sujet là, il faudrait créer un autre topic dans un forum différent, ou en discuter en MP. J'invite mamiemando à ouvrir un topic sur un forum approprié et nous y inviter par MP si elle pense que cela mérite une discussion ouverte.

            si tu as des questions sur le code posté par mamiemando dans son message ou le code dont j'ai donné le lien sur Wikipedia ou sur un autre échange ou autre chose en lien avec ton sujet, n'hésite pas ignorer cette sous-discussion et à poster :-)

            as-tu vu mon MP ?

          4. Contributeur
            @[Dal]

            Tout à fait d'accord avec toi, Dal, sur la totalité de ton post. Je ne voulais surtout pas perturber ce fil assurément dense et un peu complexe. Désolé pour mon intrusion un peu intempestive, en souvenir de quelques MP agressifs de visiteurs heureusement disparus dans le cyber*espace.

            J'en profite pour exprimer tout le respect que j'ai pour le travail pédagogique accompli par mamiemando, que je suis fidèlement.

            Bonne soirée à tous

          5. Désolé de vous fatiguez tous avec mes questions.Merci pour ces explications.Je vais tout faire pour réussir à faire l'addition en utilsant vos pistes

            Meme si ça me semble un peu compliqué votre code

        2. Contributeur

          Je pense que Theo_0055 devrait être intéressé par ce code d'exemple présenté sur la page Wikipedia des opérateurs bit à bits du C :

          https://en.wikipedia.org/wiki/Bitwise_operations_in_C#Example:_a_simple_addition_program

          L'idée est d'identifier les cas où la retenue est nécessaire (c'est à dire là où à la même position tu as 1 et 1 à un moment donné dans la même colonne) avec l'opérateur &.

          L'exemple ne fonctionne que sur un type standard du C, mais cela devrait lui donner une idée de comment gérer les retenues au niveau du bit... si le but de l'exercice est vraiment de faire des opérations de ce type sans utiliser les opérateurs du C (j'ai présenté une méthode alternative utilisant les opérateurs du C et gérant la retenue pour des blocs entiers de uint32_t).

          Si, donc, tu dois bien travailler au niveau du bit, l'exemple de Wikipedia serait à extrapoler pour fonctionner avec un tableau de données du type choisi, en poursuivant la propagation des retenues et la poursuite des calculs sur les données dans les cellules suivantes du tableau.

          1.  Merci beaucoup ça m'a pris du temps avant de comprendre l'addition sur wikipédia

            Votre méthode pour gérer les retenues est facile a comprendre mais pour l'addition cela suppose que on dépasse la valeur maximale de uint32(INT32_MAX) mais si on additionne des nombres petits exemple 2 et2 on aura jamais le cas ou ça dépasse UINT32_MAX

            Merci je vais essayer

        3. Dans aucun contexte du moins je pense

          mon exo  a 3 grande parties

          1.Gerer la memoire des entiers(créé et libéré un grand entier)

          Partie que on m'a deja aidé

          2.Manipuler des bits

          Set bit=met a 1 le bit de position x dans le grand entier pointe par e et renvoie e

          clear bit=met  a 0 .....

          get bit doit me renvoyer ka valeur du bit de position x dans le grand entier pointe par e

          nb_bit doit me donner le nombre de bit du grand entier pointe par e

          3.On veut que je fais de l'arithmetique sur de grands nombres

          a savoir addition,multiplication et decalage

          En gros j'ai resume ce qu'on me demande de faire

          Vu que on m'a donne ça en devoir ça veut dire que je dois etre capable de le faire

          1. Contributeur

            Ah, il s'agit d'un devoir, c'est cela le contexte.

            N'est-ce pas un travail personnel, donc à faire seul?

            Je suggère de progresser avec des exercices plus simples, et de faire ce devoir ensuite.

          2. @yg_be

            C'est un devoir oui mais mon prof a dit vu que c'est un exi assez difficile,vois pouvez demander de l'aide

            Je voulais le faire seul mais vraiment je suis rester longtemps bloqué sans avancer du coup j'avais besoin d'aide vu que je dois le finir cette semaine 

          3. Contributeur
            @Theo_0055

            Tu as fait la partie 1?

            Tu as une question sur la partie 2?

          4. @yg_be

            mamiemando et Dal m'ont aidé pour cette partie à comprendre apres j'essaierais de le faire moi même

        4. Bon comme cela depend du resulatat a obtenir et de k methode choisi,le mieux donc est que je reviens sur mon exo de base.Peut etre si je le comprends je pourrais aussi le faire pour des petits entiers

          la fonction add ajoute au grand nombre pointe par b la valeur du grand nombre pointe par a donc *b=*b+*a et doit me renvoyer b


          Alors aidez moi a trouver une methode car moi a part utiliser le xor ou le et je sais pas comment m'y prendre.J'ai beau essayer j'arrive pas

          1. Contributeur

            Dans quel contexte fais-tu cela?

            Si tu veux progresser, peut-être préférable de faire d'abord des exercices à ton niveau.

        5. En vrai si ma fonction doit me renvoyer un int et comme c'est un exo sur de la manipulation de bit donc je me suis dit faut que je manipule les bits

          J'ai voulu comprendre cela d'abord avant d'attaquer ma fonction 

          tall_integer *add(tall_integer *b, tall_integer *a) 
          
          1. Contributeur

            Comment "manipuler des bits", cela dépend du résultat à obtenir, et de la méthode choisie pour y arriver.

        6. Si par exemple 
            10,5

          +  2,9

          ----------

          =  13, 4

          oui je sais faire

          1. Contributeur

            Il faut, évidemment, faire cela par étape, un chiffre à la fois.

          2. @yg_be

            Oui pour chaque colonne .Pour cette exemple 3 etape

            bein en faisant par exemple (a&b) ou (a xor b) ça traite deja les bits un a un ,etape par etape non?

            Donc je vois toujours pas la où vous voulez en venir,peut etre je suis aveugle il y a des trucs qui m'echappent

          3. Contributeur
            @Theo_0055

            Réfléchis à comment tu fais une addition de nombres en représentation décimale, et, surtout, comment tu gères les reports.

          4. @yg_be

            En addition décimal des qu'une addition de nombre est >=10 on a une retenue et cette retenue on l'ajoute a la colonne suivante,c'est comme çà qu'on gére les reports

            Esceque vous voulez que j'ecris une fonction qui additionne en décimal et puis je converti ce nombre en binaire?

            Si c'est le cas,je veux le faire aussi en raisonnant sur les bits 

          5. Contributeur
            @Theo_0055

            Tu n'as pas expliqué ce que tu voulais exactement obtenir.

            Je pense qu'il est utile que tu trouves une méthode pour gérer les retenues.  Tu pourras ensuite programmer cette méthode, que ce soit en binaire ou en décimal.

        7. Addition de décimaux je vois pas en quoi ça peut m'aider

          Exemple:8+2=10

          Bon par exemple addition binaire de 1 et 3

          1=0  0  0  0  0  0  0  1

          3=0  0  0  0  0  0  1  1

          -------------------------------

          =  0  0  0  0  0  1  0  0

          Pour faire une additioon il faut que j'utilse xor car 0 xor 0=°

          0 xor 1=1

          1 xor 0 =1

          1 xor 1=0

          Donc l'opération parfaite pour faire une addition

          Pour gérer les retenues,j'utilse & car :

          0 &0=0

          0 &1=0

          1 &0=0

          1&1=1

          a &b je dois décaler à droite d'1 position le résultat pour pouvoir isolé le bit de poids faibe

          EX:(1&3)=1=                0000 0001

          décalage a droite=   0  0000 0010

          Ce nombre est donc le résultat de (1&3)<<1

          Ensuite si je fait (1 xor 3) on a 2=0000 0010

          ET donc si j'additione (1 xor 3) avec  (1&3)<<1 j'obtient le résultat voulu a savoir 4 carù

          (1&3)<<1=         0  0000 0010

          1 xor 3=                 0000 0010

                              ------------------------------

                            =     0   0000 0100

          Mais bon cette derniere etape je peux pas utiliser xor car il ne me permet pas d'ajouter les retenues

          Je sais comment ajouter cette retenue a la 3 colonne

          J'ai pensé que peut etre une fonction pourrait le faire mais bon j'ai pas pu implenter cette fonction secondaire pour ajouter une retenue a la colonne suivante

          1. Contributeur

            ton code ne fait pas du tout ce que tu expliques.

          2. @yg_be

            Oui car j'ai pas reussi a gerer les additions des retenues du coup j'arrive pas a avancer

          3. Contributeur

            Tu ne te souviens pas comment faire une addition de nombres décimaux?

        8. Oui moi je l'ai fait .Sans exemple sur papier je n'aurais pu rien faire

          Moi je sais juste que pour connaitre la retenue faut faire un ET LOGIQUE et j'ai fait ça dans mon code mais ça marche pas

          Les 4 opérations pour une addition binaire c'est XOR qui me permet de le faire

          1. Contributeur

            Retranscris ici les exemples que tu as fait, et la méthode que tu penses pouvoir utiliser pour faire une addition de nombres binaires.  As-tu envisagé de t'inspirer de la méthode utilisée pour faire une addition de nombres décimaux?

        9. J'ai réfléchi toute la journée mais j'arrive pas a faire l'adition.Un petit coup de main me sera trés utile

            Si pour de simple entier je n'arrive pas il me sera impossibl de le faire pour tall integer

          Mon autre code il marchait pas car a un moment j'ai:

           (0000  0010 ) xor (   0000  0100)=0000 0000 ne tient pas compte de la retenue et donc on n'obtient pas 0000 00100

          1. Contributeur

            Eh bien, il faut donc effectuer la retenue.

            Qu'as-tu essayé?  Commence avec des exemples faits sans programmation, cela t'aidera à concevoir une méthode pour le programmer.

            Avant d'écrire du code, il est nécessaire de bien comprendre ce que doit faire le code.

        10. Je viens de voir que ça me donne que des 0,donc ça marche pas .je suis dit comme ça marche pour 1 ça veut dire c’est bon mais bon c’était donc qu’un coup de chance que ça a marché pour 5 et 4.Bon je vais essayer de trouver le soucis 

          1. Contributeur

            Il est utile de bien tester de nombreux cas, pas juste un ou deux.

        11. bonjour j'ai essayé de faire la soustraction et l'addition si j'ai des int .Pour l'addition ça marche mais pas la soustraction et pourtant A-B=A+(-B)=1+(inversion des bits de B+1)

          #include <stdio.h>
           
          int add(int x, int y) {
              int keep = (x & y) << 1;
              int res=x^y;
              return keep^res;
          }
          
          int convertir_binaire(int x){  
             int i;
             for(i=7;i>=0;i--){
                printf("%d",(x>>i)&1);
             }
          }
          
          int soustraction(int x, int y) {
              int a=add(~y,1);
              return add(x,a);
          }
          
          int main(){
            
            printf("5 en binaire:");convertir_binaire(5);
           printf("\n");
            printf("4 en binaire:"); convertir_binaire(4);
           printf("\n");
            int a=add(5,4);
            printf("Le résultat de l'addition binaire de 5 et 4:");convertir_binaire(a);
            printf("\n");
            int b=soustraction(5,4);
            printf("Le résultat de la soustraction binaire de 5 et 4:");convertir_binaire(b);
           
            return 0;
          }

          Le résultat de l'addition binaire de 5 et 4:00001001

          Le résultat de la soustraction binaire de 5 et 4:11111101 ce qui est faux

          Bon ensuite comment j'adapte mon code au tall_integer scahnt que je ne manipule pas des int ici

          1. Contributeur

            Ton addition est fausse.  As-tu testé 1+3?

        12. Je viens tout juste de voir que il m’a répondu à 9:38 bizarre je l’avais même pas vu

          j’ai vu hier que celui à 18h .Bref oubliez ce que j’ai dit alors.Je vais analyser sa réponse du coup

          Merci

          1. Vos impressions sont exactes ,je dois faire des additions et soustraction de bit .Et meme jusqu'a hier je reflechissais comment faire ma fonction addition pour qu'il gere le cas de la derniere retenue(sans cette derniere retenue le nombre binaire resultat de l'addition des bits de 2 nombres binaires sera fausse

            On m'a dit c'est pas tres intelligent de faire des if ex:0+1=1

            1+1=10

            etc

            Idem pour la soustraction

            Mais bon pour ne pas trop me disperser j'ai prefere comprendre d'abord le type grand entier comment il fonction set bit et clr bit 

            ...mon message d'aujourd'hui a 5h du mat

            j'ai pas encore eu d'ailleurs de reponse

          2. D’après ce qu’elle j’ai compris du code de mamiemando, il a alloué de l’espace pour 10 entier de type uint8_t et donc de taille 1 octet = 8 bits et donc  la taille sera 10 x 8 = 80 octets

            Car si on écrivait par exemple calloc(4, sizeof(int)) on allouerait l’espace pour 4 entiers, or comme un entier fait 4 octets, la taille du bloc alloué de 4 x 4=16 octets

            N’est-ce pas?

            Donc si je veux alloue de l’espace pour 1 entier de 32 bits soit 1 octet, donc de taille 1 x 1 = 1 octet, et donc je dois faire:

            #include <stdint.h> // uint*_t
            #include <stdlib.h> // malloc, free
            #include <string.h> // calloc
            
            typedef struct tall_int {
                uint32_t * data;
                size_t size;
            } tall_int;
            
            tall_int * ge_alloc() {
                tall_int * ge = malloc(sizeof(tall_int));
                if (!ge) return NULL;
                ge->size = 1;  
                ge->data = (uint32_t *) calloc(sizeof(uint32_t), ge->size);
                if (!ge->data) {
                    free(ge);
                    return NULL;    
                }
                return ge;
            }

            Et si je veux par exemple augmenter la capacité par exemple 1056 bits (132 octets)soit 33 fois la taille de uint32_t (donc 33 incrémentation de 32 bits)je dois faire

            #include <stdint.h> // uint*_t
            #include <stdlib.h> // malloc, free
            #include <string.h> // calloc
            
            typedef struct tall_int {
                uint32_t * data;
                size_t size;
            } tall_int;
            
            tall_int * ge_alloc() {
                tall_int * ge = malloc(sizeof(tall_int));
                if (!ge) return NULL;
                ge->size = 1;
                
                ge->data = (uint32_t *) calloc(sizeof(uint32_t)*33, ge->size);
                
                 
                if (!ge->data) {
                    free(ge);
                    return NULL;    
                }
                return ge;
            }

            Et enfin, si par exemple je veux me débrouiller pour que la quantité de mémoire que j’alloue correspond aux besoins de stockage de mon entier.

            De plus, si je suppose que mon entier a une taille par défaut (par exemple, 64 bits), mais que cette taille n’est pas suffisante, pour que je puisse mettre un ou plusieurs bits de supplémentaires (par exemple mettre un bit à 1). De base pour mettre l’entier a un bit à 1 on fait: a | 1 << position

            Autre question, mieux vaut augmenter ma taille de 1 lors du realloc, ou bien doubler la taille du bloc ?

            Je veux juste comprendre ces subtilités et je pense que ça sera bon.

            1. Modérateur

              D’après ce qu’elle j’ai compris du code de mamiemando, il a alloué de l’espace pour 10 entier de type uint8_t et donc de taille 1 octet = 8 bits et donc  la taille sera 10 x 8 = 80 octets

              Car si on écrivait par exemple calloc(4, sizeof(int)) on allouerait l’espace pour 4 entiers, or comme un entier fait 4 octets, la taille du bloc alloué de 4 x 4=16 octets

              Oui. Comme je l'ai dit, deux stratégies sont possible

              • Soit tu utilises le code sans structure, dans lequel je fais :
                typedef uint32_t tall_int;

                Dans ce cas tall_int est juste un alias vers uint32_t et fait 32 bits soit 4 octets. L'avantage c'est que pour ce type, tout est déjà défini (addition, soustraction, printf, etc...), mais la taille du tall_int est bornée.

              • Soit tu utilises le code avec structure (voir #7) et si tu regardes, il n'est plus question de uint32_t, mais uniquement de uint8_t. C'est délibéré, c'est pour raisonner en octets. Comme chaque uint8_t qui fait 8 bits soit 1 octet, si j'en alloue 10, ça fait 10 x 1 = 10 octets. L'avantage c'est que pour ce type, le tall_int peut arbitrairement grand sous réserve d'allouer suffisamment de mémoire, mais tout reste à définir (addition, soustraction, printf, etc...).

              Car si on écrivait par exemple calloc(4, sizeof(int)) on allouerait l’espace pour 4 entiers, or comme un entier fait 4 octets, la taille du bloc alloué de 4 x 4=16 octets

              Oui. La manière dont tu calcules la taille n'a pas d'importance du moment que la valeur de cette taille reste la même. Ainsi calloc(8, sizeof(uint8_t)) et calloc(2, sizeof(uint32_t)) sont strictement équivalents, les deux allouent au final un bloc de 64 bits (8 octets).

              Entre calloc(2, sizeof(uint32_t)) et malloc(2 * sizeof(uint32_t)), les deux allouent 64 bits, mais calloc met ces 64 bits à 0 contrairement à malloc. En conséquence, un calloc est donc légèrement plus coûteux, mais permet d'avoir un bloc initialisé.

              Si tu regardes le message #7, c'est suite à cette nuance que j'ai utilisé un coup malloc, un coup calloc.

              • Dans le premier cas, je n'avais pas besoin de faire une remise à 0 des bits (car j'initialise complètement la structure juste après).
              • Dans le second cas, je voulais que le bloc de données soit initialisé à 0 de sorte à ce que le tall_int modélisé corresponde à 0.

              Et si je veux par exemple augmenter la capacité par exemple 1056 bits (132 octets)soit 33 fois la taille de uint32_t (donc 33 incrémentation de 32 bits

              Si tu veux allouer 132 octets tu dois simplement allouer... 132 octets :-) Modulo les nuance calloc/malloc, la manière dont tu l'écris importe peu. Tu pourrais très bien écrire :

              uint8_t * data = (uint8_t *) malloc(132);

              Ensuite, si à la place de 132, tu veux écrire 33 * sizeof(uint32_t), comme cette multiplication retourne 132, c'est équivalent. Par contre version avec la multiplication aide à la lisibilité (elle insiste sur le fait qu'on veut allouer 32 uint32_t, information qu'on ne perçoit pas quand on écrit directement son résultat 132)

              De plus, si je suppose que mon entier a une taille par défaut (par exemple, 64 bits), mais que cette taille n’est pas suffisante, pour que je puisse mettre un ou plusieurs bits de supplémentaires (par exemple mettre un bit à 1).

              Je n'ai pas compris, il doit manquer des mots. Mais ce qui est clair, c'est que tu ne peux pas sortir du bloc de mémoire alloué, sinon tu vas dans le cas général déclencher une erreur de segmentation.

              Mieux vaut augmenter ma taille de 1 (realloc) ou bien doubler la taille(realloc)?

              Ça dépend de ce que tu veux faire.

              • Si tu sais que cette réallocation est la dernière car elle est suffisante, autant préserver la mémoire et n'allouer que le nécessaire.
              • Si tu sais que tu es susceptible de devoir réallouer de nombreuses fois le même buffer, tu peux doubler la taille à chaque fois pour minimiser le nombre de réallocations (en sacrifiant plus de mémoire). C'est une stratégie parmi tant d'autres, tu peux être plus ou moins gourmand concernant la taille de mémoire supplémentaire que tu vas allouer.

              De base pour mettre l’entier a un bit à 1 on fait: a | 1 << position

              • Si tu utilises un uint32_t, pas de problème tu peux directement mettre son 17-ème bit de poids faible à 1 ainsi :
                uint32_t i = 1234;
                i |= 1 << 17;
              • Si tu es dans la version "structure" de tall_int, l'index du bit à modifier peut être arbitrairement grand, or 1 << i correspond à un type entier. Donc si tu voulais modifier le 234-ème bit de poids faible ça n'irait pas. Il faut d'abord sélectionner le bon octet, puis corriger cet octet comme on le ferait pour un uint32_t.
                tall_int ge = ...
                size_t index_octet = 117 / 8;
                size_t index_bit = 117 % 8;
                ge->data[index_octet] |= 1 << index_bit;

              Attention cependant à l'endianness. En pratique, il y a deux endianness :

              • En big endian, les bits d'un entiers sont ordonnés par puissance de 2 décroissantes. Cette convention de stockage était utilisé sur les anciens système d'exploitation est reste la convention utilisée pour véhiculer une valeur entière dans un paquet réseau (par exemple, la taille du paquet). Si l'on note b_k le k-ème bit de poids faible d'un entier n, alors n = sum(b_k . 2^k) 
              • En little endian, certains blocs de bits sont permutés, et donc cette formule n'est plus vraie.

              Dit autrement :

              • dans la version "alias d'uint32_t", il faut être vigilant, car l'entier est stocké en little endian
              • dans la version "structure", ça dépend de la convention que tu choisis d'adopter. Le plus simple serait sans doute d'adopter la convention big endian. Ainsi, lorsque tu voudras implémenter les opérations manipulant ton type tall_int ce sera plus facile.

              Bonne chance

            2. @mamiemando

              Merci d'avoir repondu a ma question d'hier a 13h 

              maintenant je vois mieux

            3. Contributeur
              @leoliom

              Salut mamiemando,

              tall_int ge = ...
              size_t index_octet = 117 / 8;
              size_t index_bit = 117 % 8;
              ge->data[index_octet] |= 1 << index_bit;

              Sauf erreur, ce code, qui est bien pratique, suppose une organisation des octets en little endian, où les bytes de poids faible viennent en premier.

              Sur nos machines Windows, Linux ou Mac actuelles fonctionnant en little endian je ne trouve pas qu'il soit plus simple d'adopter la convention big endian.

              Cela rendrait plus compliquée l'utilisation de types de base de plus grande capacité.

              D'ailleurs, pourquoi utiliser des uint8_t et se priver de uint32_t, alors qu'il permet déjà d'utiliser les opérateurs de base sur des nombres allant jusqu'à 4294967295 contre 255 pour l'autre. Utiliser un type de base plus grand va limiter le nombre de fois que l'on aura à gérer des retenues.

              On peut écrire des fonctions comme celles-ci pour déterminer, pour une addition ou une soustraction sur une "colonne" donnée, s'il est nécessaire l'aller altérer le bloc suivant (la "colonne" suivante) :

              #define BASE_UTYPE      uint32_t
              #define BASE_UTYPE_MAX  UINT32_MAX
              
              BASE_UTYPE sum_carry_needed(BASE_UTYPE a, BASE_UTYPE b) {
                      return (b > 0 && a > BASE_UTYPE_MAX - b) ? 1 : 0;
              }
              
              BASE_UTYPE sub_borrow_needed(BASE_UTYPE a, BASE_UTYPE b) {
                      return (a < b) ? 1 : 0;
              }
              

              Ici on passe à ces fonctions des paquets de données correspondant au type de base "en colonnes" (comme si on posait l'opération, mais les "colonnes" sont des paquets de uint32_t).

              • Si sum_carry_needed() retourne faux, on sait que l'on peut additionner les deux données de cette colonne (avec l'opérateur + du C comme il se doit) sans avoir à gérer une retenue.
              • Si elle retourne faux, on peut aussi additionner les deux données (toujours avec l'opérateur + du C), mais on ajoutera 1 au paquet de données sur la "colonne" suivante (en vérifiant s'il n'y a pas de retenue provoquée par cette addition, etc.).

              Le fait d'utiliser un type de base plus grand va permettre de traiter plus de données à la fois dans chaque "colonne".

              A vrai dire, je suis troublé par l'approche de l'exercice, en voyant toutes ces fonctions de manipulation au niveau du bit à implémenter... j'ai l'impression qu'elles ont pour intention d'amener les personnes faisant l'exercice à faire des additions ou soustractions au niveau du bit comme si on les posais sur une feuille de papier.

              (c'est un point qui n'a pas été abordé dans vos échanges)

              Cela ne semble pas très réaliste...

              Après si c'est un exercice et que l'enseignant demande à ce que ce problème soit traité par des additions ou soustractions en colonnes gérant les retenues au niveau du bit ... qu'il en soit ainsi et oubliez tout ce que je viens d'écrire !

            4. @mamiemando

              Il y a une chose que je n'ai pas trop compris : pourquoi si on utilise le type tall_int on peut pas aussi faire les mêmes opérations que uint32 ? N'est-ce pas la même chose pour les deux ?

              J'ai voulu aussi tester ce que vous avez écrit :

              #include <stdio.h>
              #include <stdint.h>
              
              int main() {
                  uint32_t i = 1234;
                  int j;
                  for(j = 17 ; j >= 0; j--) {
                      printf("%u", (i & j) == j);
                  }
                  printf("\n");
              
                  i |= 1 << 17 ;
                  int k;
                  for (k = 17; k >= 0; k--){
                      printf("%u", (i&k) == k);
                  }
                  return 0;
              }

              ça me donne ceci:

              010000000000000101

              010000000000000101

              Bizarrement ça modifie pas le 17eme bit et ne le met pas à 1

              Concernant ceci:

              tall_int ge = ...
              size_t index_octet = 117 / 8;
              size_t index_bit = 117 % 8;
              ge->data[index_octet] |= 1 << index_bit;

              index octet et  index bit ps trop compris

              Par exemple si j'ai un nombre=61685=1111000011110101

              Il y a 2 octets

              Si je fais 61685/8 ça ne me donne pas l'index de l'octet mais un nombre trop grand

              etc

              Du coup j'ai essayé de l'appliquer a ma fonction ci dessous(met à 1 le bit de position x par l' entier pointé par e et elle renvoie e) mais je pense pas que le resultat sera correct

              tall_integer *set_bit(tall_integer *e, uint32_t x) {
                return NULL;
              }
            5. Contributeur
              @Theo_0055

              qu'essaies-tu de réaliser avec "printf("%u",(i&j)==j);"?

          3. Ok je comprends merci

            Juste une question,avec votre exemple si je veux par exemple manipuler des entiers de 32bits à la place de uint8_t on met uint32_t?

            1. Contributeur

              Si tu veux faire un code évolutif, et puisqu'on te demande, dans un premier temps, de commencer par un code susceptible de traiter des entiers de 32 bits, tu peux emprunter le code de mamiemando avec un type de base 32 bits uint32_t et lorsque tu lui alloues la mémoire, tu lui alloues de la mémoire que pour un seul uint32_t.

              Cela veux dire que lorsqu'on te demandera d'augmenter la capacité, tu pourras l'augmenter par incréments de 32 bits.

              Cela peut accélérer l'exécution de ton code, car les processeurs, de nos jours, ne traitent plus vraiment les informations par octets.

          • 1
          • 2