在 unsigned int 中搜索位模式

Question

我正在通过 Kochan's Programming in 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 */
}

在 unsigned int 中搜索位模式

Searching for a bit pattern in an unsigned int

c

bit-manipulation

bit-shift

bit

bitwise-operators