opération bits à bits

a marqué ce sujet comme résolu.

Bonjour, je devais réaliser 4 fonctions qui effectuent des opérations bits à bits , pouvez-vous m’aider s’il vous plaît :):

  • la première fonction s’appelle :
typedef unsigned long long Mot64;

int equiv_rotation(Mot64 x, Mot64 y)

elle vérifie si les premiers bits du premier nombre sont les mêmes que le deuxième à une rotation près par exemple sur 8 bits, les nombres 01110010 et 01001110 sont les mêmes par une rotation de 3 bits vers la droite : 0110010 ->01001110

  • la deuxième fonction s’appelle :
int plus_long_suffixe(Mot64 x , Mot64 y)

La fonction renvoie la taille du plus grand suffixe commun dans l’ecriture binaire des deux nombres par exemple : 0100110 et 0101110 ont comme plus grand suffixe commun les 3 bits 110

  • la troisieme fonction s’appelle :
int nb_101(Mot64 x)

La fonction est paramétrée par un nombre de 64 bits et qui renvoie le nombre de fois que l’on peut rencontrer un bit à 1 suivi d’un 0, lui-même suivi d’un 1. Par exemple, la fonction appelée avec le nombre 11011101010…0 renvoie 3 à cause des trois occurrences 11011101010…0, 11011101010…0 et 11011101010…0 du motif 101.

  • la dernière fonction s’appelle:

int Harming(Mot64 x , Mot64 y )

La fonction est paramétrée par deux nombres de 64 bits et qui renvoie le nombre de leurs bits qui sont différents, position par position. Par exemple, la fonction appelée avec les nombres 110010…0 et 011010…0 renvoie 2.

int equiv_rotation(Mot64 x , Mot64 y){
    int cmpt = 1;
    for(int i = 0 ; i < 64 ; i++){
        if((y << 1) & 1 == (x >> 1) & 1 ) --cmpt;
        else{
            if(cmpt <= 0) return 1;
            return 0;
        }
        x = x >> 1 ; 
        y = y << 1 ;
    }
    return 1;
}

int plus_grand_suffixe(Mot64 x , Mot64 y ){
    if(x & 1 != y & 1) return 0;
    return 1 + plus_grand_suffixe(x >> 1 , y >> 1 );
}

int Harmin(Mot64 x , Mot64 y){
    int cmpt = 0;
    for(int i = 0 ; i < 64 ; i++){
        if(x & 1 != y & 1) ++cmpt;
        x = x >> 1 ;
        y = y >> 1 ;

    }
    return cmpt ; 

}

int nb_101(Mot64 x){
    Mot64 res = 0;
    int cmpt = 3;
    nbtotal = 0;
    for(int i = 0 ; i < 64 ; i++){
        res |= ((x>> 1) & 1) << 1;
        --cmpt ; 
        if(cmpt == 0){
            if(res == 5) ++nbtotal;
            res = 0;
        }
        x = x >> 1 ;
    }
    return nbtotal;

    }

Je vous remercie d’avance.

Voici un petit code qui te donne quelques astuces pour écrire tes fonctions.

#include <stdio.h>
typedef unsigned long long MOT64;
int main(void) {
    MOT64 x =5;
    MOT64 y = x;
    y = y<<(64-3);
    x = x>>3;
    y = x | y;
    printf("%016llX\n", y);
    x = 1llu<<63;
    x = x>>4;
    printf("%016llX\n", x);
    MOT64 m =0;
    m = ~m;
    printf("%016llX\n", m);
    m = (1llu<<4) - 1;
    printf("%016llX\n", m);
    m = ~m;
    printf("%016llX\n", m);
    int s = -136;
    s = (s % 64 + 64) % 64;
    printf("%d\n", s);
}

Qui donne:

A000000000000000                                                                                                        
0800000000000000                                                                                                        
FFFFFFFFFFFFFFFF                                                                                                        
000000000000000F                                                                                                        
FFFFFFFFFFFFFFF0                                                                                                        
56                                                                                                                       

Un décalage n’est jamais circulaire dans une simple instruction. Le premier test montre comment faire un décalage circulaire de 3 vers la droite. Le second test montre que le bit de signe n’est pas étendu pour un uint64. Le test suivant montre comment faire un masque de 64 bits. Ensuite un masque de 4 bits à droite (on pourrait le décaler de 60 pour le placer à gauche). Le test suivant nous donne le masque complémentaire. Enfin, il faut faire attention aux décalages supérieurs à 64 ou négatifs. Je montre comment calculer le décalage positif associé à un décalage trop grand ou négatif.

Notons qu’un décalage circulaire de S vers la droite (gauche) est équivalent à un décalage circulaire de 64-S vers la gauche (droite) pour un nombre de 64 bits.

Bien sûr, le décalage peut se faire en une seule instruction:

    MOT64 x =5;
    int r = 3;   // right shift
    x = (x>>r) | (x<<(64-r));

Si on veut un décalage vers la gauche par défaut, il faut interchanger les opérateurs << et >>.

Pour ta fonction:

int Harmin(Mot64 x , Mot64 y){

Je ferais directement le ou exclusif (XOR = ^) de tes deux nombres. On aura des 1 aux positions différentes. On compte ensuite le nombre de 1 dans ce résultat.

Pour ta fonction

int plus_grand_suffixe(Mot64 x , Mot64 y ){

Que se passe-t-il si les nombres sont identiques? Une boucle infinie!

Fais-le en séquenciel sur une boucle de 64.

L’énoncé de la fonction

int equiv_rotation(Mot64 x , Mot64 y){

n’est pas clair pour moi. Je garderait la boucle et je comparerais les deux nombres au complet. Si c’est égal, je retourne la valeur de l’indice i. Sinon, je décale de façon circulaire un seul des deux nombres de une position. Si je me rend à la fin, dois-je retourner -1?

+2 -0

Pour nb_101 l’idée est, je pense de prendre les trois premiers bits puis de comparer à 5 ((x & 7) == 5). Ensuite, tu décales le nombre d’un (x >>= 1) et tu continues.

Tu peux même faire ça avec une boucle while jusqu’à ce que le nombre soit différent de 0.

Aussi, tu n’as pas défini de type pour la variable nbtotal.

Je n’ai pas bien compris ce que tu essaies de faire avec res mais j’ai le sentiment que ça ne marchera pas car res est une combinaison (OU logique) avec des nombres pairs et on voudrait le comparer à 5 qui est impaire.


Aussi, fait très attention à la priorité opératoire des opérateurs bits à bits.


int plus_grand_suffixe(Mot64 x , Mot64 y ){
    if(x & 1 != y & 1) return 0;
    return 1 + plus_grand_suffixe(x >> 1 , y >> 1 );
}

Malheureusement ici, la première opérateur faite est 1 != y, on doit donc mettre des parenthèses.

int plus_grand_suffixe(Mot64 x , Mot64 y ){
    if((x & 1) != (y & 1)) {
      return 0;
    }
    return 1 + plus_grand_suffixe(x >> 1 , y >> 1 );
}

Comme ça a déjà été dit, tu dois également gérer le cas terminal (0, 0). Or, ce cas n’est pas différenciable de si on avait entrer (0, 0) (qui doit retourner 64). Le plus simple ici est d’abandonner la récursion, mais tu peux également rajouter un paramètre si tu souhaites conserver la récursion (ce que je ne te recommence pas).

+2 -0

Pour trouver le plus grand suffixe, on peut faire un XOR des deux nombres et chercher où se trouve le premier 1 en partant de la droite.

int plus_grand_suffixe(MOT64 x, MOT64 y) {
    x = x ^y;
    for(int i = 0; i < 64; i++) {
        if(x&1) return i;
        x >>= 1;
    }
    return 64;
}y)

+1 -0

Pour nb_101 je voulais ajouter 3 fois chaque bit de x dans res et si res = 101 alors j’incrémente nb_total et je recommence l’opération

Pour equiv_rotation il faut comparer les premiers bits x avec les derniers bits de y du coup, j’effectue une rotation gauche pour récupérer le premier bit de y est une rotation à droite pour récupérer le dernier bit de x puis je les compare c if((y << 1) & 1 == (x >> 1) & 1 ) --cmpt; (comme je ne savais pas comment obtenir les bits que je voulais pour x et y ) j’ai mis un compteur qui est décrémenté pour savoir s’ils ont au moins un bit en commun.

j’en profite pour poser une question quand on fait cette opération (x & 7) on obtient les 3 premiers chiffres ???

Pour nb_101 je voulais ajouter 3 fois chaque bit de x dans res et si res = 101 alors j’incrémente nb_total et je recommence l’opération

Il me semble que ((x>> 1) & 1) << 1 est équivalent à x & 2 et donc que la valeur est soit 2, soit 0.
Tu avais donc une stratégie qui ne marchait pas selon moi. Essaye plutôt avec & 7 (tu vois pourquoi ?) et redonne nous tes fonctions corrigées de manière à ce qu’on puisse vérifier que tu as bien fait les bonnes corrections.

Sinon, je l’ai loupé tout à l’heure mais ta fonction Hamming me semble presque correcte. Tu as juste un problème de priorité opératoire encore sur if(x & 1 != y & 1) qui devrait être if((x & 1) != (y & 1))

+1 -0

Pour ta fonction equiv_rotation, Tu pourrais utiliser le décalage circulaire vers la droite de 1 pour x seulement et comparer globalement les deux nombres. Tu répètes dans une boucle jusqu’à 64 fois. C’est nettement plus simple.

Pour la fonction nb_101, utilises le truc de ache. Si tu as un match, tu décales de 3, sinon tu décales de 1. Pas besoin de décalage circulaire ici. Assures-toi que tu ne décales pas plus que 64.

+0 -0

J’ai écrit une version un peu plus tordue de Harmin dans laquelle je prend les bits 4 à la fois et je retrouve dans une table le nombre de bits à 1 de chaque groupe.

int Harmin(MOT64 x, MOT64 y) {
    int bits[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
    x = x ^ y;
    int count = 0;
    for(int i = 0; i < 16; i++) {
        count += bits[x&15];   // 15 = 1111
        x >>= 4;
    }
    return count;
}
+0 -0

@PierrotLeFou: On aime pas trop donner des codes tous fait sur le forum. :/ D’habitude on préfère essayer d’indiquer l’OP vers la solution.

En plus ton code n’est pas très détaillé, je le comprends mais il est loin d’être évident.

+0 -0

J’ai bien essayé au début de donner des indications pour aider l’auteur. Mais je n’ai pas écrit les quatre foncions tels qu’il les attendait.

J’avoue que ce dernier code n’est pas clair. Il contient cependant l’indice majeur dont l’autteur 45K devrait se servir pour écrire ses propres versions.

Devrais-je vraiment mieux expliquer et/ou commenter ce dernier code?

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte