Count the number of subsets containing 1

Question

There is a bitset of length L (it will be about 500-700). I need to get a count of each subset containing only 1

Example

N = 32

Set = 0 * 11 * 0 * 111 * 00 * 1 * 0 * 1 * 00 * 1111 * 0 * 11 * 00 * 111 * 000 * 1 * 0 * 1 *

Out = {[1] = 4, [2] = 2, [3] = 2, [4] = 1, [5] = 0, ... [32] = 0}

void get_count(int tab[], int len) { int *out = calloc(1, sizeof(*out) * INT_BIT * len); int i, j, k; int cur; int count = 0; for(i = 0; i < len; i++) { cur = tab[i]; for(j = 0; j < INT_BIT; j++) { count += (cur & 1); if(!(cur & 1)) { out[count]++; count = 0; } cur >>= 1; } } for(i = 0; i < INT_BIT * len; i++) { printf("%d ", out[i]); } printf("\n"); free(out); } 

This simple operation will take about a billion times. The iteration over each bit is too slow. How to optimize this algorithm?

Answer 1

I would use a lookup table, choosing the appropriate size (maybe 8 bits or 16 bits).

In this lookup table, I would associate each key with 4 values:

• 1 bit number attached to the left side
• number of 1 bits attached to the right side.
• the number of subsets in the middle that are not tied to anything
• the sizes of the subsets in the middle

For example, you can associate key 11011011 with 2,2,2 so that you know that the left adjacent byte with at least 1 bit attached to the right side will contain a subset whose size is + 2 (left attached length of the current byte) etc.

You need to find a way

• manage more than one subset in one key (e.g. 01011010 )
• manage a key that has all 1s, so you have to consider the byte left and right and add the key length as part of the length of the subset.

but every key that has 0 on the first and last bits is trivially controlled, so you reduce the amount of processing needed for some possible keys.

I think it’s difficult to develop, but it can also be funny, and in the end you will just need to compare the keys, since everything else is hardcoded in the search table. Of course, I'm not sure that the last algorithm will surpass the simple approach, but, in my opinion, it is worth giving a chance.