Get list of bits set in BitMap

Question

In C, Is there any optimized way of retrieving list of BitPositions set without parsing through each bit.

Consider following example

int bitmap[4];

So, there are 4 * 32 Bit Positions..Values are following

bitmap = { 0x1, 0x0, 0x0, 0x0010001 }

I want retrieve Position of each bit set instead of parsing from 0 to 4 * 32 positions.

Answer 1

Related with this question, you can see What is the fastest way to return the positions of all set bits in a 64-bit integer?

A simple solution, but perhaps not the fastest, depending on the times of the log and pow functions:

#include<math.h>
#include<stdio.h>

void getSetBits(unsigned int num, int offset){

    int bit;
    while(num){
        bit = log2(num);
        num -= pow(2, bit);

        printf("%i\n", offset + bit); // use bit number
    }
}

int main(){
    int i, bitmap[4] = {0x1, 0x0, 0x0, 0x0010001};
    for(i = 0; i < 4; i++)
        getSetBits(bitmap[i], i * 32);
}

Complexity O(D) | D is the number of set bits.

Answer 2

An optimal solution which runs in O(k), where k = the total number of set bits in your entire list, can be achieved by using a lookup table. For example, you can use a table of 256 entries to describe the bit positions of every set bit in that byte. The index would be the actual value of the Byte.

For each entry you could use the following structure.

struct
{
   int numberOfSetBits;
   char* list; // use malloc and alloocate the list according to numberOfSetBits
}

You can then iterate across the list member of each structure and the number of iterations = the number of set bits for that byte. For a 32-bit integer you will have to iterate through 4 of these structs, one per each byte. To determine which entry you need to check you use a Bitmap and shift 8 bits. Note, that the bit positions are relative to that byte, so you may have to add an offset or either 24, 16, or 8 depending on the byte you are iterating through (assuming a 32 bit integer).

Note: if additional memory usage is not a problem for you, you could build a 64K Table of 16-bit entries and you will decrease the number of your structs by half.

Answer 3

First of all, one cannot really use int for bitmap in C, because shifting a bit to left to the sign bit has undefined behaviour, C doesn't guarantee that the representation is two's complement, or that there are 32 bits in an int; that being said the easiest way to avoid these pitfalls is to use the uint32_t from <stdint.h> instead. Thus

#include <stdint.h>
uint32_t bitmap[4];

So consider that you number these bits 0 ... 127 from indexes 0 ... 3; and within indexes 0 ... 31; so, you can get the index into array and the bit number within that value by using the following formula:

int bit_number = // a value from 0 ... 127
int index = value >> 32; // shift right by number of bits in each index
int bit_in_value = value & 31; // take modulo 32 to get the bit in value

Now you can index the integer by:

bitmap[index];

and the bit mask for the desired value is

uint32_t mask = (uint32_t)1 << bit_in_value;

so you can check if the bit is set by doing

bit_is_set = !!(bitmap[index] & mask);

Now to speed things up, you can skip any index for which bitmap[index] is 0 because it doesn't contain any bits set; likewise, within each index you can speed things up by shifting bits in the uint32_t from the bitmap right by 1 and masking with 1; and breaking the loop when the uint32_t becomes 0:

for (int index = 0; index <= 3; index ++) {
     uint32_t entry = bitmap[index];
     if (! entry) {
         continue;
     }

     int bit_number = 32 * index;
     while (entry) {
         if (entry & 1) {
             printf("bit number %d is set\n", bit_number);
         }
         entry >>= 1;
         bit_number ++;
     }   
}

Other than that there is not much to speed up, besides lookup tables, or using compiler intrinsics, such as this to set which is the lowest bit set but you'd still have to use some anyway.