具有相同数量的0和1的二进制数

Question

当我解决欧拉项目问题#15时,我意识到它可以通过从开始到结束的路径组合方式来解决.生成的路径始终具有相同大小的向右或向下选择(或0和1),而正确的路径始终具有相同的0和1的数量.因此,在二进制字中具有相同数量0和1的数字的数量是1比特长度的C(2,1)对于2比特是C(4,2),对于4比特是"C(6,3)"......

现在我的问题是:如果一个数字具有0和1的相同数量,是否有一个函数可以解决？我想它更像是一个逻辑函数,我不想迭代所有的数字或使用正则表达式(这将比迭代更糟).

**其他问题是关于这种"平衡"价值观之间的增长和空间？

Answer 1

您正在寻找一个popcount函数,它计算给定数字中的设置位数.有些处理器内置,有些则没有.

c=0; while (n &= (n-1)) c++;

做的工作,但破坏n.

有关更好的算法,请参阅此链接,或google"popcount".

Answer 2

作为 Paul R 答案的后续，对中心二项式系数的公式进行了简化，请参阅http://mathworld.wolfram.com/CentralBinomialCoefficient.html

\n\n

p = n！/ ((n/2)!)\xc2\xb2 = 2 ^n/2 (n-1)!! /（n/2）！

\n\n

克！！是“双阶乘”，这意味着在计算时跳过所有其他数字：k！= k * (k-2) * (k-4) * ...（只要因子为正）。

\n\n

对于您的计算，很多数字将被抵消（同时计算分子和分母时，您可以使用 gcd）

\n