ビットパターンの一致に関する以下のコードを修正するにはどうすればよいですか？

Question

bitpatSearch()という名前の関数を書くと、unsigned intの中に指定されたビットパターンを探します。関数は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ビットのunsigned intを32でシフトすることはできません。定義されていません。場合は、お使いのアルゴリズムについて

#include <limits.h> 

... 

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

：32前に停止するようにループを変更します。

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

またはそれ以上は、それよりも32異なる場合がありますお使いのシステムのための型のサイズ、をループさせますあなたは最も重要なビットから検索することになっています、それを行う！それ以外の場合は、パターンが複数回存在する場合、予想される位置が見つからないことがあります。

ナンバリングシステムの正確な定義なしにビット番号について話すことは非常に混乱しています。ビット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; 
} 

が、これは単一行くにsourceで与えられたシフト値でpatternの全体を一致させようと、それはdoesnのようなポータブルでありますintが特定のサイズであると仮定します。

コードは、未定義の動作を避けるために厳重に動作します。特にINT_BITS以上のシフトを回避します。たとえば、マスク(1u << n) - 1を構築するときに不正なシフトを避けるためには、ケースif (n == INT_BITS) return source == pattern ? 0 : -1;が必要です。

コードの簡単な単体テストは次のとおりです。いくつかのテストケースは32ビット整数を前提としています。私はそれらを移植性にするには怠惰でした。

#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

あなたはwhileループに入るたびにあなたが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; 
}