Opérations de base sur les bitsRésolu

Question

Bonjour,j'ai un exo où on me demande de manipuler de trés grand nombre et on me demande de faire des soustraction,addition,multiplication,nombre de bits... en binaire mais je peux pas faire cette exo sans comprendre d'abord la logique de comment on fait pour des petits nombres déja

Par exemple en multiplication je sais que:

Ex:2x3

2=0000 0010

3=0000 0011

ETAPE1:on fait 1xtous les bits de 2

ETAPE2:On déacale d'1 cran vers la droite et on fait 1 x tous les bits de 2

ETAPE3:On déacale d'1 cran  vers la droite et on fait 0 x tous les bits de 2

ETAPE4:On déacale d'1 cran  vers la droite et on fait 0 x tous les bits de 2

......

ETAPE8:On déacale d'1 cran  vers la droite et on fait 0 x tous les bits de 2

Derniere etape:Additionner les bits par colonne

En gros donc j'ai compris qe une multiplication binaire et une combinaison d'addition det de décalge sauf que l'implemter c'est autre chose.

Que dois je faire pour arriver a écrire cette fonction?

Bon j'attaque celui qui est le plus difficile selon moi et apres  les autres on verra

Dalfab · Answer

Bonjour,

Ta décomposition pour la multiplication est presque correcte à part:
- ce ne sont pas des décalages à droite mais des décalages à gauche qu'il faut faire.
- multiplier par 1 ne nécessite en fait aucune multiplication, et multiplier par zéro est encore plus simple.
Viens ensuite ta dernière étape: additionner les bits par colonne. En base 2, l'addition est plus complexe que la multiplication. Je l'écrirais plutôt: additionner tous les nombres trouvés précédemment, en supposant que l'addition de grand nombres est déjà définie quelque part.

Il faut donc commencer par l'addition de 2 grand nombres:
Ici tu es vraisemblablement sur des nombres tellement grands que le processeur ne sait les additionner.
Pour ajouter 2 nombres, on peut aussi opérer 1 bit après l'autre. Je vais aussi partir d'un exemple:
3+14 soit:
0 0 0 0 0 1 1 
0 0 0 1 1 1 0 +
==========
- On va ajouter les 2 derniers bits: 1 + 0 = 1, on obtient 1, on retient rien
- les 2 avant derniers: 1 + 1 + retenue0 = 0, on retient 1
- les 2 antépénultièmes: 0 + 1 + retenue1 = 0, on retient 1
- les précédents: 0 + 1 + retenue1 = 0, on retient 1
- les précédents: 0 + 0 + retenue1 = 1, on retient rien
- puis plus que des zéro et pas de retenue à ajouter, on a fini.
Le résultat est obtenu en décalant à gauche le bit trouvé à chaque étape : 1 0 0 0 1 soit 17.
On voit que l'on pourrait avoir ainsi géré 2 nombres de plusieurs centaines de bits avec des calculs intermédiaires qui ne reviennent finalement qu'à ajouter 3 bits.

La méthode marche. Mais on peut peut-être utiliser le fait que le processeur sait déjà ajouter 3 nombres faisant plus d'un bit. On peut par exemple découper le grand nombre, non pas bit par bit, mais 16 bits par 16 bits. Le principe précédent marche, à chaque étape on aura 2 nombres de 16 bits et une retenue de 16 bits à ajouter (on n'est plus en base 2 mais en base 65536). Et les résultats intermédiaires des nombres de 16 bits avec un décalage de 16 à chaque étape.

Pour revenir à la méthode bit par bit de l'addition:
On part d'un résultat mis à 0. et d'une retenue à 0.
La première étape c'est : trouver le dernier bit de chacun des très grand nombres, additionner ces 2 bits. On trouve 0: bit est 0, retenue 0. On trouve 1: bit est 1, retenue 0. On trouve 2: bit est 0, retenue 1. On trouve 3: bit est 1, retenue 1. Si bit vaut 1, on stocke dans résultat le bit sans le décaler.
Pour la i-ème étape, ce sont les i-èmes bits en partant de la fin qu'ils faut trouver et additionner avec la retenue précédente. Si bit vaut 1, il faut le décaler de i avant de le mettre dans résultat.

Si on pose que tu as écris des fonctions pour décaler un grand nombre de i bits à gauche, une fonction pour positionner le ième bit, et une fonction pour trouver la valeur du ième bit. Tout peut s'écrire en utilisant ces fonctions.

Theo_0055 · Answer

Bonjour j'ai anlyse chaque detail que vous m'avez explique et juste une chose pourquoi doit on decaler a gauche  a chaque fois le bit

J'ai essayer de faire des dessins et tout mais j'arrive pas a comprendre cela.

Pour l'addition bit et bit je suis toujours entrain de reflechir a comment le faire et a implementer ces fonctions auxiliaires(ceux de la fin de votre message).Des que je trouve je vous dirais

ah oui desole je vous ai pas dit que j'ai une structure qui s'appelle tall_int:

struct tall_int{
  size_t size
  uint32 *data

}

tall_integer *add(tall_integer *b, tall_integer *a) 
/*Ce dernier foit additionner le grand entier pointe par b a celui pointe par a et doit renvoyer b en gros *b=*b+*a*/

Dalfab · Answer

Les fonctions nécessaires ne sont pas si simples. Il faut essayer. Si on suppose que size est le nombre utile de bits dans le tall_int, on peut écrire par exemple: struct tall_int tall_int_create_null(void) { struct tall_int res; res.size = 1; // le nombre zéro nécessite un bit. res.data = malloc( sizeof(uint32) ); // allocation minimale pour au moins 1 bit res.data[0] = 0; // la donnée vaut 0 return res; } void tall_int_left_shift( struct tall_int* pvalue, int nb ) { if ( pvalue->size <= 32 && pvalue->data[0] == 0 ) return; // Le nombre zéro reste zéro. size_t nb_uint32 = ( pvalue->size + 31 ) / 32; // ça calcule bien le nombre min de uint32 pour avoir size bits accessibles! size_t nb_uint32_needed = ( pvalue->size + nb + 31 ) / 32; pvalue->size += nb; if ( nb_uint32 != nb_uint32_needed ) { // il faut ré-allouer plus de uint32 size_t nb_added_uint32 = nb_uint32_needed - nb_uint32; uint32* new_data = realloc( pvalue->data, nb_uint32_needed * sizeof(uint32) ); pvalue->data = new_data; // on ajoute des zéros à droite (donc pour le moment on décale à gauche de 32*nb_added_uint32) for ( size_t i = nb_uint32 ; i < nb_added_uint32 ; i++ ) pvalue->data[i] = 0; // 32 bits à zéro de plus nb -= nb_added_uint32 * 32; // du coup le décalage à faire change } if ( nb > 0 ) { // il faut décaler à gauche, c'est complexe de le faire bit par bit // car ici on doit déplacer des bits tout en modifiant la même zone, passer par // 2 buffers où on copie les bits d'un buffer vers un autre buffer serait plus simple // on peut repenser cette fonction... .... TODO .... } else if ( nb < 0 ) { // il faut décaler à droite de -nb, là aussi ça n'est pas simple .... TODO .... } } La fonction de décalage est vraisemblablement la plus complexe de toutes. La version que je donne est incomplète et peut peut-être être simplifiée. L'addition et la multiplication sont plus simples. L'exercice n'est pas simple du tout pour un débutant ...

Theo_0055 · Answer

Merci beaucoup car je bloqué un peu dessus depuis presque 2 semaines????Non je suis pas débutant disons c’est ma 3eme Anne ou je fais du C .Sauf que on m’a donné ce devoir alors que j’ai jamais fait de manipulation de bit.Du coup c’est ma 1ere fois

Je vais analyser tout ça et essayer de faire l’addition et la multiplication et de compléter vos pointillés

merci encore

Theo_0055 · Answer

Bonjour je voulais savoir si mon type tall_int a la place d'un size_t size on avait un int taille pour dire c'est la taille du tableau,esceque l'exo serait plus simple a faire?

Theo_0055 · Answer

Bonjour votre fonction tall_int_create_null si on le fait de cette façon:

tall_int_t *tall_int_create_null(void) {
    tall_int_t * ge = malloc(sizeof(tall_int_t));
    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;
}

Je l'ai adapté a mon exo au cas ou vous ne compreniez(votre

tall_int_create_null est la même chose que le ge_cree de mon exo

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;
}

Aurais je une erreur dans la fçon dont on cré un tall_int et dont la façon on le libére?car je vois pas où se trouve le problème me^me en débuggant avec gdb

Dommage que ici je peux pas mettre en piece jointe mon fichier test pour que vous puissiez comprendrede quoi je parle

Theo_0055 · Answer

bonsoir finalement j'ai débugger mon probléme. Je voulais juste savoir pourquoi on peut pa utiliser le symbole >> pour faire par exemple un décalage a droite et << a gauche

Dalfab · Answer

Bien sûr que >> et << peuvent être utilisés, et même doivent être utilisés pour décaler un tall_integer! Sauf que comme le tall_integer est peut être composé de plusieurs uint32, il faudra utiliser des >> et des << et des & et des | pour tous les cas de décalage à gauche, et tu auras aussi besoin de toutes les 4 opérations citées pour le décalage à droite.

Theo_0055 · Answer

D’accord je vois ça a l’air compliqué mais j’essaierais de le faire ,j’ai,pas encore réussi

Dalfab · Answer

En utilisant encore un exemple: Cas d'un tall_integer composé de 2 uint32 à décaler à gauche de 5 bits. Le poids fort fait 12 bits utiles que je représente par des X, le dernier est représenté par des Y.
Avant décalage :
00000000000000000000XXXXXXXXXXXX   YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
Après décalage :
000000000000000XXXXXXXXXXXXYYYYY   YYYYYYYYYYYYYYYYYYYYYYYYYYY00000

Le calcul du décalage pour le dernier uint32 est simple:

Y' = Y << 5;     // rmq les 5 premiers bits de Y disparaissent

Quel calcul donne la nouvelle valeur du premier? On a besoin de décaler à droite Y pour calculer X' ...

Theo_0055 · Answer

Bonjour,j'ai pas encore fait le décalage mais j'ai essayé de faire l'addition sauf que je vois pas pourquoi mon programme ne marche pas

/*Donne la valeur du bit a la position x dans le grand entier pointé par e et doit retourne un char*/
char ge_get_bit(tall_int_t *e, uint32_t x) {
  return ( ((e->data[x/32] >> (x%32)) & 1)!=0 );
  
}

grand_entier_t *ge_add(grand_entier_t *b, grand_entier_t *a) {
    
    tall_int_t *resultat=ge_cree();
   
    size_t taille_max_octet;
    if (a->size > b->size)
       taille_max_octet = a->size;
    else
       taille_max_octet = b->size;
    
    resultat->size=taille_max_octet;
    resultat->data =realloc(resultat->data,sizeof(uint32_t)*taille_max_octet);
    if (!resultat->data) {
        free(resultat);
        return NULL;   
    } 
    int index_bit;
     int retenue=0;
  
    for(index_bit=0;index_bit<taille_max_octet*32;index_bit++){
        int bit =ge_get_bit(a, index_bit)+ge_get_bit(b, index_bit)+retenue;
     
        if (bit ==1 || bit==3)
           ge_set_bit(resultat, index_bit);
        else
            ge_clr_bit(resultat, index_bit);

retenue=ge_get_bit(a, index_bit) & ge_get_bit(b, index_bit);
  
    }
    return resultat;
}

Dalfab · Answer

Tout d'abord la taille réservée pour résultat est insuffisante. Ça n'est la taille du plus grand, c'est peut-être un de plus. Par exemple 3 millions tient dans un seul uint32, mais 3 millions + 2 millions demande d'allouer 2 uint32.

Le calcul de la retenue n'est pas bon. Encore un exemple : 1 + 0 + retenue1 va donner bit=2 et devrait donner retenue=1. J'écrirais plutôt : retenue = bit >= 2;.

Que se passe-t-il si si on appelle ge_get_bit() pour lire le 100ième bit d'un objet n'ayant qu'un seul uint32? Tu peux être dans ce cas si tu ajoute un nombre de 128bits à un nombre de 32bits. Il te faut un test supplémentaire ou garantir que la fonction retourne 0 dans ce cas.

Je ne peux pas juger de la validité de ge_set_bit() et ge_clr_bit().

On pourrait travailler en ajoutant directement 2 uint32 + uint32 sans passer par les bits. La subtilité est alors : comment déterminer s'il y a retenue?

Theo_0055 · Answer

J'ai testé set bit bit et clear bit et ça marche grand_entier_t *ge_set_bit(grand_entier_t *e, uint32_t x) { e->data[x/32] |= (1 << (x % 32)); return e; } grand_entier_t *ge_clr_bit(grand_entier_t *e, uint32_t x) { e->data[x/32] &= ~(1 << (x% 32)); return e; } Ah oui c'est vrai on a comme retenue 1 si on a bit qui est égale a soit 2 soit 3 merci pour la retenue j'ai compris

Theo_0055 · Answer

Je pense que le faire comme vous dites sera plus simple:

"On pourrait travailler en ajoutant directement 2 uint32 + uint32 sans passer par les bits. La subtilité est alors : comment déterminer s'il y a retenue?"

Moi je sais quepar si on a bit (addition bit  et b)> aux 2 bits additionné(a et b) alors on a retenue qui vaut 0 sinon 1

C'est une autre façon que j'ai pensé mais est elle compatible avec ce que vous avez dit?

Dalfab · Answer

Pour travailler non pas bit par bit mais uint32 par uint32, il faut faire attention à la retenue. Je donne un code qui contourne le problème en trichant un peu (l'addition de 2 uint32 risque d'avoir un dépassement de capacité, j'utilise un type plus grand.) uint32 retenue = 0; for ( int index_mot = 0 ; index_mot < taille_max_octet ; index_mot++ ) { uint64 somme = retenue; if ( index_mot < a->size ) // faire des additions de plus de 32 bits somme += a->data[index_mot]; if ( index_mot < b->size ) somme += b->data[index_mot]; retenue = somme >> 32; // le reste est ce qui est au dela d'un uint32 resultat->data[index_mot] = (uint32)somme; // garder la partie qui tient dans uint32 } if ( retenue > 0 ) { // il reste retenue, resultat est trop petit resultat->size++; resultat->data = realloc( resultat->data , resultat->size * sizeof(uint32) ); resultat->data[resultat->size-1] = retenue; }

Theo_0055 · Answer

esceque vu que on additionne 2 uint32 la taille max octet vaut 2 (equivalent de 2 uint32 soit 64 biit)?

Pour la retenue en general elle est pas cense etre plutot a gauche car on propage la retenue a gauche et non à droite

Pourquoi dans les additions binaires il y a toujours des décalages a faire?

if ( retenue > 0 ) je pense que c'est la me*me chose qu'écrire if ( retenue )

Theo_0055 · Answer

Ca marche pas grand_entier_t *ge_add(grand_entier_t *b, grand_entier_t *a){ grand_entier_t *resultat=ge_cree(); size_t taille_max_octet; if (a->size > b->size) taille_max_octet = a->size; else taille_max_octet = b->size; resultat->size=taille_max_octet; resultat->data =realloc(resultat->data,sizeof(uint32_t)*taille_max_octet); if (!resultat->data) { free(resultat); return NULL; } uint32_t retenue = 0; for ( int index_mot = 0 ; index_mot < taille_max_octet ; index_mot++ ) { uint64_t somme = retenue; if ( index_mot < a->size ) // faire des additions de plus de 32 bits somme += a->data[index_mot]; if ( index_mot < b->size ) somme += b->data[index_mot]; retenue = somme >> 32; // le reste est ce qui est au dela d'un uint32 resultat->data[index_mot] = (uint32_t)somme; // garder la partie qui tient dans uint32 } return resultat; } bizarrement ça n'ajoute pas le b->data[index_mot] dans somme

Dalfab · Answer

Je ne sais pas.
En cas tout, ce que je vois est que tu appelles ge_add() mais ne récupère pas son résultat! A quoi bon appeler la fonction?

Theo_0055 · Answer

je vois pas ce que vous voulez dire.Vous dites que je ne récupére pas mon résultat.Pourtant,je l'ai mis dans ma variable resultat

Theo_0055 · Answer

pourtant le resulat est dans la varaibale resultat

Opérations de base sur les bits

25 réponses

Votre réponse

Discussions similaires