일치하는 비트 패턴과 관련하여 다음 코드를 어떻게 수정할 수 있습니까?

Question

안에 지정된 비트 패턴을 찾는 bitpatSearch()이라는 함수를 작성해야합니다. 함수는 3 개의 인수를 취해야합니다 : bitpatSearch(source, pattern, n). source의 오른쪽에 n 비트를 검색하고 pattern이어야하며 패턴이 시작되는 비트 수 (일치하는 경우 0 ~ 31 번째 비트 순서로 가정)와 일치하는 것이없는 경우 -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)에 의해 32 비트 unsigned int을 이동할 수 없습니다, 그것은 정의되어 있지 않습니다. 경우, 알고리즘에 관한

#include <limits.h> 

... 

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

: 32 전에 중지 루프를 변경합니다

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

또는 더 나은, 그것은 32 다를 수 있습니다 시스템에 대한 형의 크기, 돌이 만들기 당신은 가장 중요한 비트에서 검색해야합니다. 그렇지 않으면 패턴이 두 번 이상 나타나는 경우 예상 위치를 찾을 수 없습니다.

넘버링 시스템의 정확한 정의없이 비트 수에 관해 이야기하는 것은 매우 혼란 스럽습니다. 비트 0은 가장 왼쪽 (가장 중요) 또는 가장 오른쪽 (가장 중요하지 않은) 비트입니까? C에서, 이것은 시프트 연산자 (비트 의 값은 1U << n입니다.)와 일치하므로 가장 중요하지 않은 비트부터 가장 중요한 것까지 번호를 매기는 것이 일반적입니다. 그러나 일부 사람들은 비트를 왼쪽에서 오른쪽으로 번호 지정하는 데 사용됩니다. 반대 컨벤션.

Answer 2

그 비트 번호는 가장 오른쪽 비트가 비트가 0

귀하의 코드는 매우 복잡이고, 오른쪽에서 왼쪽으로 일반적주의하시기 바랍니다. 중첩 루프는 필요하지 않습니다. 여기에 귀하의 문제에 대한 쉬운 해결책이 (패턴 검색은 오른쪽에서 왼쪽입니다) :

(편집 :. 폴 Hankin 및 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; 
} 

, 이것은 하나의 이동에 source 주어진 시프트 값에 pattern의 전체 검사를 시도, 그것은 아무튼으로 이식 int이 특정 크기라고 가정합니다.

코드는 정의되지 않은 동작을 피하기 위해 노력합니다. 특히 INT_BITS 이상으로 시프트를 피할 수 있습니다. 예를 들어, 마스크 (1u << n) - 1을 만들 때 잘못된 이동을 피하기 위해 케이스 if (n == INT_BITS) return source == pattern ? 0 : -1;이 필요합니다.

다음은 코드에 대한 간단한 단위 테스트입니다. 일부 테스트 케이스는 32 비트 int로 가정합니다. 왜냐하면 내가 이식성을 만들기에는 너무 게을 렀기 때문입니다. 당신은 while 루프를 입력 할 때마다 당신이 pattern의 값을 변경하기 때문에

#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의 사본을 작성해야합니다. 따라서 다음에 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; 
}