0

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.

jamarit6
  • 3
  • 2
  • Possible dupe: https://stackoverflow.com/questions/35115478/specific-binary-permutation-generating-function ā€“ rici Apr 24 '22 at 00:07
  • 1
    Does this answer your question? [Generate all binary strings of length n with k bits set](https://stackoverflow.com/questions/1851134/generate-all-binary-strings-of-length-n-with-k-bits-set) ā€“ Abhinav Mathur Apr 24 '22 at 03:28
  • This is identical to the problem of generating the set of n things taken m at a time (combinations). Here, the things are the positions of 1 bits. There are gajillions of answers about how to do this. ā€“ Gene Apr 24 '22 at 05:09

2 Answers2

0

-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.

Jean Valj
  • 119
  • 4
0

  1. 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.)

  2. 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.

Ayush
  • 373
  • 4
  • 12