设置N位数可以表示多少个Int32数？

Question

我想知道的是32位中N位设为1可以设置多少个数

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)
{
    ....
}

我正在尝试为此计算一个预先计算的字典，但它需要很长时间：

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

Answer 1

简单：如果大小是 n（32 在 Int32 的情况下）并且我们恰好设置了 k 位，我们可以表示

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

个数字，其中 C(k, n) 代表一个 binomial coefficient。

编辑：正如dasblinkenlight在评论中提到的，32!是一个巨大的数字，超过甚至 long.MaxValue 所以，更实用的公式可能是

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

可能的 C# 实现：

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

设置N位数可以表示多少个Int32数？

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

c#

math

bits