c(n,k)奇偶性判断.cpp

很高效的判断组合数C(n,k)的奇偶性。 巧妙的使用了位运算。时间复杂度为O(1). 避免使用大数类。

/*
C(n,k)%2==1得出  n!中 2的因子 等于 (n-k)!与k!中2的因子之和
所以 n/2+n/4+n/8+...+0==(n-k)/2+k/2+(n-k)/4+k/4+(n-k)/8+k/8+....+0+0

而  n/2>=(n-k)/2+k/2(取==条件为(n-k),k不能同时为奇数  也就是k,(n-k)二进制位最后一位至少有一个为0)
  再n=n/2,k=k/2;  同理可以得出k,(n-k)二进制倒数第二位至少有一个为0
  依此类推
 整理结论 得出 ((n-k)&k)==0
这个式子应该和  (n&k)==k等价

*/
#include    <stdio.h>

int         n , k , t;
int         main()
{
           while(scanf("%d%d",&n,&k)==2&&(n || k))
           {
                 t = n&k;
                 if( t == k)
                        printf("1\n"); else printf("0\n");                             
           } 
           return 0;
}