Finding a bit pattern in a 32bit unsigned integer.

Question

I would describe my question using an example

Given a source - 1010 0010, I would like to know how many times (count) the pattern 10 is present in the byte (the source can be of any size 8, 16, 24, or 32 bits).

I would like the function which finds the count to be generic. User should be able to give his own pattern viz. 1000, 101 etc

I want to add that I tried solving the problem. Below is the code snippet (In C Language)

The logic that I have used is to use Ex-OR operation so that if the pattern matches the result of ex-or operation will be 0.

unsigned int FindPattern (unsigned int u32Number, unsigned int u32Pattern)
{

    unsigned int count = 0;
    unsigned int u32Temp = 0;

    while (0 != u32Number)
    {
        /* How can I turn off (0) all the bits except bits which represent pattern 
         * For example if pattern is 3 bits then the all the bits except the last 3 
         * bits should be 0. */

        if(!(u32Number ^ u32Pattern))
        {
      count++;
        }

    u32Number = u32Number >> 1;
    }

    return count;
}

Answer 1

A very odd problem, basic solution:

Starting from the right most bit
Find a 0, Set a marker
Go left 1 bit
If the bit is a 1, Increment the Number of 10's, Move Left 1 Bit
If the bit is a 0, Unset the Previous Marker, Set the Marker
Repeat until you have reached the beginning of the string

Hope that helps.

Answer 2

uint32_t pattern = 0xA2;
uint32_t occurrences = countOnes((pattern >> 1) & ~pattern);

// ...

uint32_t countOnes(uint32_t v)
{
    v = v - ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

(the countOnes implementation is from the Bit Twiddling Hacks page.)

Answer 3

Try this:

#include <stdio.h>

int main(void)
{

    unsigned int number = 0xa2;
    unsigned int pattern = 0x02;
    unsigned int pattern_mask = 0x03;

    int count = 0;
    while(number > 0) {

     if( !((number ^ pattern) & pattern_mask) ) {
      ++count;
      printf("%x\n", number);
     }

     number >>= 1;

    }

    printf("\ncount:  %d\n", count);

    return 0;
}

Assumes you are not interested in leading zeros.

pattern_mask could be calculated.

Answer 4

#include <iostream>
using namespace std;

int count(long haystack, long needle, unsigned int needle_bits)
{
 int total_bits = 8 * sizeof(haystack);

 long excludepattern = 1; for (unsigned int j = 1; j < needle_bits; j++) excludepattern += excludepattern * 2; //generate mask

 int count = 0;

 for (unsigned int i = 0; i < total_bits - needle_bits; i++)
 {
  long pattern = haystack >> i;
  pattern &= excludepattern; //mask the haystack so only the used bits count

  if (pattern == needle) count++;
 }

 return count;
}

int main()
{
 long haystack = 55; //110111
 long needle1 = 2; //10
 long needle2 = 3; //11;

 cout<<"10 occurs "<<count(haystack,needle1,2)<<" times in 110111."<<endl;
 cout<<"11 occurs "<<count(haystack,needle2,2)<<" times in 110111."<<endl;

 system("PAUSE");
 return 0;
}

I'm sorry this is in C++, not C but that shouldn't matter for the count function as it uses no C++ specific constructs.

Expected output: 10 occurs 1 times in 110111. 11 occurs 3 times in 110111.

Answer 5

Does your pattern always begin with a 1? If not, the length will have to be specified somehow. If so, well, this smells like a homework problem, but I commend to you the following expressions:

 b <<= 1
 b < pat
 b - 1