当N位设置时，可以表示多少个Int32数？(How many Int32 numbers can be represented when N number of bits is set?)

当N位设置时，可以表示多少个Int32数？(How many Int32 numbers can be represented when N number of bits is set?)

我想知道的是，如果N位设置为32位中的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; }

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

最满意答案

很容易：如果size是n （在Int32情况下为Int32 ）并且我们设置了k位，我们可以表示

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

数字，其中C(k, n)代表二项式系数 。

编辑 ：正如评论中提到的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; }

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