Как я могу исправить следующий код относительно совпадающих битовых шаблонов?

Question

Мне поручено написать функцию под названием bitpatSearch(), которая ищет заданный шаблон бита внутри unsigned int. Функция должна принимать 3 аргумента: bitpatSearch(source, pattern, n). Он должен искать целое число source для самых правых n бит pattern и выводить количество бит, где начинается шаблон (предположим, что порядок от 0 до 31-го порядка для 32-битного целого), если есть совпадение, и -1, если нет совпадения.

Несмотря на то, что упражнение рекомендуется искать с самого левого бита, мой код выполняет поиск с самого правого, так как я думал, что будет проще (поскольку я мог бы И с 1.) Однако что-то не так, и я подозреваю, что арифметика за заявлением return может быть проблемой, но не может понять это.

Программа, похоже, всегда ошибочна, но всегда правильно говорит, есть ли совпадение.

#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

Вы не можете сдвинуть 32- unsigned int на 32, она не определена. Изменение цикла остановиться до 32:

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

Или лучше сделать цикл по размеру типа для вашей системы, которая могла бы быть иначе, чем 32:

#include <limits.h> 

... 

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

Что касается вашего алгоритма, если вы должны искать от самого значительного бита, сделайте это! В противном случае вы можете не найти ожидаемую позицию, если шаблон присутствует более одного раза.

Обратите внимание, что очень сложно говорить о битовых номерах без точного определения системы нумерации: бит 0 самый левый (самый значительный) или самый правый (наименее значимый) бит? В C часто используется число бит от наименее значимого до самого значимого, так как это согласуется с оператором сдвига (бит n имеет значение 1U << n), но некоторые люди используются, чтобы пронумеровать бит слева направо, напротив конвенции.

Answer 2

Пожалуйста, обратите внимание, что нумерация бит обычно справа налево, где крайний правый бит бит 0.

Ваш код очень сложно. Вложенные петли не нужны. Вот простое решение для вашей проблемы (шаблон поиска находится справа налево):

(EDIT:. Код теперь включает в себя улучшения, предложенный Полом Ханкина и 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

Вы частично уничтожить pattern в внутренний цикл while, сдвигая его как биты, сопоставляются. Поэтому, если вы получите частичное совпадение, то pattern больше не будет содержать правильное значение для последующих поисков. Пример того, что ваш код ошибается, - bitpatSearch(0xf0f, 0xff, 8). Кодекс находит совпадение в позиции 12, но нигде не встречается.

Я бы написать такой код:

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

В отличие от вашего кода, это пытается сопоставить полноту pattern при заданном значении сдвига в source на одном дыхании, и является портативным, как это Безразлично Предположим, что int - это особый размер.

Код работает, чтобы избежать неопределенного поведения; особенно избегая сдвигов INT_BITS или более. Например, случай if (n == INT_BITS) return source == pattern ? 0 : -1; необходим, чтобы избежать незаконного сдвига при построении маски (1u << n) - 1.

Вот несколько простых модульных тестов для кода. Некоторые из тестовых примеров предполагают 32-битный int, потому что я был слишком ленив, чтобы сделать их переносимыми.

#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

Вам нужно создать копию pattern, потому что каждый раз, когда вы входите в цикл, пока вы меняете значение pattern. Поэтому в следующий раз, когда вы войдете в цикл while, вы будете сравнивать с неправильным шаблоном.

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