位操作－－对优化算法有了个新的认识，--优化算法新的

位操作－－对优化算法有了个新的认识，--优化算法新的

 好久没来csdn了，今天想问个关于C读取扇区的问题（没人回答．．），结果看到一个N皇后问题最快的算法，看了好一会才明白，这算法巧妙之处我认为有２个：

１．以前都是用数组来描述状态，而这算法采用是的位来描述，运算速度可以大大提升，以后写程序对于描述状态的变量大家可以借鉴这个例子，会让你的程序跑得更快　　　　　　　　　　　　　　　　　　　　　　　

２．描述每行可放置的位置都是只用row,ld,rd这３个变量来描述，这样使得程序看起来挺简洁的．

下面是程序，自己加了些注释：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long sum = 0, upperlim = 1;             //sum为排列的总数, upperlim为N个位为1的数

void test(long row, long ld, long rd)    //row,ld,rd分别为上面的所有皇后在该行吃掉的列位,左右对角线位
{

   if (row != upperlim)          //如果N皇后没有全部排好;row中1表示该列已经排了皇后,0表示没有排
   {
       long pos = upperlim & ~(row | ld | rd);     //pos表示该行可排的位置:1表示可排,0表示不可排
       while (pos)                 //如果该行还有可排的位置则继续循环
       {
           long p = pos & -pos;       //p取pos最右边为1的位,即该行放置皇后的位置(负数是以补码形式保存的)
           pos -= p;                  //将pos中对应的p为1的位置0,表示皇后已排,先不可排
           test(row + p, (ld + p) << 1, (rd + p) >> 1);   //在下一行排皇后
       }
   }
   else sum++;
}

int main(int argc, char *argv[])
{
   time_t tm;
   int n = 16;

   if (argc != 1)  n = atoi(argv[1]);
   tm = time(0);
   if ((n < 1) || (n > 32))
   {
       printf(" 只能计算1-32之间/n");
       exit(-1);
   }
   printf("%d 皇后/n", n);
   upperlim = (upperlim << n) - 1;

   test(0, 0, 0);
   printf("共有%ld种排列, 计算时间%d秒 /n", sum, (int) (time(0) - tm));
}