關于位運算

       關于位運算，自從做過了“黑白棋遊戲”之後，深感位運算之強大！在節約時間和空間很有幫助，常被拿來作優化之用。

       學習位運算我個人感覺有兩點很重要：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