问个想不明白的算法
判断C(n, k) (0 ≤ k ≤ n < 2^31)的奇偶性
input: n, k
output: 奇/偶
m = n - k;
cnt = 0;
while (n > 0)
{
cnt += n > > 1;
n > > = 1;
}
while (m > 0)
{
cnt -= m > > 1;
m > > = 1;
}
while (k > 0)
{
cnt -= k > > 1;
k > > = 1;
}
if (cnt > 0)
printf( "偶 ");
else
printf( "奇 ");
想了好久想不通为什么，那位达人给点数学上的证明或提示？谢谢！
[解决办法]
其算法原理如下:
首先, 一个数可以表示为 2^x * y 其中 x> =0, y某一奇数
m = n-k
则
C(n, k) = n!/((n-k)! * k!) = n!/(m!*k!)
n! 表示为 2^x * y , 其中 x= n/2 + n/4 + n/8 + n/16 ....
