Counting binary bit pattern combinations

Question

I'm looking for an algorithm that will count the number of binary bit patterns in an n-bit word which are equal to or less than an arbitrary limit that is less than 2^n. Further, I want to generate the count for all 1-bit combinations, 2-bit combinations, etc.. Obviously, if the limit were 2^n, there would be 2^n combinations (C(n,1) 1-bit combinations plus C(n,2) 2-bit plus C(n,3) 3-bit and so on). If a limit were imposed, however, not every one of those possible combinations would be valid (less than the imposed limit).

For example, say n is 4. There are 16 possible bit patterns, 15 of which contain 1 or more 1-bits. If a limit of 10 were imposed, those patterns greater than 10 would not be included in the count. So, for single bit patterns, the valid ones would be 0001 0010 0100 and 1000. Two-bit patterns would be 0011, 0101, 0110, 1001. Patterns 1010 and 1100 would not be counted because they exceed 10. The only 3-bit bit would be 0111 while the sole 4-bit pattern, 1111, is over the limit.

If F is my counting function, F(4,10,1) would return 4, the number of 4-bit patterns of 1 bit that are less than 10. F(4,10,2) would return 4 where as C(4,2) is 6. Because the actual value of n can be large (40 or bits), enumerating the possible patterns, testing against the limit, and counting valid ones is impractical.

Any ideas as to how this might be done efficiently?

Answer 1

since this is tagged as a homework question, why don't you offer your ideas and we can give you advice. You could always design an inefficient algorithm, and analyze that to try and create efficiencies...

Answer 2

Break the range below the limit down into regions of size 2^m with a fixed prefix and take the bits set in the prefix into account.

Answer 3

Just a hint, but try to attack this inductively / recursively (whichever moniker you prefer); reduce the problem to smaller instances of itself.