How many Int32 numbers can be represented when N number of bits is set?

Question

What I want to know is how many numbers can be set if N bits are set to 1 out of 32bits.

Example lets try with 4 bits
//HowMany(1) = 4
//1000
//0100
//0010
//0001
//
//HowMany(2) = 6
//1001
//1010
//1100
//0110
//0101
//0011

public int HowMany(int bits)
{
    ....
}

I am trying to compute a precompute a dictionary for this but it takes ages:

    var dict = new Dictionary<int, int>();
    for (int i = 0; i <= Int32.MaxValue; i++)
    {
        var str = Convert.ToString(i, 2);
        var count = str.Count(x => x == '1');
        if (!dict .ContainsKey(count))
            dict .Add(count, 0);
        dict [count] += 1;
    }

Just seems to be the math concept of [Combination](https://en.wikipedia.org/wiki/Combination) — Damien_The_Unbeliever, Mar 13 '17 at 09:40
Note also that your precomputation code has a bug - you'll either get a `ArithmeticOverflowException` or an infinite loop, since you will at some point try to `i++` on an `i` that is currently set to `Int32.MaxValue`. — Damien_The_Unbeliever, Mar 13 '17 at 09:45
ok i guess this can be easily solved by changing i < Int32.MaxValue — MajorInc, Mar 13 '17 at 09:47

Dmitry Bychenko · Accepted Answer · 2017-03-13T09:51:43.063

4

Easily: if size is n (32 in case of Int32) and we have exactly k bits set, we can represent

  C(k, n) = n! / (k! * (n - k)!)

numbers, where C(k, n) stands for a binomial coefficient.

Edit: As dasblinkenlight's mentioned in the comments, 32! is a huge number which exceeds even long.MaxValue so, probably, a more practical formula is

  C(k, n) = n * (n - 1) * ... * (n - k + 1) / k!

Possible C# implementation:

private static long HowMany(int k, int n = 32) {
  long result = 1;

  for (int i = 0; i < k; ++i)
    result *= (n - i);

  for (int i = 1; i <= k; ++i)
    result /= i;

  return result;
}

edited Mar 13 '17 at 09:51

answered Mar 13 '17 at 09:39

Dmitry Bychenko

180,369
20
160
215

Thanks thats what I thought its the Binomial Coefficient... C# code anywhere? – MajorInc Mar 13 '17 at 09:42
1

Since 32! would overflow an `int` and even `long`, you should mention what to do to avoid overflowing. – Sergey Kalinichenko Mar 13 '17 at 09:43
@MajorInc see [this question](http://stackoverflow.com/questions/12983731/algorithm-for-calculating-binomial-coefficient) – Pikoh Mar 13 '17 at 09:45
@Pikoh just saw this one. Tried to change it from long to int... but think it gives wrong results... e.g. when n = 2, it gives 495 instead of 496 – MajorInc Mar 13 '17 at 09:46
@MajorInc don't use the accepted answer, use Moop's one for example – Pikoh Mar 13 '17 at 09:48
@Dmitry-Bychenko your answer code seems to work aswell. Thanks – MajorInc Mar 13 '17 at 09:51

How many Int32 numbers can be represented when N number of bits is set?

1 Answers1