c# - 设置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;
}