CODEWITHSUNDEEP
c#mathbit
MajorInc
MajorInc

Reputation: 354

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

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;
    }

Upvotes: 1

Views: 84

Answers (1)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186793

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;
}

Upvotes: 4

Related Questions