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;
}
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;
}
User contributions licensed under CC BY-SA 3.0