N皇后问题
2010年8月10日 00:22 | Comments(22) | Category:C语言 | Tags:c 二进制 位运算 数学
#include <stdio.h> static int upperlim, sum; void binqueen(int row, int ld, int rd) { int pos, p; if(row != upperlim) { pos = upperlim & ~(row | ld | rd); while (pos) { p = pos & -pos; pos -= p; binqueen(row+p, (ld+p)<<1, (rd+p)>>1); } } else sum++; } int main(void) { int n; scanf("%d", &n); upperlim = (1<<n) - 1; binqueen(0, 0, 0); printf("%d", sum); return 0; }
求一个数的二进制有多少个1?
2010年8月03日 02:29 | Comments(1) | Category:C语言 | Tags:c 分治 位运算 二进制
/*author:Star date:2010-08-02*/ #include <stdio.h> #include <assert.h> int CntBit(unsigned int n) //分治思想 { n = ((n & 0xaaaaaaaa) >> 1 ) + (n & 0x55555555); n = ((n & 0xcccccccc) >> 2 ) + (n & 0x33333333); n = ((n & 0xf0f0f0f0) >> 4 ) + (n & 0x0f0f0f0f); n = ((n & 0xff00ff00) >> 8 ) + (n & 0x00ff00ff); n = ((n & 0xffff0000) >> 16) + (n & 0x0000ffff); return n; } int main(int argc, char *argv[]) { unsigned int N; int i, j; scanf("%u", &N); printf("%u:", N); i = CntBit(N); assert(i >= 0 && i <= 32); for(j = 31; j >= 0; --j) printf("%d", N&(1<<j) ? 1 : 0); printf("\nhave %d bit that are \'1\'", i); return 0; }
这里数以的大小范围为例。