Finding a bit pattern in an unsigned int

Question

I learn C through Kochan Programming in C. One of the exercises is as follows:

Write a function with a name bitpat_search()that looks for the appearance of a specific bit pattern inside unsigned int. The function must take three arguments and should be called as such:

bitpat_search (source, pattern, n)

The function searches for an integer sourcestarting from the leftmost bit to see if the rightmost n bits are patternin source. If the pattern is found, ask the function to return the bit number from which the pattern begins, where the leftmost bit is number 0. If the pattern is not found, then the function returns -1. So, for example, a call

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

calls the function bitpat_search()to search for the number 0xe1f4 (= 1110 0001 1111 0100 binary code) for the appearance of a three-bit pattern 0x5 (= 101 binary). The function returns 11to indicate that the pattern was found in source, starting at bit 11.

Make sure that the function does not make size assumptions int.

So I implemented the function:

#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;
}

First, I calculate the size of an integer (can't use sizeof()). Then I will align the template that we are looking for to start with MSB. I create a temporary variable compareand assign a value to it source, and also initialize the variable bitnumto 0; it will track the position of the bit we are comparing.

compare ( 0 , ), : true, , compare ( , compare ), bitnum . , pattern source -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 */
}