Ich suche nach einem Algorithmus, der die Anzahl der binären Bitmuster in einem n-bit Wort zählt, die gleich oder kleiner als ein beliebiger Grenzwert sind, der kleiner als 2^n ist. Außerdem möchte ich die Zählung für alle 1-bit Kombinationen, 2-bit Kombinationen usw. generieren. Wenn das Limit 2^n wäre, gäbe es natürlich 2^n Kombinationen (C(n,1) 1-bit combinations plus C(n,2) 2-bit plus C(n,3) 3-bit and so on). Wenn jedoch ein Grenzwert festgelegt würde, wäre nicht jede dieser möglichen Kombinationen gültig (weniger als die festgelegte Grenze).Binäre Bitmuster-Kombinationen zählen
Sagen Sie beispielsweise n=4. Es gibt 16 mögliche Bitmuster, von denen 15 1 oder mehr 1-bits enthalten. Wenn eine Grenze von 10 auferlegt würde, würden diese Muster, die größer als 10 sind, nicht in der Zählung enthalten sein. Für einzelne Bitmuster wären also die gültigen 0001, 0010, 0100 und 1000. Zwei-Bit-Muster wären 0011, 0101, 0110, 1001. Die Muster 1010 und 1100 würden nicht gezählt, weil sie 10 überschreiten. Das einzige 3-Bit-Bit wäre 0111, während das einzige 4-Bit-Muster, 1111, über dem Grenzwert liegt.
Wenn F meine Zählfunktion ist, wäre F(4,10,1) 4 zurück, die Anzahl der 4-bit Muster von 1 Bit, die kleiner als 10 F(4,10,2) würde 4 zurück, wo, wie C(4,2) ist 6. Da der tatsächliche Wert von n groß sein kann (40 oder Bits), das Aufzählen der möglichen Muster, das Testen gegen das Limit und das Zählen gültiger Muster ist unpraktisch.
Irgendwelche Ideen, wie dies effizient gemacht werden könnte?
Ausgezeichnete Idee; Das OP artikuliert seine Frage auch sehr gut, also erwarte ich einige gute Vorschläge von ihm! –