I'm looking for a quick way to generate every binary number of length n which contains m 1s.
So for example, if n=3, m=2, this would just be: 110, 011, 101.
The naive approach would be to iterate through numbers between 1 and 2^n - 1, checking if each value's binary representation contains m 1s. Alternatively, using some algorithm to get each combination of m 1s and n - m 0s.
However, I'm wondering if there might be some quicker way to do this with bitwise operators, or perhaps a property of numbers with m 1s in their binary representation that could be exploited.
CodePudding user response：
-First you need to put a '1' in position n -Then you need to put m-1 '1' in the positions 0 to n-1. -You need Comb(n-1,m-1) to do this, for example using a recurring algorithm (to put m-1 '1' in n-1 positions you put a 1 in positions i= n-1 to m-2 and m-2 '1' in i-1 positions.
CodePudding user response：
If you want only to count all possible binary numbers, then the answer will be nCm i.e C(n,m) = (n! / (m! * (n−m)!). See here. (for an explanation of the mathematical concept: combination.)
If you need to find all numbers, then this problem is the same as: "Find all the possible Binary strings of size n having m set bits". You can refer to this for this case.