CODEWITHSUNDEEP
cbit-manipulation
Rohit
Rohit

Reputation:

Finding a bit pattern in a 32bit unsigned integer

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

Upvotes: 2

Views: 7377

Answers (6)

nickhalden
nickhalden

Reputation: 73

Here is a solution in C. Anyone can help simplify the "if" statement ?

int bit_pattern_exists (int num, int pattern)
{
int i= 0, count = 0;

int len_num=0;
int len_pattern=0;
int p = pattern;
int temp = num;

/* count the number of bits in the pattern */
while (p) {
    len_pattern++;
    p = p >> 1;
}   

/* count the number of bits in the number */
while (temp) {
    len_num++;
    temp  = temp >> 1;
}   

if (len_num<len_pattern)
    return FALSE;

i = 0 ; 

while (i < len_num) {
    if ((pattern << i) == (((~(~0 << len_pattern))<<i)&num)) {
        count++;
    }   

    i++;

    if (len_pattern > len_num -i) 
        break;
}   

return count;
}

Upvotes: 0

Norman Ramsey
Norman Ramsey

Reputation: 202495

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

Upvotes: 1

Ruud
Ruud

Reputation: 3261

#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.

Upvotes: 1

Karl Voigtland
Karl Voigtland

Reputation: 7705

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.

Upvotes: 3

user113476
user113476

Reputation:

Here's a naive C# solution which you may be able to gather some ideas from to implement your C homework.


        static void Main(string[] args)
        {
            String p = "10";            
            int s = 0x0A0A0C0C;

            Console.WriteLine(CountBitPattern(p, s));
            Console.ReadLine();
        }

        // count the occurences of bit pattern p - in - int s
        static int CountBitPattern(String p, int s)
        {
            String t = "";

            for (int i = 31; i >= 0; i--)
            {
                if ((s & (1 << i)) > 0)
                    t += '1';
                else
                    t += '0';
            }

            int c = 0;
            int n = 0;
            int r = 0;
            while (r > -1)
            {
                r = t.IndexOf(p, n);
                if (r > -1)
                    c++;
                n = r + 1;
            }

            return c;
        }

Upvotes: 0

AAA
AAA

Reputation: 4956

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.

Upvotes: 3

Related Questions