c - 在 unsigned int 中搜索位模式

Question

我正在通过 Kochan 的 C 语言编程学习 C。其中一个练习如下:

Write a function called bitpat_search() that looks for the occurrence of a specified pattern of bits inside an unsigned int. The function should take three arguments, and should be called as such:

bitpat_search (source, pattern, n)

The function searches for the integer source, starting at the leftmost bit, to see if the rightmost n bits of pattern occur in source. If the pattern is found, have the function return the number of the bit at which the pattern begins, where the leftmost bit is number 0. If the pattern is not found, then have the function return -1. So, for example, the call

index = bitpat_search (0xe1f4, 0x5, 3);

causes the bitpat_search() function to search the number 0xe1f4 (= 1110 0001 1111 0100 binary) for the occurrence of the three-bit pattern 0x5 (= 101 binary). The function returns 11 to indicate that the pattern was found in the source beginning with bit number 11.

Make certain that the function makes no assumptions about the size of an 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;
}

首先，我计算一个整数的大小(不能使用sizeof())。然后，我对齐我们正在寻找的模式，使其从 MSB 开始。我创建了一个临时变量 compare 并将 source 的值赋给它，我还将一个变量 bitnum 初始化为 0；它将跟踪我们正在比较的位的位置。

在循环中，我将 compare 左右移动(在将与位模式进行比较的位的左右两侧添加 0)，然后比较值:如果为真, 位号被返回, 否则, source 向左移动一次然后分配给 compare (这实质上移动了我们在 compare 中比较的位的位置向右)并且 bitnum 递增。如果在 source 中找不到 pattern 并且根据说明返回 -1，则循环停止执行。

但是，我的程序输出结果是 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 */
}