我正在寻找一种算法，该算法将计算一个n-bit单词中二进制位模式的数量，这些位模式等于或小于小于的任意限制2^n。此外，我想为所有1-bit组合、2-bit组合等生成计数。显然，如果限制是2^n，就会有2^n组合(C(n,1) 1-bit combinations plus C(n,2) 2-bit plus C(n,3) 3-bit and so on)。但是，如果施加限制，则并非所有可能的组合都是有效的（小于施加的限制）。
例如，说n=4。有 16 种可能的位模式，其中 15 种包含 1 或更多1-bits。如果限制为 10，则大于 10 的模式将不包括在计数中。因此，对于单个位模式，有效的将是0001、0010、0100和1000。两位模式将是0011, 0101, 0110, 1001. 模式1010并且1100不会被计算在内，因为它们超过了 10。唯一的 3 位位将是0111，而唯一的 4 位模式1111超过了限制。
如果F是我的计数函数，F(4,10,1)将返回 4，4-bit小于 10 的 1 位模式的数量。F(4,10,2)将返回 4，其中为C(4,2)6。因为 的实际值n可能很大（40 或位），枚举可能的模式，针对限制进行测试并计算有效的是不切实际的。
关于如何有效地做到这一点的任何想法？