c - Count the number of subset containg 1's -

there bitset of lengt n (it 500-700). need count of every subset containing 1's

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; < 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; < int_bit * len; i++) {     printf("%d ", out[i]); } printf("\n"); free(out); } 

this simple operation executed billions times. iterate on every bit slow. how optimizing algorithm?

i use lookup table choosing appropriate dimension (maybe 8 bits or 16 bits keys).

in lookup table associate every key 4 values:

• number of 1 bits attached left side
• number of 1 bits attached right side
• number of subsets in middle not attached anything
• sizes of subsets in middle

for example associate key 11011011 2,2,2 know left adjacent byte @ least 1 bit attached right side contain subset size + 2 (the left attached length of current byte) , on.

you need find way

• manage more 1 subset in same key (eg 01011010)
• manage key has 1s have consider left byte , right byte , add key length part of subset length.

but every key has 0 on first , last bit trivially managed reduce amount of processing required possible keys.

i guess tricky develop funny too, , in end need comparisons of keys since else hardcoded in lookup table. of course i'm not sure final algorithm outperform simple approach in opinion worth giving chance.