位运算

学习状态压缩必须要先搞懂位运算这是集中位运算的符号与其作用。

名称	C/C++样式	Pascal样式	简记法则
按位与	&	*and*	全一则一，否则为零
按位或	\|	or	有一则一，否则为零
按位取反	~	*not*	是零则一，是一则零
按位异或	^	*xor*	不同则一，相同则零
左移位	<<	*shl*	*a<<k等价于a2**k
右移位	>>	*shr*	a>>k等价于a/2k

优先级：not>and>xor>or；

位运算的应用：

（1）获取一个或多个固定为的值

　　　假设x = 1010(10进制的10)

　　　我们要获取从右边第二位的值，那么我们可以这样来获取

　　　x&(1<<1)也就是

　　　x: 　　　　　　1010

　　　1<<1：　0010

　　　x&(1<<1)：　0010

　　　这样我们就可以通过判断x&(1<<1)是否等于0来知道这一位是0还是1了。

　　　x&(1<<n) 就是获取第n-1位的值。

（2）把一个或多个固定为的值置为零

　　　假设x = 1010（10进制的10）

　　　我们要把从右边第二位的值置为零，那么我们可以这样来做

　　　x&(~(1<<1))也就是

　　　x　　　　　　　 1010

　　　~（1<<1） 1101

　　　x&（~（1<<1）） 1000

　　　x&(~(1<<n)) 就是把x的第n-1位变成0

　　　这是我写的第一个位运算的代码虽然很水还是贴出来纪念一下吧……sad

　　　题意是n*n的棋盘上放n个車有多少种方案。

　　　显然是n！所以下面的代码就是在计算n！……sad

 1 #include<cstdio>
 2 #include<cstring>
 3 
 4 int a[65][65];
 5 
 6 int check(int q)
 7 {
 8     int p = 0;
 9     int t = 1;
10     while(t <= q)
11     {
12         if(q&t) p++;
14         t <<= 1;
15     }
16     return p;
17 }
18 
19 int main()
20 {
21     int n,t,i,j;
22     while(scanf("%d",&n) != EOF)
23     {
24         memset(a,0,sizeof(a));
25         t = 1;
26         for(i = 0;i < n; i++)
27         {
28             a[1][1<<i] = 1;
29         }
30 
31         for(i = 2;i <= n; i++)
32         {
33             for(j = 1;j <= (1<<n); j++)
34             {
35                 int c = check(j);//check（j）查找j转换为二进制之后有几个1；

36                 if(c == i)
37                 {
38                     for(t = 0;t < n; t++)
39                     {
40                         int k = (1<<t);
41                         if((j&k) != 0)
42                         {
43                             int h = j&(~k);
44                             a[i][j] += a[i-1][h];
45                         }
46                     }
47                 }
48             }
49         }
50 
51         printf("%d! = %d\n",n,a[n][(1<<n)-1]);
52     }
53     return 0;
54 }