Я ищу алгоритм, который будет подсчитывать количество двоичных битовых шаблонов в слове 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 или биты), перечисление возможных шаблонов, тестирование против предела и подсчет действительных нецелесообразно.
Любые идеи относительно того, как это можно сделать эффективно?
Отличная идея; OP тоже очень хорошо формулирует свой вопрос, поэтому я ожидаю от него каких-то хороших предложений! –