Find a pattern of binary numbers using shift-right and bitwise-AND?

Question

I'm attempting to write a function in assembly that will detect if a longer binary number contains a smaller binary pattern.

Example:
Does 100111 contain 1001?

When I read this problem I figured that I would do a bitwise-AND with the large number and its smaller pattern while shifting right (logical) each time in a loop.

So, in my head I thought it would do:

100111 AND 1001 = 0  
Shift-right 1  
010011 AND 1001 = 0  
Shift-right 1  
001001 AND 1001 = 1 // Pattern FOUND!

and repeat this until either the number was shifted until it was zero or the AND returned 1.

However, I think I must have something confused because this is returning 1 for most things I put in, on the first run of the loop. Am I confused on my usage of AND?

Answer 1

You should AND and then test against the search pattern:

if ((TestPattern & SearchPattern) == SearchPattern)
{
   // then match
}

Answer 2

Bitwise AND does not work the way you expect (judging from the samples and ignoring the notation which seems to suggest you are using bitwise AND as the logical AND of bits). AND only takes the bits that are set to 1 "into account". E.g 1111 AND 1001 == 1001.

You need to use XOR and compare against 0 for match (remember the mask the bits you are not comparing from the result). In your example a match is found when (N ^ 1001) & 1111 == 0000

Answer 3

The problem is that "partial matches" also return a non-zero value for your AND check:

100111 AND 001001 = 000001

So this tests if any of the bits match, but you want to make sure all bits are the same. The result of the AND needs to be equal to the pattern you are searching:

x = 100111
if (x AND 1001 == 1001)
  print "found"

Answer 4

In order to make sure that both the 0 and 1 bits match your search pattern, you need to do something like this:

if ((InputPattern AND SearchMask) == SearchPattern)
{
    // then match
}

The SearchMask should be all 1 bits, of a length equal to your SearchPattern. For example, you could have SearchMask == 1111, SearchPattern == 1001.