在无符号int中搜索位模式

Question

我正在通过Kochan的C语言编程学习C语言，其中一个练习是：

使bitpat_search()函数搜索数字0xE1F4(=1110 0001 1111 0100二进制）是否出现三位模式0x5(=101二进制）。该函数返回11，以指示在源代码中找到了以11位开头的模式。

确保函数没有对int的大小做任何假设。

这是我实现函数的方式：

#include <stdio.h>

int bitpat_search(unsigned int source, unsigned int pattern, int n);
int int_size(void);

int main(void)
{
    printf("%i\n", bitpat_search(0xe1f4, 0x5, 3));

    return 0;
}

int bitpat_search(unsigned int source, unsigned int pattern, int n)
{
    int size = int_size();
    pattern <<= (size - n);
    unsigned int compare = source;
    
    int bitnum = 0;

    while (compare)
    {
        compare >>= (size - n);
        compare <<= (size - n);

        if (compare & pattern)
        {
            return bitnum;
        }
        else
        {
            source <<= 1;
            bitnum++;
            compare = source;
        }       
    }

    return -1;
}

// Calculates the size of an integer for a particular computer
int int_size(void)
{
    int count = 0;
    unsigned int x = ~0;

    while (x)
    {   
        ++count;
        x >>= 1;
    }

    printf("%i\n", count);

    return count;
}

但是，我的程序的输出结果是14，而不是11。我用铅笔和纸跟着程序走，不明白哪里出了问题...帮忙？

Answer 1

您的测试不正确:(compare&pattern)只检查compare和pattern是否至少有一个相同的位。您应该使用掩码并编写if((compare&mask)==pattern)。

以下是更正后的版本：

int bitpat_search(unsigned int source, unsigned int pattern, int n) {
    int i, bitcount;
    unsigned int mask = (1U << n) - 1;

    pattern &= mask;   /* mask off the n rightmost bits */

    for (bitcount = 0; (source >> bitcount) != 0; bitcount++)
        continue;

    for (i = 0; i <= bitcount - n; i++) {
        if (((source >> (bitcount - n - i)) & mask) == pattern)
            return i;
    }
    return -1;  /* not found */
}