getting n consecutive bits set/unset in a array

0

I want to find the position from where n consecutive bits are set or unset in a array.

example array:

a[0] = 0x0fffffff  
a[1] = 0x000000f0  
a[2] = 0xffffff00

If I want to the find first 8 unset bits it must return 28 (28th bit position in array)

If I want to find first 32 unset bits it must return 40 (40th bit position in array)

I'm trying to expand upon code that I found here so that it will work with an arbitrarily large array:

int BitCount(unsigned int u)
 {
         unsigned int uCount;

         uCount = u
                  - ((u >> 1) & 033333333333)
                  - ((u >> 2) & 011111111111);
         return
           ((uCount + (uCount >> 3))
            & 030707070707) % 63;
 }
c
asked on Stack Overflow Oct 11, 2012 by user1738128 • edited Oct 11, 2012 by embedded.kyle

1 Answer

0

This is what I came up with:

Simply loops through the array and checks 1 bit at a time to see whether its set or not.

int UnsetBits(unsigned int a[], int sizeOfArray, int requiredBits)
{
    //number of found bits in a row
    int found = 0;

    //current index in array
    int index = 0;

    //current bit
    int bit = 0;

    while(index < sizeOfArray)
    {
        //isolate the current bit
        int data = ((a[index] << (31 - bit)) >> 31);

        //bit is unset
        if(data == 0)
        {
            found++;

            //found required amount, return start position
            if(found == requiredBits)
            {
                return bit + 1 + (index * 32) - requiredBits;
            }
        }
        //bit is set, reset found count
        else
        {
            found = 0;
        }

        //increment which bit we are checking
        bit++;

        //increment which array index we are checking
        if(bit >= 32)
        {
            bit = 0;
            index++;
        }
    }

    //not found
    return -1;
}
answered on Stack Overflow Oct 9, 2013 by wotlight

User contributions licensed under CC BY-SA 3.0