Décalage/Multiplication de bit

Je crois pouvoir aider sur ce problème. D'abord, une évidence: A * B == B * A
On peut vouloir optimiser en choisissant le rôle de chaque nombre. On peut vouloir réduire le nombre de décalages et d'additions.
On pourrait compter le nombre de bits égaux à 1 et se servir du nombre ayant le moins de bits (ici B)
Le nombre de bits du produit de deux nombres est au plus égal à la somme des nombres de bits des deux nombres.
On peut donc réserver la somme des espaces pour le produit, quitte à en faire sauter à la fin.
On commence par créer un _accumulateur_ égal à tous des zéros.
Supposons que je choisis de décaler A en fonction des bits de B.
Je cherche le premier bit de B à partir de 0 qui soit égal à 1.
Je décale A vers la gauche du nombre de positions qui sépare le bit 1 de B à partir de la position précédente
(0 au début).
J'additionne cette valeur décalée de A à l'accumulateur.
Je recommence en cherchant le bit 1 suivant de B et je calcule la _différence_ des positions.
Et je reviens au décalage de A.
Le processus s'arrête quand je suis rendu au delà de la limite de B
Ce sera un avantage de compter le nombre de bits à 1. Si B==0, on aura 0 bit, et le résultat est l'accumulateur
(0 en partant).

bonjour,

Peux-tu partager le code de ge_set_bit()?

Je ne pense pas que le décalage à droite fasse partie de ton exercice.

Les nombres négatifs font-ils partie de ton exercice?

En fait ils ont dit ce n'est pas obligatoire mais si vous vouliez le faire faites le

tall_int_t *ge_set_bit(grand_entier_t *e, uint32_t x) {
    e->data[x/32] |= (1 << (x % 	32));
    return e;
}

Par exemple si on dit mettre le bit 100 a 1 alors que mon grand entier sa taille est de par exemple 64 bits

je pense que il faut que j’.augmente avec un realloc mon entier de 64 bits de 100-64 bits supplémentaires 

Pour la multiplication j'ai essayé de faoire ceci.Lorsque je compile ça me renvoie pas d'erreur sauf que le résulat est faux ,j'ai essayé de débugger mais je sis toujours pas ce qui cloche

int ge_nb_bits(grand_entier_t *e) {
  
  return e->size*32;
}

tall_int_t *ge_shift(tall_int_t *a, int nb_bits) {
    if(nb_bits>=0){
       grand_entier_t *resultat=ge_cree();
       int index_bit;
       for(index_bit=ge_nb_bits(a)-1 ; index_bit >= 0 ; index_bit--){
          if(ge_get_bit(a, index_bit)){
             resultat = ge_set_bit(resultat, index_bit+nb_bits);
          }
       }
       return resultat;
    }
    return NULL;
}


tall_int_t *ge_mul(tall_int_t *b, tall_int_t *a) {
    int i, j;
  
    uint32_t max=(a->size > b->size)?a->size:b->size;
    

     /*On a donc effecté comme décalge le nombre de bit de a et la taille de l'entier résultat de la 
     multiplication est la taille du plus grand en  taille entre a et b + le nombre de décalage */
    int size =max-1;
    grand_entier_t *res = ge_cree();
    if (!res) return NULL;

        res->data = realloc(res->data, size * sizeof(uint32_t));
        if (!res->data) {
            ge_libere(res);
            return NULL;
        }
    
    uint32_t somme=0;
    grand_entier_t *res_final=ge_cree();
    for (i = 0; i < max; i++) {
       
       for(j = 0; j < max; j++){
           res->data[i] = a->data[i] * b->data[j];
       }
       
       if(i>=1)//car on commence a décaler qu'a l'étape 2 donc ici pour i>=1
         res=ge_shift(res,max);
       somme+=res->data[i];
    }
    res_final->data=&somme;
    return res_final;
}

Oula j'avais espoir de faire la multiplication sans utiliser l'addition.Mon addition elle marche pas tres bien et me renvoie toujours un 0 sur 32 bits

J'ai essayé de débugger avec gdb a plusieurs reprises mais j'arrive pas a trouver le soucis.J'en suis sur que mon addition est presque bonne

char ge_get_bit(grand_entier_t *e, uint32_t x) {
  return ( ((e->data[x/32] >> (x%32)) & 1)!=0 );
  
}


tall_int_t *ge_add(tall_int_t *b,tall_int_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;
}

Merci pour votre aide.J'ai laisse tomber car j'arrivais pas

Merci quand meme

J'ai écrit presque tout mon code hier soir (cette nuit pour vous car je suis en Amérique).
C'est pas trop compliqué et pas trop long (environ 125 lignes).
On dit que je suis un "one-liner". J'écrit plus condensé que d'autres, mais clairement tout de même.
Les fonctions principales sont:
+ shifter()  Qui décale un des registres.
+ adder()  Qui additionne deux registres de même longueur.
+ bfind()  Qui cherche le prochain bit à 1 dans un registre.
+ product()  Qui fait le produit de deux registres pouvant être de longueurs différentes.
Et les fonctions accessoires:
+ regis()  Qui crée un registre et l'initialise à 0.
+ allocate()  Qui appelle malloc() avec vérification.
Pour faciliter mes tests, mes registres contiennent des uint8_t au lieu des uint32_t pour pouvoir travailler avec des uint64_t.
J'ai paramétrisé mon code avec des #define pour passer facilement de l'un vers l'autre.
J'entre des nombres d'au plus 32 bits et je les convertis en registres. J'ai les fonctions:
+ convert()  Qui convertis un 32 bits en registre.
+ restore()  Qui reconvertis un registre en uint64_t
Jusqu'ici, mes tests fonctionnent.
Je ne sais pas si je pourrai publier mon code car je suis aveugle et j'utilise mon ordi avec une synthèse vocale.
Ma synthèse ne me permet pas d'avoir accès à la barre d'outils à laquelle on accède probablement avec la souris.

Ah vraiment merci pour tous vos efforts juste pour m'aider,c'est admmirable

Mais comment pouvez vous lire mon message et tout vu que vous etes aveugle,disons je m'y connais pas trop sur le sujet

Il ya certains fonctions auxiliaires que vous avez fait que je ne comprend pas l'utilité.Je pense que la multiplication qu'on me demande est plus simple meme si j'ai pas réussi

Mais quand me^me je suis curieux de ce que fait votre code

J'ai parlé de synthèse vocale. C'est un logiciel qui analyse le contenu de l'écran et qui simule la voix humaine. C'est "presque" humain.
Si je fais Flèche-Bas, elle dit toute la ligne. Insert+Flèche-Droite, le mot suivant, ...
Je peux lire un caractère à la fois. C'est dans ce mode seulement que je peux savoir s'il y a des majuscules.
En effet, elle les CRIE plutôt que les dire...
Si l'éditeur fonctionnait directement en Markdown, je pourrais colorer mon code et même beaucoup plus.
C'est ce qui se passe sur le site ZesteDeSavoir.
Si tu utilises des uint32_t, je ne vois pas comment tu peux faire des additions bit-à-bit.
Je prend tout de même la chance de poster mon code en espérant qu'un modérateur charitable le convertira adéquatement.
-
// Multiplication par décalages et additions successives dans des pseudo-registres.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
 
#define TYPE uint8_t   // Type des éléments des registres.
#define SIZE (sizeof(TYPE) * 8)
 
typedef struct {
    size_t size;
    TYPE *data;
} Tall;
 
// Affichage dans le bon ordre.
void display(Tall *reg) {
    printf("[%d]={", reg->size);
    char *s = "";
    for(int i = reg->size-1; i >= 0; s=", ", i--) printf("%s%02X", s, reg->data[i]);
    printf("}\n");
}
 
// Demande de mémoire avec validation.
void *allocate(size_t size) {
    void *area = malloc(size);
    if(area)   return area;
    perror("malloc");
    fprintf(stderr, "Required: %d\n", size);
    exit(EXIT_FAILURE);
}
 
// Décalage d'un registre (ne peut être supérieur à la longueur du registre en bits).
void shifter(Tall *reg, int shift) {
    int ws = shift / SIZE;
    for(int i = reg->size-1; i >= ws; i--)   reg->data[i] = reg->data[i - ws];
    for(int i = ws-1; i >= 0; i--)   reg->data[i] = 0;
    shift %= SIZE;
    if(shift == 0)   return;
    TYPE mask = (1<<shift) - 1;
    TYPE before = 0;
    for(int i = ws; i < reg->size; i++) {
        TYPE after = (reg->data[i]>>(SIZE-shift)) & mask;
        reg->data[i] = (reg->data[i] << shift) | before;
        before = after;
    }
}
 
// Addition de deux registres de même longueur.
void adder(Tall *acc, Tall*reg) {
    TYPE carry = 0;
    for(int i = 0; i < acc->size; i++) {
        TYPE res = acc->data[i] + reg->data[i] + carry;
        TYPE max = (acc->data[i] > reg->data[i]) ? acc->data[i] : reg->data[i];
        carry = (max > res) ? 1 : 0;
        acc->data[i] = res;
    }
}
 
// Création d'un registre et initialisation à zéro.
Tall *regis(size_t size) {
    Tall *reg = allocate(sizeof(Tall));
    reg->size = size;
    reg->data = allocate(sizeof(TYPE) * size);
    for(int i = 0; i < size; i++)   reg->data[i] = 0;
    return reg;
}
 
// Recherche du prochain bit à 1 dans un registre à partir de la position donnée.
size_t bfind(Tall *reg, int shift) {
    size_t limite = reg->size * SIZE;
    while(shift < limite) {
        if((reg->data[shift/SIZE]>>(shift%SIZE))&1)   return shift;
        shift++;
    }
    return shift;
}
 
// Conversion d'un nombre en registre.
Tall *convert(uint64_t num) {
    Tall *reg = regis(sizeof(uint32_t) / sizeof(TYPE));   // Je me limite à 32 bits pour les tests.
    uint64_t mask = (1<<SIZE) - 1;   // SIZE doit être inférieur à 64.
    for(int i=0; i<reg->size; i++) {
        reg->data[i] = num & mask;
        num >>= SIZE;
    }
    return reg;
}
 
// Restaurer un nombre à partir d'un registre (pourvu que le type du nombre soit assez grand).
uint64_t restore(Tall *reg) {
    uint64_t num = 0;
    for(int i = reg->size-1; i >= 0; i--)   num = (num<<SIZE) + reg->data[i];
    return num;
}
 
// Produit de deux registres pouvant être de longueurs différentes.
Tall *product(Tall *rg1, Tall *rg2) {
    Tall *acc = regis(rg1->size + rg2->size);
    Tall *reg = regis(acc->size);
    for(int i = 0; i < rg1->size; i++)   reg->data[i] = rg1->data[i];
    int s = -1;
    int p = 0;
    int limit = rg2->size * SIZE;
    while(1) {
        s = bfind(rg2, s+1);
        if(s >= limit)   break;
        shifter(reg, s-p);
        p = s;
        adder(acc, reg);
    }
    free(reg);
    return acc;
}
 
// Programme principal ...
int main(void) {
    puts("Nombre 1 ");
    uint64_t nb1;
    scanf("%lld", &nb1);
    puts("Nombre 2 ");
    uint64_t nb2;
    scanf("%lld", &nb2);
    uint64_t res = restore(product(convert(nb1), convert(nb2)));
    printf("%lld %s %lld (%lld * %lld)\n", res, ((res==nb1*nb2) ? "égal" : "différent"), nb1*nb2, nb1, nb2);
    return 0;
}

Attention @Theo_0055, ce code n'est pas exempt d'erreurs.
Par exemple essaie d'entrer : 65530 65530, il va s'auto-diagnostiquer par "4294049828 différent 4294180900 (65530 * 65530)", indiquant un bug! 

De plus il me semble qu'il ne correspond pas à ton exercice, car ne gère pas des nombres de tailles différentes.
Il faut le prendre comme un exemple à comprendre, pas comme une solution.

Oui ca correspond pas du tout a mon exo en effet.Mais peut etre je peux m'inspirer

Ah donc sa solution ne marche pas a 100%,pourrant elle me semblait correct,ou se trouve l'erreur dans son code ?car il me semblait correct

J'ai en effet constaté l'erreur. Je n'ai pas encore pris le temps de vérifier où elle se trouve.
Je me doute que c'est dans la fonction adder() à cause du carry, mais je n'en suis pas certain.
@Theo_0055:
Peux-tu reformuler autrement ton problème?
Est-ce que chaque position du champs "data" ne devrait contenir qu'un seul bit?
Tu parles de produit par décalage et additions successives. C'est bien ce que je fais.
C'est de cette façon que le faisaient les anciens ordinateurs.

L'erreur est bien dans adder(). On ne peut pas ajouter 3 termes et retrouver ensuite s'il y a eu dépassement de capacité. Il faut décomposer en 2 additions et tester 2 fois s'il y a eu carry.

L'énoncé est dans l'autre forum

On ne peut pas déborder deux fois:
    255 + 255 = 510 -> 1 | 254 + carry <= 25

Voici ma correction:
void adder(Tall *acc, Tall*reg) {
    TYPE carry = 0;
    for(int i = 0; i < acc->size; i++) {
        TYPE res = acc->data[i] + reg->data[i];
        TYPE max = (acc->data[i] > reg->data[i]) ? acc->data[i] : reg->data[i];
        acc->data[i] = res + carry;
        carry = (max > res) ? 1 : 0;
    }
}

Ah d’accord  j’ai compris Thanks