Я ищу алгоритм, который будет подсчитывать количество двоичных битовых комбинаций в слове 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 шаблонов 1 бита, которые меньше 10. F(4,10,2) вернет 4, где C(4,2) равно 6. Поскольку фактическоезначение n может быть большим (40 или бит), перечислять возможные шаблоны, тестировать их по пределу и считать действительные нецелесообразно.
Есть идеи относительно того, как это можно сделать эффективно?