c - 第 11 章 C Kochan 编程中的练习 6，查找位模式

Question

希望得到位运算符的帮助。练习内容如下:

Write a function called bitpat_search() that looks for the occurence 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 bit_pat(search() function to search the number 0xe1f4 (= 1110 0001 1111 0100 binary) for the occurence 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.

我在运行时遇到了一些问题:

1- 这些数字对我来说实际上没有多大意义......每次迭代后我都尝试了各种 printf() 函数，看起来 0x5 数字被读取为 100 二进制，这将是四。如果我尝试其他数字，它们会相当随机，但通常为 000，所以……不是很有帮助。我算错了吗？右移会以某种方式改变它吗？

2 - 它返回了错误的位置(19 而不是 11)，但是当我把上面的 q1 的数字弄乱时，它并没有真正起作用，是吗？

抱歉，如果这对所有可爱的人来说是显而易见的，我只是可以看到它。 (顺便说一句，我只是想从书中学习，这不是学校的作业)。

谢谢

#include <stdio.h>

int int_size(unsigned int num);
int bit_test(unsigned int word, int position, int size);
int bitpat_search(unsigned int source, unsigned int pattern, int n);

int main(void)
{
    int index;

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

    printf(" Pattern found in position %i\n", index);
    return 0;
}

int bitpat_search(unsigned int source, unsigned int pattern, int n)
{
    int i, j, tempSource, tempPat, count;

    int size = int_size(~0);

    for (i = 0; i < size;)
    {
        count = 0;
        for (j = 0; j < n; j++)
        {
            tempSource = bit_test(source, i, size);
            tempPat = bit_test(pattern, j, size);

            i++;
            count++;

            if (tempSource != tempPat)
            break;
        }
        if (count == n)
            return i - n;
    }
    return 0;

}

int bit_test(unsigned int word, int position, int size)
{
    if( (word >> (size - position)) & 0x1) // shift bits in word 31 minus n     spaces right, and AND word with hexadecimal 1
        return 1; // if above is true (1 & 1) return 1
    else
        return 0;

}

int int_size(unsigned int num)
{
    int size = 0;

    while (num)
    {
        size++;
        num >>= 1;
    }

    return size;
}

Answer 1

for (i = 0; i < size;)
{
    count = 0;
    for (j = 0; j < n; j++)
    {
        tempSource = bit_test(source, i, size);
        tempPat = bit_test(pattern, j, size);

在这里，您要检查源代码中位置 i 的位与模式中位置 j 的位。这在源代码中必须是 i+j，否则您在源代码中将模式与一个位进行比较，而不是将模式与 number 位进行比较。由于模式 101 包含 1 和 0，因此您永远找不到任何东西。

旁注:您可以将 int_size 函数替换为 sizeof(int)*8。这假定了 8 位字节，但是自八十年代初以来就没有出现过该假设不成立的计算机，因此这应该是一个相当安全的假设。