Manipuler de grands nombres

Résolu/Fermé
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 - Modifié le 9 oct. 2022 à 23:48
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 - 23 oct. 2022 à 23:03

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

mamiemando Messages postés 33146 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 11 juin 2024 7 757
10 oct. 2022 à 00:10

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

2
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474
9 oct. 2022 à 18:48

bonjour,

l'exercice fait suite à un cours sur quel sujet?

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
Modifié le 9 oct. 2022 à 19:30

C'est suite a un cours mais tres tres court sur la  manipulationde bits

En fait ils disent les grands entiers ,ils son tcodés sur plus de bits que ne peuvent en contenir les entiers disponibles dans le langage.Parfois on en a besoin par exemple dans certaines domaines où il faut utiliser de grands chiffres

0
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474
9 oct. 2022 à 19:33

Tu as déjà eu un cours à propos de "créer dans le tas"?

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
Modifié le 9 oct. 2022 à 20:29

Non j'ai pas de cours la dessus mais l'enonce a dit on veut créer de grands entiers dynamiquement dans le tas .Meme   si, au debut, ils n'ont que 32 bits, il faudra  écrire des fonctions d'allocation et de liberation.En effet,dans l'exo ils ont supposé au debut  que  que les entiers ont une taille fixe de 32 bits et ils ont dit que pour les autres parti de l'exo on augmentera cette taille

mais moi je sais meme pas ce que ça veut dire créer dans le tas,cette phrase elle n'a pas pour moi beaucoup d'importance.!

0
[Dal] Messages postés 6185 Date d'inscription mercredi 15 septembre 2004 Statut Contributeur Dernière intervention 7 juin 2024 1 087
9 oct. 2022 à 20:39

le tas est la mémoire disponible sur le système susceptible d'être allouée avec malloc()

0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
9 oct. 2022 à 21:17

Ah je savais pas merci 

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
Modifié le 11 oct. 2022 à 15:17

Merci pour ces quelques éclaircissements. Je dois revoir un peu mon cours sur la mémoire en C avant d'attaquer cet exercice.

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
Modifié le 13 oct. 2022 à 06:03

J'ai fini de réviser tout mon cours et je comprends maintenant les types uint8_t et les histoires de tas et de pile et autres et ce que vous avez fait.Je vias essayer de faire le reste et je vous en tiendrais au courant

0
mamiemando Messages postés 33146 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 11 juin 2024 7 757
13 oct. 2022 à 10:24

Parfait, bon courage ! La question initiale étant réglée, je bascule le sujet en résolu. Si tu as d'autres questions par rapport à ton exercice, merci d'ouvrir un nouveau fil de discussion afin de garder le forum propre (un problème par discussion).

Bonne continuation

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
13 oct. 2022 à 11:42

d'accord merci la reponse a mes codes je le metterais dans un autre fil de discussion

0
mamiemando Messages postés 33146 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 11 juin 2024 7 757
13 oct. 2022 à 14:34

Merci, mais ça n'est pas nécessaire, à moins que tu sois particulièrement fier de ton code :-).

Je m'explique : le but d'un forum est de poser dans chaque discussion un petit problème, clair et réutilisable. Pour cela il doit mettre en jeu une notion minimale et clairement identifiée. Dans les sous-forums liés aux systèmes, ce serait typiquement installer un logiciel particulier, résoudre un message d'erreur particulier, réaliser une tâche d'administration système ou réseau particulière, etc. Dans les sous-forums liés à la programmation, ce serait comment réaliser une tâche minimale particulière, comment utiliser une fonction, comment résoudre une erreur de programmation ou un bug ; mais pas comment réaliser un exercice ou un projet de A à Z.

En effet, le but est que les gens puisse facilement trouver sur le forum avec un minimum de lecture la réponse précise à leur question (qui a peu de chance d'être exactement ton exercice, en tout cas pas dans sa globalité).

C'est d'ailleurs pour ça qu'à moins que l'exercice soit extrêmement court, on est souvent un peu récalcitrants à répondre à un exercice, car outre les aspects négatifs sur le plan pédagogique, un exercice met souvent en jeu plusieurs notions. 

Dans le cas présent, le but de ce fil de discussion discussion était de définir un type personnalisé, discuter comment l'allouer et le désallouer. Comme je pense que pour ce problème initial, tout a été dit, j'ai proposé de basculer le sujet en résolu. Si cependant tu fais face à d'autres difficultés, je t'invite à ouvrir un nouveau fil de discussion dans lequel tu proposeras un exemple minimal mettant ton problème en évidence, on ce fil de discussion se limitera spécifiquement à ce problème.

Bonne chance

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
Modifié le 13 oct. 2022 à 15:48

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?

0
[Dal] Messages postés 6185 Date d'inscription mercredi 15 septembre 2004 Statut Contributeur Dernière intervention 7 juin 2024 1 087
Modifié le 13 oct. 2022 à 21:37

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.

0
leoliom Messages postés 171 Date d'inscription jeudi 21 juillet 2016 Statut Membre Dernière intervention 20 février 2024 2
Modifié le 14 oct. 2022 à 10:16

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.

0
mamiemando Messages postés 33146 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 11 juin 2024 7 757
Modifié le 14 oct. 2022 à 10:32

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

0
leoliom Messages postés 171 Date d'inscription jeudi 21 juillet 2016 Statut Membre Dernière intervention 20 février 2024 2 > mamiemando Messages postés 33146 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 11 juin 2024
14 oct. 2022 à 09:48

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

maintenant je vois mieux

0
[Dal] Messages postés 6185 Date d'inscription mercredi 15 septembre 2004 Statut Contributeur Dernière intervention 7 juin 2024 1 087 > leoliom Messages postés 171 Date d'inscription jeudi 21 juillet 2016 Statut Membre Dernière intervention 20 février 2024
Modifié le 14 oct. 2022 à 18:40

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 !

0
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474 > Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023
15 oct. 2022 à 16:02

As-tu testé ta méthode?

1
mamiemando Messages postés 33146 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 11 juin 2024 7 757 > Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023
17 oct. 2022 à 13:45

@[Dal] StatutContributeur Message #18

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.

Tout à fait, et je le dis d'ailleurs en toutes lettres dans mon message #16 : on suppose dans ce code que l'on adopte pour ce type une représentation big endian. Rien n'oblige quand on fait son propre type à utiliser l'endianness que l'on souhaite du moment que les opérations qu'on applique dessus sont cohérentes.

En l'occurrence, que ton système soit big endian ou little endian, tu peux donc représenter si tu le souhaite un tall_int avec une représentation big endian. Bien entendu, il faut coder les opérations arithmétiques en fonction de l'endianness que tu as choisi d'utiliser.

Supposons qu'on soit sur un système little endian (c'est le cas la plupart du temps de nos jours) et que l'on veuille coder l'addition sur un tall_int avec une représentation big endian. Pour ce faire, tu peux itérer octet par octet en partant de l'octet de poids faible vers l'octet de poids fort.

Note au passage qu'il est sans doute intéressant pour faciliter l'itération d'organiser les octets dans ce sens (c'est-à-dire l'octet de poids faible à gauche) pour faciliter l'écriture du code. En pratique, tu choisis la convention que tu veux. C'est d'ailleurs ce que tu proposes dans le message #18.

Comme on est à l'échelle de l'octet, l'endianness ne joue pas et on peut utiliser l'addition native d'un uint8_t avec un uint8_t. Le seul point, sur lequel il faut être attentif, c'est gérer les retenues. C'est d'ailleurs le point que tu abordes dans la suite de ton message. En cas de retenue, la propager vers l'addition faite pour l'octet suivant. Bref c'est pas hyper naturel à coder, mais ça se fait.

@Theo_0055 StatutMembre

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

Si tu définis tall_int comme un uint32_t, il n'y a rien à faire, on peut utiliser les opérations natives codées dans la libc pour les uint32_t. Toute la discussion que [Dal] et moi avons est en rapport avec la version ou tall_int est défini à l'aide d'un buffer arbitrairement grand.

Bonne chance

1
leoliom Messages postés 171 Date d'inscription jeudi 21 juillet 2016 Statut Membre Dernière intervention 20 février 2024 2
14 oct. 2022 à 19:02

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

0
[Dal] Messages postés 6185 Date d'inscription mercredi 15 septembre 2004 Statut Contributeur Dernière intervention 7 juin 2024 1 087
14 oct. 2022 à 22:43

mamiemando a répondu de façon très détaillée à ton message :

https://forums.commentcamarche.net/forum/affich-37704271-manipuler-de-grands-nombres#16

non ?

0
leoliom Messages postés 171 Date d'inscription jeudi 21 juillet 2016 Statut Membre Dernière intervention 20 février 2024 2
15 oct. 2022 à 04:31

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

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
15 oct. 2022 à 09:00

ne faites pas attention leoliom est mon 2nd compte

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
Modifié le 15 oct. 2022 à 19:15

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

0
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474
16 oct. 2022 à 00:10

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

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
16 oct. 2022 à 05:18

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 

0
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474
16 oct. 2022 à 09:45

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

1
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
16 oct. 2022 à 17:30

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

0
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474
16 oct. 2022 à 17:58

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.

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
16 oct. 2022 à 18:12

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

0
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474
16 oct. 2022 à 18:23

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?

1
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
16 oct. 2022 à 19:34

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

0
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474
16 oct. 2022 à 21:00

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

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1 > yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024
16 oct. 2022 à 21:09

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

0
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474
16 oct. 2022 à 21:33

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

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
16 oct. 2022 à 21:40

Si par exemple 
  10,5

+  2,9

----------

=  13, 4

oui je sais faire

0
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474
16 oct. 2022 à 21:50

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

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1 > yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024
16 oct. 2022 à 22:09

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

0
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474 > Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023
17 oct. 2022 à 08:57

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

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1 > yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024
17 oct. 2022 à 11:22

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 

0
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474 > Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023
17 oct. 2022 à 11:56

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.

0
Theo_0055 Messages postés 275 Date d'inscription mardi 21 juillet 2020 Statut Membre Dernière intervention 19 janvier 2023 1
Modifié le 17 oct. 2022 à 12:34

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) 
0
yg_be Messages postés 22867 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 12 juin 2024 1 474
17 oct. 2022 à 12:41

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

1