关于位运算

       关于位运算，自从做过了“黑白棋游戏”之后，深感位运算之强大！在节约时间和空间很有帮助，常被拿来作优化之用。

       学习位运算我个人感觉有两点很重要：1耐心 2精益求精。

在下来的题目分析中，大家将会有强烈的体会。

文章结构：

1.        位运算的基本介绍

a)        移位运算

b)       与运算

c)        或运算

d)       非运算

e)        异或运算

2.        常见注意问题

3.        实战问题解决

a)        位基本操作 PKU 2453

b)       位压缩技术 PKU 2443

c)        位操作在BFS中的优化PKU 2965

4.        参考网页及文献

按位左右移位运算符

按位左右移位运算符是最常用的两个，即便没有用过也用过它的重载：cout<< 和cin>> 吧！

<<1 = * 2

<<2 = * 4

...

>>1 = / 2

>>2 = / 4

...

移位运算符包括：

“>> 右移”；“<< 左移”；“>>> 无符号右移”

例子：

-5>>3=-1

1111 11111111 1111 1111 1111 1111 1011

1111 11111111 1111 1111 1111 1111 1111

其结果与 Math.floor((double)-5/(2*2*2)) 完全相同。

-5<<3=-40

1111 11111111 1111 1111 1111 1111 1011

1111 11111111 1111 1111 1111 1101 1000

其结果与 -5*2*2*2 完全相同。

5>>3=0

0000 00000000 0000 0000 0000 0000 0101

0000 00000000 0000 0000 0000 0000 0000

其结果与 5/(2*2*2) 完全相同。

5<<3=40

0000 00000000 0000 0000 0000 0000 0101

0000 00000000 0000 0000 0000 0010 1000

其结果与 5*2*2*2 完全相同。

-5>>>3=536870911

1111 1111 1111 1111 1111 1111 1111 1011

0001 1111 1111 1111 1111 1111 1111 1111

无论正数、负数，它们的右移、左移、无符号右移 32 位都是其本身，比如 -5<<32=-5、-5>>32=-5、-5>>>32=-5。

一个有趣的现象是，把 1 左移 31 位再右移 31 位，其结果为 -1。

0000 00000000 0000 0000 0000 0000 0001

1000 00000000 0000 0000 0000 0000 0000

1111 11111111 1111 1111 1111 1111 1111

按位与运算（&）

&在C语言编程中怎么用，比如X=2，Y=3，X&Y为多少?

按位与运算 按位与运算符"&"是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时，结果位才为1 ，否则为0。参与运算的数以补码方式出现。

例如：2&3可写算式如下： 10 (2的二进制)&11(5的二进制补码) 10 (2的二进制)可见2&3=2。

10

& 11

------

10

在实际编程的应用中，我在判奇偶性的时候喜欢用(n&1)，如果为1则是奇数，如果为0则是偶数。因为不管这个数有多数位，决定奇偶的只可能是最后一位。

清零特定位 (mask中特定位置0，其它位为1，s=s&mask)

取某数中指定位 (mask中特定位置1，其它位为0，s=s&mask)

常用来将源操作数某些位置1，其它位不变。 (mask中特定位置1，其它位为0s=s|mask)

按位或运算（|）

按位或运算符“|”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的二个二进位有一个为1时，结果位就为1。参与运算的两个数均以补码出现。

例如：9|5可写算式如下：

    00001001

   | 00000101

    00001101        (十进制为13)可见9|5=13

按位非运算（~）

对一个表达式执行按位“非”（取反）。

result =~ expression

执行按位非操作，该操作的结果如下所示：

0101   (expression)

----

1010   (result)

异或XOR运算（^）

异或的运算方法是一个二进制运算：

 1^1=0

 0^0=0

 1^0=1

 0^1=1

 两者相等为0,不等为1.

 这样我们发现交换两个整数的值时可以不用第三个参数。

 如a=11,b=9.以下是二进制

 a=a^b=1011^1001=0010;

 b=b^a=1001^0010=1011;

 a=a^b=0010^1011=1001;

 这样一来a=9,b=13了。

应用：

使特定位的值取反 (mask中特定位置1，其它位为0 s=s^mask)

不引入第三变量，交换两个变量的值 (设 a=a1,b=b1)

　　目 标 操 作 操作后状态

　　a=a1^b1 a=a^ba=a1^b1,b=b1

　　b=a1^b1^b1 b=a^b a=a1^b1,b=a1

　　a=b1^a1^a1 a=a^b a=b1,b=a1

好的，介绍完位运算的基本操作，现在我们看一下位运算中一些常见要注意的问题

1、优先级

这是个非常严重的问题，在进行位运算的时候优先级太容易被忽略掉了

尤其要注意的：

移位运算符, 单目的取反运算符~的优先级比比较运算符高。但是，&, |, ^的优先级是比比较运算符低的！，这点一定要注意

如6 & 6 > 4的结果是0， 而不是 true; (6 & 6) > 4的结果才是true，所以要注意勤加括号

2、速度

位运算的速度是非常快的，你甚至可以忽略他的耗时，但是毕竟操作肯定是有耗损的。

所以，应该尽量使用

^=， |= ，&=之类的操作，比如说a ^= b， 速度比 a = a ^ b快，因为前者是直接在a上进行操作，而 a = a ^ b的第二个a，是一个a的副本，可见在操作中程序对a复制了一次，运算的结果又对原来的a做了一次赋值

3、范围（要当心移位运算时发生范围溢出）

实战问题：

位基本操作 PKU 2453 An Easy Problem

http://acm.pku.edu.cn/JudgeOnline/problem?id=2453

我们还是从简单的题目开始看

首先是PKU的2453,这题本身就是设计就是很清楚的位运算

题目的大意是给一个数I要求出一个比I大的最小值，这个值二进制的表示1的数量要和I中1的数目相同。

那么首先我们可以想到的方法是，对相同的I的排列数，不用通同位运算得解，但是效率应该不会很高，如果要提高效率或者可以研究一个1的位置变换的规律，比如当I中只有一个1的时候，这时，答案只需将I左移一位：1à2 ，4à8

其次，我们想到的肯定是位操作来解决，运用位操作的高效应该可以用枚举来完成此题。

我们可以很容易地想到这样的枚举方式：

for (i=I+1;;i++) If (i中1的个数和I相同) break;

print(i);

这样的话要处理的之剩下，如何判断i中1的个数是否和I相同

求出i中1的个数：

首先题目最大的数为：1000000 得到的2进制有20位之多

可以确定的是，最大的这个数的解不会超出20位

写一个函数传入n:

const int M = 20;

int cnt = 0;

for (i=0;i<=M;i++) if ((n>>i)&1) cnt++;

return cnt;

这样便可以求出一个数n中1的个数了。

具体AC代码：(C++)

#include <iostream>

using namespace std;

const int M = 21;

int num(int n)

{

       inti,cnt = 0;

       for(i=0;i<=M;i++)

              if((n>>i)&1)

                     cnt++;

       returncnt;

}

int main()

{

       inti,I;

       while(scanf("%d",&I)!=EOF,I)

       {

              intnumI = num(I);

              for(i=I+1;;i++)

                     if(num(i) == numI)

                            break;

              printf("%d\n",i);

       }

       return0;

}

以上代码的时间复杂度大约为O(nm)

虽然AC了，但这题光凭枚举效率一定是不高的，看一下运行的情况：

2453 Accepted 204K 219MSC++ 342B

为了提高时间效率，其实这道题还是可以找到规律的

其解法为：从右向左，找到第一个“01”以便进位

那么我们把01里的1向前进一位，变成10，它后面的1要移到最右边

实现：我们可以从右向左遍历这个数，找到第一个’01’，进位后把后面的1移到最右边

这样的一个算法，可以写成O(n+m)也可以优化到O(n)

我用优化的方法写了一下：

具体AC代码：(C++)

#include <iostream>

using namespace std;

const int M = 21;

int main()

{

    inti,j,k,I;

   while (scanf("%d",&I)!=EOF,I)

    {

         int numOfRZero = 0;

         int flag;

         for (i=0;i<=M;i++)

         {

             if ((I>>i)&1)

             {

                  if(!((I>>(i+1))&1))

                  {

                      I+=(1<<i);

                      flag = i;

                      break;

                  }

             }

             else

                  numOfRZero++;

         }

         int cleaner = 0xffffff; //用来将后面的几位清零

         int clean = 0xffffff;

         cleaner <<=  flag;

         cleaner &= clean;

         I &= cleaner; // 将后面的几位清零

         clean >>= (24-(flag-numOfRZero));

         I |= clean;

         printf("%d\n",I);

    }

   return 0;   

}

运行结果：

2453 Accepted 204K 0MSC++ 1120B

终于0MS AC ，但这样大家就满足了吗？！

我不得不提，我们应该清楚一点：其实位运算的最高境界是：无遍历

也是就是在常数的时间效率里得解。

高手AC CODE：（C）

#include <stdio.h>

int main()

{

    intn,x;

   while(scanf("%d",&n),n)

    {

        x=n&-n;

       printf("%d\n",n+x+(n^n+x)/x/4);

    }

       return0;

}

两行代码，无遍历，0MS，两变量

一切搞定，我想这就是最高的境界吧

虽然我不能想到如此优的解法，

但这两句代码，将对我们的位操作学习，有无尽的启发！

位压缩技术 PKU 2454 Set Operation

http://acm.pku.edu.cn/JudgeOnline/problem?id=2454

OK，唾沫横飞地分析完一道题中位运算的基本操作

现在我们可以深入地学习位压缩存储技术

PKU2454 这是一道看似简单的题目，但是庞大的测试数据将是我们的第一个BOSS

题意：给定一定数目的集合，然后每给出一对数据i，j判断是否它们在某个集合中同时出现过。（这样的题最好不要给中大描述，他们一定也会用一句话硬要把它说表达出来）。

对于这样的题目，我们的第一反应是，存入数组，模拟一个个集合，然后查找。

但是一看数据量很庞大，于是我用了HASH技术，把每个集合的查找时间降低到O(1)，

这样对于一组数据的总体时间只要O(n)，n的最坏情况为1000，还是可以接受的，以下是我的代码：

#include<iostream>

usingnamespace std;

bools[1005][10005];

intmain()

{

       int i,j,k,m,t,temp,n;

       while (scanf("%d",&n)!=EOF)

       {

              memset(s,0,sizeof(s));

              for (i=0;i<n;i++)

              {

                     scanf("%d",&t);

                     for (j=0,k=0;j<t;j++)

                     {

                            scanf("%d",&temp);

                            s[i][temp] = 1;   //标记这个数已用

                     }

              }

              //---------------------------------------------

              scanf("%d",&m);

              int a,b;

              for (i=0;i<m;i++)

              {

                     scanf("%d%d",&a,&b);

                     for (j=0;j<n;j++)

                     {

                            if(s[j][a]&& s[j][b])

                            {

                                   printf("Yes\n");

                                   break;

                            }

                     }

                     if (j == n)

                            printf("No\n");

              }

       }

       return 0;

}

运行结果：

2443 Time Limit Exceeded C++ 616B

我已经优化过了还超时！我哭~~！看了一下Discuss，有人说是位压缩技术

但是这道题怎么想也想不出可以比我以上代码的更优的位压缩方式

后来受高人启发，压缩的不是数据而是位置，即压缩集合编号。

这样不但压的空间，对查找到的时间也可以在常数时间内完成

再运用位操作中的与运算，就可以把时间降到O(n/(sizeof(int)*8))了                               

AC CODE：

//为了快速解题，下面的代码我采用了中式英文注释

#include<iostream>

usingnamespace std;

ints[10005][33];

intmain()

{

       int i,j,k,m,t,temp,n;

       int a,b;

       while (scanf("%d",&n)!=EOF)

       {

              memset(s,0,sizeof(s));

              for (i=0;i<n;i++)

              {

                     scanf("%d",&t);//num of sets

                     for (j=0;j<t;j++)

                     {

                            scanf("%d",&temp);//element of each set

                            //calculate thepostion of the element

                            int bitPos =(1<<(i%32)); //the position of 1 means the bit position

                            if((s[temp][i/32]&bitPos) == 0) //if elements repeat ,drop it ..else save it

                                   s[temp][i/32]+= bitPos;

                     }

              }

              scanf("%d",&m);

              for (i=0;i<m;i++)

              {

                     scanf("%d%d",&a,&b);

                     // seach sets use bit op

                     for (j=0;j<33;j++) //nowwe just need to seach 32 elems

                     {

                            if (s[a][j] &s[b][j]) // if there are the same pos 1 in two set num

                                   break;                      //       itmeans these two in the same set

                     }

                     if (j == 33)printf("No\n");

                     elseprintf("Yes\n");

              }

       }

       return 0;

}

2443Accepted 1496K 782MS C++ 1001B

位操作在BFS中的优化

这项技术我是从“黑白棋游戏”中学的，大家可以看一下题报告：

http://blog.csdn.net/jqandjq/archive/2008/12/02/3430846.aspx

后来发现的很多搜索和枚举都可以用它来优化，不过对思维要求是要很清晰。

PKU 2965 The Pilots Brothers'refrigerator

http://acm.pku.edu.cn/JudgeOnline/problem?id=2965

题目的大意是：有一扇门，上面有16（4*4）个开关，要把门打开就要让16个开关都为打开的状态。现在给你的初始状态至少有一个是关闭的，你改变一个开关的状态时，相应的行和列的开关都会被改变，那么问怎么做才能使开关全开。

这是一题再经典不过的搜索题了，不过我们要用位运算来优化此题

我们可以用一个INT型来表示一扇门的状态，1为关门0为打开。

当改变一个状态的时候，只要对相应行列的状态做一个XOR运算就OK了

剩下的就全看搜索的功底了

这道题出得很好，主体的要求需要我们用BFS

而输出的时候为了打印路径，需要我们用DFS（用一般递归就OK）

两种搜索集合在一道题里了。

AC CODE：

#include<iostream>

#include<queue>

usingnamespace std;

boolbfs();

intchange[4][4] =

{

       0xf888,0xf444,0xf222,0xf111,

       0x8f88,0x4f44,0x2f22,0x1f11,

       0x88f8,0x44f4,0x22f2,0x11f1,

       0x888f,0x444f,0x222f,0x111f

};

structNode

{

       int x,y;

       int last;

       int step;

};

intstart,temp;

Nodestate[70000];

boolused[70000];

int flag;

voidfinds(int n)

{

       if (state[n].last == -1)

              return;

       finds(state[n].last);

       printf("%d%d\n",state[n].x+1,state[n].y+1);

       return;

}

intmain()

{

       int i,j,k,m,n,t;

       char str[4][4];

       start = 0;

    char c;

    int num = 32768;

              for (i = 0; i < 4; ++i)

              {

                     for (j = 0; j < 4; ++j)

                     {

                            scanf("%c",&c);

                            if (c == '+')

                                   start += num;

                            num >>= 1;

                     }

                     getchar();

              }

              //-------------------------------------------------------

              memset(used,0,sizeof(used));

              flag = 0;

              bfs();

        printf("%d\n",state[0].step);

        finds(0);

       return 0;

}

boolbfs()

{

       int i,j,t=-1;

       int head = 0;

       int tail = 1;

       queue <int> Q;

       Q.push(start);

       used[start] = 1;

       state[start].last = -1;

       state[start].step = 0;

       while (!Q.empty() && t!=0)

       {

              temp = Q.front();

              Q.pop();

              for (i=0;i<4;i++)

              {

                     for (j=0;j<4;j++)

                     {

                            t =temp^change[i][j];

                            if (!used[t])

                            {

                                   Q.push(t);

                                   state[t].last= temp;

                                   state[t].step= state[temp].step + 1;

                                   state[t].x =i;

                                   state[t].y =j;

                                   used[t] = 1;

                                   if (t == 0)

                                   {

                                          break;

                                   }

                            }

                     }

              }

       }

       return 0;

}

相关例题：

PKU：2453 2443 1753 2965

（2081 2050 1324 3460附加网摘题目，不作重点要求）

.

参考网页及文献：

按位左右移位运算符

http://www.nshen.net/blog/article.asp?id=437

按位与运算符

http://wqp1977wqp.blog.163.com/blog/static/119448722007454246783/

按位或运算符

http://geniusvic.blog.hexun.com/21245303_d.html

按位非运算符

http://doc.51windows.net/jscript5/?url=/jscript5/html/jsoprbitwisenot.htm

A bit of fun: fun with bits  By bmerry

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation

Victordu PKU 2443 位运算

http://www.cppblog.com/Victordu/archive/2008/02/18/42887.aspx