Hi friends! i have a sub-problem that i wasn't able to solve efficiently:

You are given a integer x (<= 10^6) you need to convert to binary, count all the numbers formed by the subsequences of only 1's of their binary representation.

Example x = 13 = 1101 (2^3 + 2^2 + 2^0), the generated numbers will be: 13 12 9 8 5 4 1, we can count in a frecuncy table Frec[13] ++, Frec[12] ++, ..... Frec[1] ++

How to do it efficiently?

I tried with a method O(2^k) where k is the numbers of bits:

void countSubMasks(int x) { for (int bit = x; bit > 0; bit = (bit — 1) & x) { Frec[bit]++; } }

but the method could be used 10^6 times.

Is there an algorithm that does this efficiently?