Comment puis-je corriger le code suivant concernant les trames de bits correspondantes?

Question

J'ai été chargé d'écrire une fonction appelée bitpatSearch() qui cherche un modèle de bit spécifié à l'intérieur d'un unsigned int. La fonction doit prendre 3 arguments: bitpatSearch(source, pattern, n). Il doit rechercher l'entier source pour les bits n les plus à droite de pattern et afficher le nombre de bits où le motif commence (en supposant 0 à 31 bits pour un entier de 32 bits) s'il y a correspondance et -1 s'il n'y a pas de correspondance.

Bien que l'exercice recommandé de rechercher à partir du bit le plus à gauche, mon code recherche à partir du plus à droite, comme je pensais que ce serait plus facile (comme je le pouvais ET valeurs avec 1.) Cependant, quelque chose ne va pas, et je soupçonne que l'arithmétique derrière l'instruction return peut être un problème, mais ne peut pas tout à fait comprendre.

Le programme semble toujours obtenir la position erronée, mais me dit toujours correctement s'il y a une correspondance.

#include <stdio.h> 

int bitpatSearch(unsigned int source, unsigned int pattern, int n){ 

unsigned int count, x, sourceCopy; 

for(count = 0; count <= 32; ++count){ //loop for all possible shifts for a 32 bit integer 

    x = 0; 

    sourceCopy = source >> count; 

    while(((sourceCopy & 1) == (pattern & 1)) && (x != n)){ 

     sourceCopy >>= 1; 

     pattern >>= 1; 

     ++x; 

     } 

    if(x == n) //then there is a match 

    return 32 - (count + n); // I think the problem is here, with basic arithmetic 

} 

return -1; 

} 

Answer 1

Vous ne pouvez pas déplacer un 32 bits unsigned int de 32, il est pas défini. Changer la boucle pour arrêter avant 32:

for (count = 0; count < 32; ++count) 

Ou mieux, en font une boucle sur la taille du type de votre système, ce qui pourrait être différent de 32:

#include <limits.h> 

... 

for (count = 0; count < sizeof(source) * CHAR_BIT; ++count) 

En ce qui concerne votre algorithme, si vous êtes censé chercher à partir du bit le plus significatif, faites cela! Sinon, vous risquez de ne pas trouver la position attendue si le motif est présent plus d'une fois. Notez qu'il est très déroutant de parler de numéros de bits sans une définition précise du système de numérotation: le bit 0 est-il le bit le plus à gauche (le plus significatif) ou le plus à droite (le moins significatif)? En C, il est courant de numéroter les bits du plus petit au plus significatif, car cela est cohérent avec l'opérateur de décalage (le bit n a la valeur 1U << n), mais certaines personnes sont utilisées pour numéroter des bits de gauche à droite, exactement le convention contraire.

Answer 2

S'il vous plaît noter que la numérotation des bits est généralement de droite à gauche, où le dernier bit est le bit 0.

Votre code est très compliqué. Les boucles imbriquées ne sont pas nécessaires. Voici une solution facile pour votre problème (recherche de modèle est de droite à gauche):

(EDIT:. Code inclut désormais des améliorations comme le suggère Paul Hankin et underscore_d)

#include <stdio.h> 
#include <limits.h> 

#define NO_MATCH -1 
#define ARGUMENT_ERROR -2 

#define DEBUG 

int bitpatSearch(unsigned int source, unsigned int pattern, unsigned int n) { 
    unsigned int mask; 
    unsigned int tmp; 
    int i; 

    /******************************************************************** 
    * Three trivial cases: 
    * 
    * (a) If n = 0, then every pattern is a match; so return 0 
    *  (match at position 0). 
    * (b) If n = CHAR_BIT * sizeof(source), then there is a match at 
    *  position 0 if source equals pattern and no match otherwise. 
    * (c) If n > CHAR_BIT * sizeof(source), it makes no sence to test 
    *  for matching patterns, because we don't know the 
    *  n - CHAR_BIT * sizeof(source) most significant bits. 
    *******************************************************************/ 
    if (n == 0) 
    { 
     return 0; 
    } 
    if (n == CHAR_BIT * sizeof(source)) { 
     if (source == pattern) { 
      return 0; 
     } 
     return NO_MATCH; 
    } 
    if (n > CHAR_BIT * sizeof(source)) { 
     return ARGUMENT_ERROR; 
    } 

    mask = ~((~0u) << n); 
    pattern &= mask; 

    #ifdef DEBUG 
    printf("mask = 0x%08x\n", mask); 
    printf("pattern = 0x%08x\n", pattern); 
    #endif 

    for (i = 0; i <= CHAR_BIT * sizeof(source) - n; i++) { 
     tmp = (source >> i) & mask; 
     #ifdef DEBUG 
     printf("tmp  = 0x%08x at position %2i:\n", tmp, i); 
     #endif 
     if (tmp == pattern) { 
      #ifdef DEBUG 
      printf("Match at position %2i!\n", i); 
      #endif 
      return i; 
     } 
    } 

    return NO_MATCH; 
} 

int main() { 
    int result; 

    /* 
    dec 243 = bin 11110011 
    dec 9 = bin 1001 
         ^match at position 1 
    */ 

    result = bitpatSearch(243, 9, 4); 
    printf("Result = %i\n", result); 

    return 0; 
} 

Answer 3

Vous détruire partiellement pattern en la boucle while interne en la décalant lorsque les bits sont appariés. Donc, si vous obtenez une correspondance partielle, alors pattern ne contiendra plus la valeur correcte pour les recherches suivantes. Un exemple que votre code se trompe est bitpatSearch(0xf0f, 0xff, 8). Votre code trouve une correspondance à la position 12, mais il n'y a aucune correspondance nulle part.

j'écrire le code comme ceci:

#include <limits.h> 

#define INT_BITS (CHAR_BIT * sizeof(unsigned)) 

int bitpatSearch(unsigned int source, unsigned int pattern, int n){ 
    if (n == 0) return 0; 
    if (n > INT_BITS) return -1; 
    if (n == INT_BITS) return source == pattern ? 0 : -1; 
    pattern &= (1u << n) - 1; 
    for (int i = 0; i <= INT_BITS - n; i++) { 
     if (((source >> i) & ((1u << n) - 1)) == pattern) { 
      return i; 
     } 
    } 
    return -1; 
} 

Contrairement à votre code, cette tente de faire correspondre l'intégralité pattern à une valeur de décalage donnée dans source d'un seul coup, et est portable comme doesn Ne supposez pas que int est une taille particulière.

Le code travaille dur pour éviter un comportement indéfini; en évitant spécifiquement les changements par INT_BITS ou plus. Par exemple, le cas if (n == INT_BITS) return source == pattern ? 0 : -1; est nécessaire pour éviter un décalage illégal lors de la construction du masque (1u << n) - 1.

Voici quelques tests unitaires simples pour le code. Certains des cas de test supposent un int de 32 bits parce que j'étais trop paresseux pour les rendre portables.

#include <stdio.h> 

int main(int argc, char **argv) { 
    struct { 
     unsigned source, pattern; 
     int n; 
     int want; 
    } test_cases[] = { 
     { 0x0000000fu, 0xf, 4, 0 }, 
     { 0x0000000fu, 0xf, 2, 0 }, 
     { 0xf0000000u, 0xf, 4, 28 }, 
     { 0xf0000000u, 0xf, 2, 28 }, 
     { 0x01000000u, 0x1, 4, 24 }, 
     { 0x80000000u, 0x1, 1, 31 }, 
     { 1u << (INT_BITS - 1), 0x1, 2, -1 }, 
     { 0xffffffffu, 0x6, 3, -1 }, 
     { 0x777u, 0x77, 12, 4 }, 
     { 0x1234abcdu, 0x1234abcdu, 32, 0 }, 
     { 0x1234abcdu, 0x1234abcdu, 33, -1 }, 
     { 0x1234abcdu, 0x42u, 0, 0 }, 
     { 0xf0f, 0xff, 8, -1}, 
    }; 

    int failed = 0; 
    for (int i = 0; i < sizeof(test_cases)/sizeof(test_cases[0]); i++) { 
     unsigned source = test_cases[i].source; 
     unsigned pattern = test_cases[i].pattern; 
     int n = test_cases[i].n; 
     int want = test_cases[i].want; 
     int got = bitpatSearch(source, pattern, n); 
     if (got != want) { 
      printf("bitpatSearch(0x%x, 0x%x, %d) = %d, want %d\n", source, pattern, n, got, want); 
      failed = 1; 
     } 
    } 
    return failed ? 1 : 0; 
} 

Answer 4

Vous devez créer une copie de pattern parce que chaque fois que vous entrez dans la boucle while vous changez la valeur de pattern. Donc, la prochaine fois que vous entrez dans la boucle while, vous allez comparer avec un mauvais modèle.

#include <stdio.h> 

int bitpatSearch(unsigned int source, unsigned int pattern, int n){ 

unsigned int count, x, sourceCopy,patternCopy; 

for(count = 0; count <= 32; ++count){ //loop for all possible shifts for a 32 bit integer 

    x = 0; 

    sourceCopy = source >> count; 
    patternCopy=pattern; 

    while(((sourceCopy & 1) == (patternCopy & 1)) && (x < n)){ 


     sourceCopy >>= 1; 

     patternCopy >>= 1; 

     ++x; 
     } 

    if(x == n) //then there is a match 

    return 32 - (count + n); // I think the problem is here, with basic arithmetic 

} 

return -1; 

} 
int main() 
{ 
    printf("%d",bitpatSearch(243,9,4)); 
    return 0; 
}