Search for pattern in binary array

Finding a given pattern can be done with a number of steps equal to the number of bits in the pattern. I do not know if it is most efficient way to detect a pattern, but for not too large patterns, it may be competitive.

As an example, consider your pattern 0100 0000.
It must be found in bitstring bs and we call bs[i] the ith bit of bs.
The pattern is matched at a given position i iff

bs[i] is false (0)
and bs[i+1] is false (0)
and bs[i+2] is false (0)
and bs[i+3] is false (0)
and bs[i+4] is false (0)
and bs[i+5] is false (0)
and bs[i+6] is true (1)
and bs[i+7] is false (0)

This can be turned to the logical expression
~ bs[i] & ~ bs[i+1] & ~ bs[i+2] & ~ bs[i+3] & ~ bs[i+4] & ~ bs[i+5] & bs[i+6] & ~ bs[i+7]
where there is logical complement ~ when there is a 0 in the pattern.

This can be rewritten with right bit shift to get the expression :
~ bs[i] & ~ ((bs>>)[i]) & ~ ((bs>>2)[i]) & ~ ((bs>>3)[i]) & ~ ((bs>>4)[i]) & ~ ((bs>>5)[i]) & ((bs>>6)[i]) & ~ ((bs>>7)[i])
where (bs>>k)[i] is the ith bit of bs shifted k steps rightwards.

From this we can deduce the following C code

#include <stdio.h>

unsigned int findpattern(unsigned int bitstring, unsigned int pattern, 
                         unsigned int patternsize) {
  unsigned int match=~0;
  for(int i=0; i<patternsize; i++){
    match &= ((pattern&0x1)-1) ^ (bitstring);
    pattern >>=1;
    bitstring >>=1;
  }

  return match;
}

int main() {
  unsigned int bitstring=0xffa07fff;
  unsigned int pattern=0x40;

  unsigned int match=findpattern(bitstring,pattern,8);

  if (! match) 
    printf("No match for %x in %x\n",pattern, bitstring);
  else 
    printf("Matches found for %x in %x : %.8x\n", pattern, bitstring, match);
}

The function findpattern returns an int where the ith bit is set if the pattern has been found at position i. In no pattern is found match is zero.

The idea is just to scan the successive bits of pattern by right shifting pattern. At any time if lsb is set, we AND the result with a properly shifted version of bitstring and if lsb of pattern is unset we AND it with the complement of the shifted bit string.
The complementation is done by xoring with (pattern&1)-1. If lsb is set, it is a xor with 1-1=0 (identity), otherwise a xor with -1 (equivalent of ~).

Note that there may be false matches in the higher bits as the bitstring is somehow artificially extended by (patternsize-1) zeros on the left and this may create problems with some combination of bitstring/pattern. That is the reason of the final mask that clears (pattersize-1) leftmost bits of match as it is impossible to find a match beyond bit 32-patternsize. For this reason match is anded with (2^(32-(patternsize-1)) that is a number formed of ones, with patternsize-1 zeros at leftmost positions.