技術 > 位運算
目錄
No. 1
  位運算
   在很多係統程序中常要求在位(bit)一級進行運算或處理。C語言提供了位運算的功能, 這使得C語言也能像匯編語言一樣用來編寫係統程序。
  一、位運算符C語言提供了六種位運算符:
  & 按位與
  | 按位或
  ^ 按位異或
  ~ 取反
  << 左移
  >> 右移
  1. 按位與運算 按位與運算符"&"是雙目運算符。其功能是參與運算的兩數各對應的二進位相與。衹有對應的兩個二進位均為1時,結果位纔為1 ,否則為0。參與運算的數以補碼方式出現。
  例如:9&5可寫算式如下: 00001001 (9的二進製補碼)&00000101 (5的二進製補碼) 00000001 (1的二進製補碼)可見9&5=1。
  按位與運算通常用來對某些位清0或保留某些位。例如把a 的高八位清 0 , 保留低八位, 可作 a&255 運算 ( 255 的二進製數為0000000011111111)。
  main(){
  int a=9,b=5,c;
  c=a&b;
  printf("a=%d
  b=%d
  c=%d
  ",a,b,c);
  }
  2. 按位或運算 按位或運算符“|”是雙目運算符。其功能是參與運算的兩數各對應的二進位相或。衹要對應的二個二進位有一個為1時,結果位就為1。參與運算的兩個數均以補碼出現。
  例如:9|5可寫算式如下: 00001001|00000101
  00001101 (十進製為13)可見9|5=13
  main(){
  int a=9,b=5,c;
  c=a|b;
  printf("a=%d
  b=%d
  c=%d
  ",a,b,c);
  }
  3. 按位異或運算 按位異或運算符“^”是雙目運算符。其功能是參與運算的兩數各對應的二進位相異或,當兩對應的二進位相異時,結果為1。參與運算數仍以補碼出現,例如9^5可寫成算式如下: 00001001^00000101 00001100 (十進製為12)
  main(){
  int a=9;
  a=a^15;
  printf("a=%d
  ",a);
  }
  4. 求反運算 求反運算符~為單目運算符,具有右結合性。 其功能是對參與運算的數的各二進位按位求反。例如~9的運算為: ~(0000000000001001)結果為:1111111111110110
  5. 左移運算 左移運算符“<<”是雙目運算符。其功能把“<< ”左邊的運算數的各二進位全部左移若幹位,由“<<”右邊的數指定移動的位數,
  高位丟棄,低位補0。例如: a<<4 指把a的各二進位嚮左移動4位。如a=00000011(十進製3),左移4位後為00110000(十進製48)。6. 右移運算 右移運算符“>>”是雙目運算符。其功能是把“>> ”左邊的運算數的各二進位全部右移若幹位,“>>”右邊的數指定移動的位數。
  例如:設 a=15,a>>2 表示把000001111右移為00000011(十進製3)。 應該說明的是,對於有符號數,在右移時,符號位將隨同移動。當為正數時, 最高位補0,而為負數時,符號位為1,最高位是補0或是補1 取决於編譯係統的規定。turbo c和很多係統規定為補1。
  main(){
  unsigned a,b;
  printf("input a number: ");
  scanf("%d",&a);
  b=a>>5;
  b=b&15;
  printf("a=%d b=%d
  ",a,b);
  }
  請再看一例!
  main(){
  char a='a',b='b';
  int p,c,d;
  p=a;
  p=(p<<8)|b;
  d=p&0xff;
  c=(p&0xff00)>>8;
  printf("a=%d
  b=%d
  c=%d
  d=%d
  ",a,b,c,d);
  }
  位域
  有些信息在存儲時,並不需要占用一個完整的字節, 而衹需占幾個或一個二進製位。例如在存放一個開關量時,衹有0和1 兩種狀態, 用一位二進位即可。為了節省存儲空間,並使處理簡便,C語言又提供了一種數據結構,稱為“位域”或“位段”。所謂“位域”是把一個字節中的二進位劃分為幾個不同的區域, 並說明每個區域的位數。每個域有一個域名,允許在程序中按域名進行操作。 這樣就可以把幾個不同的對象用一個字節的二進製位域來表示。一、位域的定義和位域變量的說明位域定義與結構定義相仿,其形式為:
  struct 位域結構名
  { 位域列表 };
  其中位域列表的形式為: 類型說明符 位域名:位域長度
  例如:
  struct bs
  {
  int a:8;
  int b:2;
  int c:6;
  };
  位域變量的說明與結構變量說明的方式相同。 可采用先定義後說明,同時定義說明或者直接說明這三種方式。例如:
  struct bs
  {
  int a:8;
  int b:2;
  int c:6;
  }data;
  說明data為bs變量,共占兩個字節。其中位域a占8位,位域b占2位,位域c占6位。對於位域的定義尚有以下幾點說明:
  1. 一個位域必須存儲在同一個字節中,不能跨兩個字節。如一個字節所剩空間不夠存放另一位域時,應從下一單元起存放該位域。也可以有意使某位域從下一單元開始。例如:
  struct bs
  {
  unsigned a:4
  unsigned :0 /*空域*/
  unsigned b:4 /*從下一單元開始存放*/
  unsigned c:4
  }
  在這個位域定義中,a占第一字節的4位,4位填0表示不使用,b從第二字節開始,占用4位,c占用4位。
  2. 由於位域不允許跨兩個字節,因此位域的長度不能大於一個字節的長度,也就是說不能超過8位二進位。
  3. 位域可以無位域名,這時它衹用來作填充或調整位置。無名的位域是不能使用的。例如:
  struct k
  {
  int a:1
  int :2 /*該2位不能使用*/
  int b:3
  int c:2
  };
  從以上分析可以看出,位域在本質上就是一種結構類型, 不過其成員是按二進位分配的。
  二、位域的使用位域的使用和結構成員的使用相同,其一般形式為: 位域變量名·位域名 位域允許用各種格式輸出。
  main(){
  struct bs
  {
  unsigned a:1;
  unsigned b:3;
  unsigned c:4;
  } bit,*pbit;
  bit.a=1;
  bit.b=7;
  bit.c=15;
  printf("%d,%d,%d
  ",bit.a,bit.b,bit.c);
  pbit=&bit;
  pbit->a=0;
  pbit->b&=3;
  pbit->c|=1;
  printf("%d,%d,%d
  ",pbit->a,pbit->b,pbit->c);
  }
  上例程序中定義了位域結構bs,三個位域為a,b,c。說明了bs類型的變量bit和指嚮bs類型的指針變量pbit。這表示位域也是可以使用指針的。
  程序的9、10、11三行分別給三個位域賦值。( 應註意賦值不能超過該位域的允許範圍)程序第12行以整型量格式輸出三個域的內容。第13行把位域變量bit的地址送給指針變量pbit。第14行用指針方式給位域a重新賦值,賦為0。第15行使用了復合的位運算符"&=", 該行相當於: pbit->b=pbit->b&3位域b中原有值為7,與3作按位與運算的結果為3(111&011=011,十進製值為3)。同樣,程序第16行中使用了復合位運算"|=", 相當於: pbit->c=pbit->c|1其結果為15。程序第17行用指針方式輸出了這三個域的值。
  類型定義符typedef
  C語言不僅提供了豐富的數據類型,而且還允許由用戶自己定義類型說明符,也就是說允許由用戶為數據類型取“別名”。 類型定義符typedef即可用來完成此功能。例如,有整型量a,b,其說明如下: int aa,b; 其中int是整型變量的類型說明符。int的完整寫法為integer,
  為了增加程序的可讀性,可把整型說明符用typedef定義為: typedef int integer 這以後就可用integer來代替int作整型變量的類型說明了。 例如: integer a,b;它等效於: int a,b; 用typedef定義數組、指針、結構等類型將帶來很大的方便,不僅使程序書寫簡單而且使意義更為明確,因而增強了可讀性。例如:
  typedef char name; 表示name是字符數組類型,數組長度為20。
  然後可用name 說明變量,如: name a1,a2,s1,s2;完全等效於: char a1,a2,s1,s2
  又如:
  typedef struct stu{ char name;
  int age;
  char sex;
  } stu;
  定義stu表示stu的結構類型,然後可用stu來說明結構變量: stu body1,body2;
  typedef定義的一般形式為: typedef 原類型名 新類型名 其中原類型名中含有定義部分,新類型名一般用大寫表示, 以
  便於區別。在有時也可用宏定義來代替typedef的功能,但是宏定義是由預處理完成的,而typedef則是在編譯時完成的,後者更為靈活方便。
No. 2
  位運算簡介及實用技巧(一):基礎篇
  什麽是位運算
  程序中的所有數在計算機內存中都是以二進製的形式儲存的。位運算說穿了,就是直接對整數在內存中的二進製位進行操作。比如,and運算本來是一個邏輯運算符,但整數與整數之間也可以進行and運算。舉個例子,6的二進製是110,11的二進製是1011,那麽6 and 11的結果就是2,它是二進製對應位進行邏輯運算的結果(0表示False,1表示True,空位都當0處理):
  110
  AND 1011
  ---------------
  0010 --> 2
  由於位運算直接對內存數據進行操作,不需要轉成十進製,因此處理速度非常快。當然有人會說,這個快了有什麽用,計算6 and 11沒有什麽實際意義啊。這一係列的文章就將告訴你,位運算到底可以幹什麽,有些什麽經典應用,以及如何用位運算優化你的程序。
  Pascal和C中的位運算符號
  下面的a和b都是整數類型,則:
  C語言 | Pascal語言
  -------+-------------
  a&b | a and b
  a|b | a or b
  a ^ b | a xor b
  ~a | not a
  a << b| a shl b
  a >> b | a shr b
  註意C中的邏輯運算和位運算符號是不同的。520|1314=1834,但520||1314=1,因為邏輯運算時520和1314都相當於True。同樣的,!a和~a也是有區別的。
  各種位運算的使用
  === 1. and運算 ===
  and運算通常用於二進製取位操作,例如一個數 and 1的結果就是取二進製的最末位。這可以用來判斷一個整數的奇偶,二進製的最末位為0表示該數為偶數,最末位為1表示該數為奇數.
  === 2. or運算 ===
  or運算通常用於二進製特定位上的無條件賦值,例如一個數or 1的結果就是把二進製最末位強行變成1。如果需要把二進製最末位變成0,對這個數or 1之後再減一就可以了,其實際意義就是把這個數強行變成最接近的偶數。
  === 3. xor運算 ===
  xor運算通常用於對二進製的特定一位進行取反操作,因為異或可以這樣定義:0和1異或0都不變,異或1則取反。
  xor運算的逆運算是它本身,也就是說兩次異或同一個數最後結果不變,即(a xor b) xor b = a。xor運算可以用於簡單的加密,比如我想對我MM說1314520,但怕別人知道,於是雙方約定拿我的生日19880516作為密鑰。1314520 xor 19880516 = 20665500,我就把20665500告訴MM。MM再次計算20665500 xor 19880516的值,得到1314520,於是她就明白了我的企圖。
  下面我們看另外一個東西。定義兩個符號#和@(我怎麽找不到那個圈裏有個叉的字符),這兩個符號互為逆運算,也就是說(x # y) @ y = x。現在依次執行下面三條命令,結果是什麽?
  x <- x # y
  y <- x @ y
  x <- x @ y
  執行了第一句後x變成了x # y。那麽第二句實質就是y <- x # y @ y,由於#和@互為逆運算,那麽此時的y變成了原來的x。第三句中x實際上被賦值為(x # y) @ x,如果#運算具有交換律,那麽賦值後x就變成最初的y了。這三句話的結果是,x和y的位置互換了。
  加法和減法互為逆運算,並且加法滿足交換律。把#換成+,把@換成-,我們可以寫出一個不需要臨時變量的swap過程(Pascal)。
  procedure swap(var a,b:longint);
  begin
  a:=a + b;
  b:=a - b;
  a:=a - b;
  end;
  好了,剛纔不是說xor的逆運算是它本身嗎?於是我們就有了一個看起來非常詭異的swap過程:
  procedure swap(var a,b:longint);
  begin
  a:=a xor b;
  b:=a xor b;
  a:=a xor b;
  end;
  === 4. not運算 ===
  not運算的定義是把內存中的0和1全部取反。使用not運算時要格外小心,你需要註意整數類型有沒有符號。如果not的對象是無符號整數(不能表示負數),那麽得到的值就是它與該類型上界的差,因為無符號類型的數是用00到$FFFF依次表示的。下面的兩個程序(僅語言不同)均返回65435。
  var
  a:word;
  begin
  a:=100;
  a:=not a;
  writeln(a);
  end.
  #include <stdio.h>
  int main()
  {
  unsigned short a=100;
  a = ~a;
  printf( "%dn", a );
  return 0;
  }
  如果not的對象是有符號的整數,情況就不一樣了,稍後我們會在“整數類型的儲存”小節中提到。
  === 5. shl運算 ===
  a shl b就表示把a轉為二進製後左移b位(在後面添b個0)。例如100的二進製為1100100,而110010000轉成十進製是400,那麽100 shl 2 = 400。可以看出,a shl b的值實際上就是a乘以2的b次方,因為在二進製數後添一個0就相當於該數乘以2。
  通常認為a shl 1比a * 2更快,因為前者是更底層一些的操作。因此程序中乘以2的操作請盡量用左移一位來代替。
  定義一些常量可能會用到shl運算。你可以方便地用1 shl 16 - 1來表示65535。很多算法和數據結構要求數據規模必須是2的幂,此時可以用shl來定義Max_N等常量。
  === 6. shr運算 ===
  和shl相似,a shr b表示二進製右移b位(去掉末b位),相當於a除以2的b次方(取整)。我們也經常用shr 1來代替div 2,比如二分查找、堆的插入操作等等。想辦法用shr代替除法運算可以使程序效率大大提高。最大公約數的二進製算法用除以2操作來代替慢得出奇的mod運算,效率可以提高60%。
  位運算的簡單應用
  有時我們的程序需要一個規模不大的Hash表來記錄狀態。比如,做數獨時我們需要27個Hash表來統計每一行、每一列和每一個小九宮格裏已經有哪些數了。此時,我們可以用27個小於2^9的整數進行記錄。例如,一個衹填了2和5的小九宮格就用數字18表示(二進製為000010010),而某一行的狀態為511則表示這一行已經填滿。需要改變狀態時我們不需要把這個數轉成二進製修改後再轉回去,而是直接進行位操作。在搜索時,把狀態表示成整數可以更好地進行判重等操作。這道題是在搜索中使用位運算加速的經典例子。以後我們會看到更多的例子。
  下面列舉了一些常見的二進製位的變換操作。
  功能 | 示例 | 位運算
  ----------------------+---------------------------+--------------------
  去掉最後一位 | (101101->10110) | x shr 1
  在最後加一個0 | (101101->1011010) | x shl 1
  在最後加一個1 | (101101->1011011) | x shl 1+1
  把最後一位變成1 | (101100->101101) | x or 1
  把最後一位變成0 | (101101->101100) | x or 1-1
  最後一位取反 | (101101->101100) | x xor 1
  把右數第k位變成1 | (101001->101101,k=3) | x or (1 shl (k-1))
  把右數第k位變成0 | (101101->101001,k=3) | x and not (1 shl (k-1))
  右數第k位取反 | (101001->101101,k=3) | x xor (1 shl (k-1))
  取末三位 | (1101101->101) | x and 7
  取末k位 | (1101101->1101,k=5) | x and (1 shl k-1)
  取右數第k位 | (1101101->1,k=4) | x shr (k-1) and 1
  把末k位變成1 | (101001->101111,k=4) | x or (1 shl k-1)
  末k位取反 | (101001->100110,k=4) | x xor (1 shl k-1)
  把右邊連續的1變成0 | (100101111->100100000) | x and (x+1)
  把右起第一個0變成1 | (100101111->100111111) | x or (x+1)
  把右邊連續的0變成1 | (11011000->11011111) | x or (x-1)
  取右邊連續的1 | (100101111->1111) | (x xor (x+1)) shr 1
  去掉右起第一個1的左邊 | (100101000->1000) | x and (x xor (x-1))
  最後這一個在樹狀數組中會用到。
  Pascal和C中的16進製表示
  Pascal中需要在16進製數前加$符號表示,C中需要在前面加0x來表示。這個以後我們會經常用到。
  整數類型的儲存
  我們前面所說的位運算都沒有涉及負數,都假設這些運算是在unsigned/word類型(衹能表示正數的整型)上進行操作。但計算機如何處理有正負符號的整數類型呢?下面兩個程序都是考察16位整數的儲存方式(衹是語言不同)。
  var
  a,b:integer;
  begin
  a:=00;
  b:=01;
  write(a,' ',b,' ');
  a:=$FFFE;
  b:=$FFFF;
  write(a,' ',b,' ');
  a:=FFF;
  b:=00;
  writeln(a,' ',b);
  end.
  #include <stdio.h>
  int main()
  {
  short int a, b;
  a = 0x0000;
  b = 0x0001;
  printf( "%d %d ", a, b );
  a = 0xFFFE;
  b = 0xFFFF;
  printf( "%d %d ", a, b );
  a = 0x7FFF;
  b = 0x8000;
  printf( "%d %dn", a, b );
  return 0;
  }
  兩個程序的輸出均為0 1 -2 -1 32767 -32768。其中前兩個數是內存值最小的時候,中間兩個數則是內存值最大的時候,最後輸出的兩個數是正數與負數的分界處。由此你可以清楚地看到計算機是如何儲存一個整數的:計算機用00到FFF依次表示0到32767的數,剩下的00到$FFFF依次表示-32768到-1的數。32位有符號整數的儲存方式也是類似的。稍加註意你會發現,二進製的第一位是用來表示正負號的,0表示正,1表示負。這裏有一個問題:0本來既不是正數,也不是負數,但它占用了00的位置,因此有符號的整數類型範圍中正數個數比負數少一個。對一個有符號的數進行not運算後,最高位的變化將導致正負顛倒,並且數的絶對值會差1。也就是說,not a實際上等於-a-1。這種整數儲存方式叫做“補碼”。
  位運算簡介及實用技巧(二):進階篇(1)
  ===== 真正強的東西來了! =====
  二進製中的1有奇數個還是偶數個
  我們可以用下面的代碼來計算一個32位整數的二進製中1的個數的奇偶性,當輸入數據的二進製表示裏有偶數個數字1時程序輸出0,有奇數個則輸出1。例如,1314520的二進製101000000111011011000中有9個1,則x=1314520時程序輸出1。
  var
  i,x,c:longint;
  begin
  readln(x);
  c:=0;
  for i:=1 to 32 do
  begin
  c:=c + x and 1;
  x:=x shr 1;
  end;
  writeln( c and 1 );
  end.
  但這樣的效率並不高,位運算的神奇之處還沒有體現出來。
  同樣是判斷二進製中1的個數的奇偶性,下面這段代碼就強了。你能看出這個代碼的原理嗎?
  var
  x:longint;
  begin
  readln(x);
  x:=x xor (x shr 1);
  x:=x xor (x shr 2);
  x:=x xor (x shr 4);
  x:=x xor (x shr 8);
  x:=x xor (x shr 16);
  writeln(x and 1);
  end.
  為了說明上面這段代碼的原理,我們還是拿1314520出來說事。1314520的二進製為101000000111011011000,第一次異或操作的結果如下:
  00000000000101000000111011011000
  XOR 0000000000010100000011101101100
  ---------------------------------------
  00000000000111100000100110110100
  得到的結果是一個新的二進製數,其中右起第i位上的數表示原數中第i和i+1位上有奇數個1還是偶數個1。比如,最右邊那個0表示原數末兩位有偶數個1,右起第3位上的1就表示原數的這個位置和前一個位置中有奇數個1。對這個數進行第二次異或的結果如下:
  00000000000111100000100110110100
  XOR 000000000001111000001001101101
  ---------------------------------------
  00000000000110011000101111011001
  結果裏的每個1表示原數的該位置及其前面三個位置中共有奇數個1,每個0就表示原數對應的四個位置上共偶數個1。一直做到第五次異或結束後,得到的二進製數的最末位就表示整個32位數裏有多少個1,這就是我們最終想要的答案。
  計算二進製中的1的個數
  同樣假設x是一個32位整數。經過下面五次賦值後,x的值就是原數的二進製表示中數字1的個數。比如,初始時x為1314520(網友抓狂:能不能換一個數啊),那麽最後x就變成了9,它表示1314520的二進製中有9個1。
  x := (x and 555555) + ((x shr 1) and 555555);
  x := (x and 333333) + ((x shr 2) and 333333);
  x := (x and F0F0F0F) + ((x shr 4) and F0F0F0F);
  x := (x and FF00FF) + ((x shr 8) and FF00FF);
  x := (x and 00FFFF) + ((x shr 16) and 00FFFF);
  為了便於解說,我們下面僅說明這個程序是如何對一個8位整數進行處理的。我們拿數字211(我們班某MM的生日)來開刀。211的二進製為11010011。
  +---+---+---+---+---+---+---+---+
  | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原數
  +---+---+---+---+---+---+---+---+
  | 1 0 | 0 1 | 0 0 | 1 0 | <---第一次運算後
  +-------+-------+-------+-------+
  | 0 0 1 1 | 0 0 1 0 | <---第二次運算後
  +---------------+---------------+
  | 0 0 0 0 0 1 0 1 | <---第三次運算後,得數為5
  +-------------------------------+
  整個程序是一個分治的思想。第一次我們把每相鄰的兩位加起來,得到每兩位裏1的個數,比如前兩位10就表示原數的前兩位有2個1。第二次我們繼續兩兩相加,10+01=11,00+10=10,得到的結果是00110010,它表示原數前4位有3個1,末4位有2個1。最後一次我們把0011和0010加起來,得到的就是整個二進製中1的個數。程序中巧妙地使用取位和右移,比如第二行中333333的二進製為00110011001100....,用它和x做and運算就相當於以2為單位間隔取數。shr的作用就是讓加法運算的相同數位對齊。
  二分查找32位整數的前導0個數
  這裏用的C語言,我直接Copy的Hacker's Delight上的代碼。這段代碼寫成C要好看些,寫成Pascal的話會出現很多begin和end,搞得代碼很難看。程序思想是二分查找,應該很簡單,我就不細說了。
  int nlz(unsigned x)
  {
  int n;
  if (x == 0) return(32);
  n = 1;
  if ((x >> 16) == 0) {n = n +16; x = x <<16;}
  if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
  if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
  if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
  n = n - (x >> 31);
  return n;
  }
  衹用位運算來取絶對值
  這是一個非常有趣的問題。大傢先自己想想吧,Ctrl+A顯示答案。
  答案:假設x為32位整數,則x xor (not (x shr 31) + 1) + x shr 31的結果是x的絶對值
  x shr 31是二進製的最高位,它用來表示x的符號。如果它為0(x為正),則not (x shr 31) + 1等於000000,異或任何數結果都不變;如果最高位為1(x為負),則not (x shr 31) + 1等於$FFFFFFFF,x異或它相當於所有數位取反,異或完後再加一。
  高低位交換
  這個題實際上是我出的,做為學校內部NOIp模擬賽的第一題。題目是這樣:
  給出一個小於2^32的正整數。這個數可以用一個32位的二進製數表示(不足32位用0補足)。我們稱這個二進製數的前16位為“高位”,16位為“低位”。將它的高低位交換,我們可以得到一個新的數。試問這個新的數是多少(用十進製表示)。
  例如,數1314520用二進製表示為0000 0000 0001 0100 0000 1110 1101 1000(添加了11個前導0補足為32位),其中前16位為高位,即0000 0000 0001 0100;16位為低位,即0000 1110 1101 1000。將它的高低位進行交換,我們得到了一個新的二進製數0000 1110 1101 1000 0000 0000 0001 0100。它即是十進製的249036820。
  當時幾乎沒有人想到用一句位操作來代替冗長的程序。使用位運算的話兩句話就完了。
  var
  n:dword;
  begin
  readln( n );
  writeln( (n shr 16) or (n shl 16) );
  end.
  而事實上,Pascal有一個係統函數swap直接就可以用。
  二進製逆序
  下面的程序讀入一個32位整數並輸出它的二進製倒序後所表示的數。
  輸入: 1314520 (二進製為00000000000101000000111011011000)
  輸出: 460335104 (二進製為00011011011100000010100000000000)
  var
  x:dword;
  begin
  readln(x);
  x := (x and 555555) shl 1 or (x and $AAAAAAAA) shr 1;
  x := (x and 333333) shl 2 or (x and $CCCCCCCC) shr 2;
  x := (x and F0F0F0F) shl 4 or (x and $F0F0F0F0) shr 4;
  x := (x and FF00FF) shl 8 or (x and $FF00FF00) shr 8;
  x := (x and 00FFFF) shl 16 or (x and $FFFF0000) shr 16;
  writeln(x);
  end.
  它的原理和剛纔求二進製中1的個數那個例題是大致相同的。程序首先交換每相鄰兩位上的數,以後把互相交換過的數看成一個整體,繼續進行以2位為單位、以4位為單位的左右對換操作。我們再次用8位整數211來演示程序執行過程:
  +---+---+---+---+---+---+---+---+
  | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原數
  +---+---+---+---+---+---+---+---+
  | 1 1 | 1 0 | 0 0 | 1 1 | <---第一次運算後
  +-------+-------+-------+-------+
  | 1 0 1 1 | 1 1 0 0 | <---第二次運算後
  +---------------+---------------+
  | 1 1 0 0 1 0 1 1 | <---第三次運算後
  +-------------------------------+
  位運算簡介及實用技巧(三):進階篇(2)
  今天我們來看兩個稍微復雜一點的例子。
  n皇后問題位運算
  n皇后問題是啥我就不說了吧,學編程的肯定都見過。下面的十多行代碼是n皇后問題的一個高效位運算程序,看到過的人都誇它牛。初始時,upperlim:=(1 shl n)-1。主程序調用test(0,0,0)sum的值就是n皇后總的解數。拿這個去交USACO,0.3s,暴爽。
  procedure test(row,ld,rd:longint);
  var
  pos,p:longint;
  begin
  if row<>upperlim then
  begin
  pos:=upperlim and not (row or ld or rd);
  while pos<>0 do
  begin
  p:=pos and -pos;
  pos:=pos-p;
  test(row+p,(ld+p)shl 1,(rd+p)shr 1);
  end;
  end
  else inc(sum);
  end;
  乍一看似乎完全摸不着頭腦,實際上整個程序是非常容易理解的。這裏還是建議大傢自己單步運行一探究竟,實在沒研究出來再看下面的解說。
  和普通算法一樣,這是一個遞歸過程,程序一行一行地尋找可以放皇后的地方。過程帶三個參數,row、ld和rd,分別表示在縱列和兩個對角綫方向的限製條件下這一行的哪些地方不能放。我們以6x6的棋盤為例,看看程序是怎麽工作的。假設現在已經遞歸到第四層,前三層放的子已經標在左圖上了。紅色、藍色和緑色的綫分別表示三個方向上有衝突的位置,位於該行上的衝突位置就用row、ld和rd中的1來表示。把它們三個並起來,得到該行所有的禁位,取反後就得到所有可以放的位置(用pos來表示)。前面說過-a相當於not a + 1,這裏的代碼第6行就相當於pos and (not pos + 1),其結果是取出最右邊的那個1。這樣,p就表示該行的某個可以放子的位置,把它從pos中移除並遞歸調用test過程。註意遞歸調用時三個參數的變化,每個參數都加上了一個禁位,但兩個對角綫方向的禁位對下一行的影響需要平移一位。最後,如果遞歸到某個時候發現row=111111了,說明六個皇后全放進去了,此時程序從第1行跳到第11行,找到的解的個數加一。
  ~~~~====~~~~===== 華麗的分割綫 =====~~~~====~~~~
  Gray碼
  假如我有4個潛在的GF,我需要决定最終到底和誰在一起。一個簡單的辦法就是,依次和每個MM交往一段時間,最後選擇給我帶來的“滿意度”最大的MM。但看了dd牛的理論後,事情開始變得復雜了:我可以選擇和多個MM在一起。這樣,需要考核的狀態變成了2^4=16種(當然包括0000這一狀態,因為我有可能是玻璃)。現在的問題就是,我應該用什麽順序來遍歷這16種狀態呢?
  傳統的做法是,用二進製數的順序來遍歷所有可能的組合。也就是說,我需要以0000->0001->0010->0011->0100->...->1111這樣的順序對每種狀態進行測試。這個順序很不科學,很多時候狀態的轉移都很耗時。比如從0111到1000時我需要暫時甩掉當前所有的3個MM,然後去把第4個MM。同時改變所有MM與我的關係是一件何等巨大的工程啊。因此,我希望知道,是否有一種方法可以使得,從沒有MM這一狀態出發,每次衹改變我和一個MM的關係(追或者甩),15次操作後恰好遍歷完所有可能的組合(最終狀態不一定是1111)。大傢自己先試一試看行不行。
  解决這個問題的方法很巧妙。我們來說明,假如我們已經知道了n=2時的合法遍歷順序,我們如何得到n=3的遍歷順序。顯然,n=2的遍歷順序如下:
  00
  01
  11
  10
  你可能已經想到了如何把上面的遍歷順序擴展到n=3的情況。n=3時一共有8種狀態,其中前面4個把n=2的遍歷順序照搬下來,然後把它們對稱翻折下去並在最前面加上1作為後面4個狀態:
  000
  001
  011
  010 ↑
  --------
  110 ↓
  111
  101
  100
  用這種方法得到的遍歷順序顯然符合要求。首先,上面8個狀態恰好是n=3時的所有8種組合,因為它們是在n=2的全部四種組合的基礎上考慮選不選第3個元素所得到的。然後我們看到,後面一半的狀態應該和前面一半一樣滿足“相鄰狀態間僅一位不同”的限製,而“鏡面”處則是最前面那一位數不同。再次翻折三階遍歷順序,我們就得到了剛纔的問題的答案:
  0000
  0001
  0011
  0010
  0110
  0111
  0101
  0100
  1100
  1101
  1111
  1110
  1010
  1011
  1001
  1000
  這種遍歷順序作為一種編碼方式存在,叫做Gray碼(寫個中文讓蜘蛛來抓:格雷碼)。它的應用範圍很廣。比如,n階的Gray碼相當於在n維立方體上的Hamilton回路,因為沿着立方體上的邊走一步,n維坐標中衹會有一個值改變。再比如,Gray碼和Hanoi塔問題等價。Gray碼改變的是第幾個數,Hanoi塔就該移動哪個盤子。比如,3階的Gray碼每次改變的元素所在位置依次為1-2-1-3-1-2-1,這正好是3階Hanoi塔每次移動盤子編號。如果我們可以快速求出Gray碼的第n個數是多少,我們就可以輸出任意步數後Hanoi塔的移動步驟。現在我告訴你,Gray碼的第n個數(從0算起)是n xor (n shr 1),你能想出來這是為什麽嗎?先自己想想吧。
  下面我們把二進製數和Gray碼都寫在下面,可以看到左邊的數異或自身右移的結果就等於右邊的數。
  二進製數 Gray碼
  000 000
  001 001
  010 011
  011 010
  100 110
  101 111
  110 101
  111 100
  從二進製數的角度看,“鏡像”位置上的數即是對原數進行not運算後的結果。比如,第3個數010和倒數第3個數101的每一位都正好相反。假設這兩個數分別為x和y,那麽x xor (x shr 1)和y xor (y shr 1)的結果衹有一點不同:後者的首位是1,前者的首位是0。而這正好是Gray碼的生成方法。這就說明了,Gray碼的第n個數確實是n xor (n shr 1)。
  今年四月份mashuo給我看了這道題,是二維意義上的Gray碼。題目大意是說,把0到2^(n+m)-1的數寫成2^n * 2^m的矩陣,使得位置相鄰兩數的二進製表示衹有一位之差。答案其實很簡單,所有數都是由m位的Gray碼和n位Gray碼拼接而成,需要用左移操作和or運算完成。完整的代碼如下:
  var
  x,y,m,n,u:longint;
  begin
  readln(m,n);
  for x:=0 to 1 shl m-1 do begin
  u:=(x xor (x shr 1)) shl n; //輸出數的左邊是一個m位的Gray碼
  for y:=0 to 1 shl n-1 do
  write(u or (y xor (y shr 1)),' '); //並上一個n位Gray碼
  writeln;
  end;
  end.
  位運算簡介及實用技巧(四):實戰篇
  <BLOCKQUOTE>Problem : 費解的開關
  06年NOIp模擬賽(一) by Matrix67 第四題
  問題描述
  你玩過“拉燈”遊戲嗎?25盞燈排成一個5x5的方形。每一個燈都有一個開關,遊戲者可以改變它的狀態。每一步,遊戲者可以改變某一個燈的狀態。遊戲者改變一個燈的狀態會産生連鎖反應:和這個燈上下左右相鄰的燈也要相應地改變其狀態。
  我們用數字“1”表示一盞開着的燈,用數字“0”表示關着的燈。下面這種狀態
  10111
  01101
  10111
  10000
  11011
  在改變了最左上角的燈的狀態後將變成:
  01111
  11101
  10111
  10000
  11011
  再改變它正中間的燈後狀態將變成:
  01111
  11001
  11001
  10100
  11011
  給定一些遊戲的初始狀態,編寫程序判斷遊戲者是否可能在6步以內使所有的燈都變亮。
  輸入格式
  第一行有一個正整數n,代表數據中共有n個待解决的遊戲初始狀態。
  以下若幹行數據分為n組,每組數據有5行,每行5個字符。每組數據描述了一個遊戲的初始狀態。各組數據間用一個空行分隔。
  對於30%的數據,n<=5;
  對於100%的數據,n<=500。
  輸出格式
  輸出數據一共有n行,每行有一個小於等於6的整數,它表示對於輸入數據中對應的遊戲狀態最少需要幾步才能使所有燈變亮。
  對於某一個遊戲初始狀態,若6步以內無法使所有燈變亮,請輸出“-1”。
  樣例輸入
  3
  00111
  01011
  10001
  11010
  11100
  11101
  11101
  11110
  11111
  11111
  01111
  11111
  11111
  11111
  11111
  樣例輸出
  3
  2
  -1
  </BLOCKQUOTE>
  程序代碼
  <CODE>const
  BigPrime=3214567;
  MaxStep=6;
  type
  pointer=^rec;
  rec=record
  v:longint;
  step:integer;
  next:pointer;
  end;
  var
  total:longint;
  hash:array[0..BigPrime-1]of pointer;
  q:array[1..400000]of rec;
  function update(a:longint;p:integer):longint;
  begin
  a:=a xor (1 shl p);
  if p mod 5<>0 then a:=a xor (1 shl (p-1));
  if (p+1) mod 5<>0 then a:=a xor (1 shl (p+1));
  if p<20 then a:=a xor (1 shl (p+5));
  if p>4 then a:=a xor (1 shl (p-5));
  exit(a);
  end;
  function find(a:longint;step:integer):boolean;
  var
  now:pointer;
  begin
  now:=hash[a mod BigPrime];
  while now<>nil do
  begin
  if now^.v=a then exit(true);
  now:=now^.next;
  end;
  new(now);
  now^.v:=a;
  now^.step:=step;
  now^.next:=hash[a mod BigPrime];
  hash[a mod BigPrime]:=now;
  total:=total+1;
  exit(false);
  end;
  procedure solve;
  var
  p:integer;
  close:longint=0;
  open:longint=1;
  begin
  find(1 shl 25-1,0);
  q.v:=1 shl 25-1;
  q.step:=0;
  repeat
  inc(close);
  for p:=0 to 24 do
  if not find(update(q[close].v,p),q[close].step+1) and (q[close].step+1<MaxStep) then
  begin
  open:=open+1;
  q[open].v:=update(q[close].v,p);
  q[open].step:=q[close].step+1;
  end;
  until close>=open;
  end;
  procedure print(a:longint);
  var
  now:pointer;
  begin
  now:=hash[a mod BigPrime];
  while now<>nil do
  begin
  if now^.v=a then
  begin
  writeln(now^.step);
  exit;
  end;
  now:=now^.next;
  end;
  writeln(-1);
  end;
  procedure main;
  var
  ch:char;
  i,j,n:integer;
  t:longint;
  begin
  readln(n);
  for i:=1 to n do
  begin
  t:=0;
  for j:=1 to 25 do
  begin
  read(ch);
  t:=t*2+ord(ch)-48;
  if j mod 5=0 then readln;
  end;
  print(t);
  if i<n then readln;
  end;
  end;
  begin
  solve;
  main;
  end.</CODE>
  ======================= 性感的分割綫 =======================
  <BLOCKQUOTE>Problem : garden / 和MM逛花園
  題目來源
  問題描述
  花園設計強調,簡單就是美。Matrix67常去的花園有着非常簡單的佈局:花園的所有景點的位置都是“對齊”了的,這些景點可以看作是平面坐標上的格點。相鄰的景點之間有小路相連,這些小路全部平行於坐標軸。景點和小路組成了一個“不完整的網格”。
  一個典型的花園佈局如左圖所示。花園佈局在6行4列的網格上,花園的16個景點的位置用紅色標註在了圖中。黑色綫條表示景點間的小路,其餘灰色部分實際並不存在。
  Matrix67 的生日那天,他要帶着他的MM在花園裏遊玩。Matrix67不會帶MM兩次經過同一個景點,因此每個景點最多被遊覽一次。他和他的MM邊走邊聊,他們是如此的投入以致於他們從不會“主動地拐彎”。也就是說,除非前方已沒有景點或是前方的景點已經訪問過,否則他們會一直往前走下去。當前方景點不存在或已遊覽過時,Matrix67會帶MM另選一個方向繼續前進。由於景點個數有限,訪問過的景點將越來越多,遲早會出現不能再走的情況(即四個方向上的相鄰景點都訪問過了),此時他們將結束花園的遊覽。Matrix67希望知道以這種方式遊覽花園是否有可能遍歷所有的景點。Matrix67可以選擇從任意一個景點開始遊覽,以任意一個景點結束。
  在上圖所示的花園佈局中,一種可能的遊覽方式如右圖所示。這種瀏覽方式從(1,2)出發,以(2,4)結束,經過每個景點恰好一次。
  輸入格式
  第一行輸入兩個用空格隔開的正整數m和n,表示花園被佈局在m行n列的網格上。
  以下m行每行n個字符,字符“0”表示該位置沒有景點,字符“1”表示對應位置有景點。這些數字之間沒有空格。
  輸出格式
  你的程序需要尋找滿足“不主動拐彎”性質且遍歷所有景點的遊覽路綫。
  如果沒有這樣的遊覽路綫,請輸出一行“Impossible”(不帶引號,註意大小寫)。
  如果存在遊覽路綫,請依次輸出你的方案中訪問的景點的坐標,每行輸出一個。坐標的表示格式為“(x,y)”,代表第x行第y列。
  如果有多種方案,你衹需要輸出其中一種即可。評測係統可以判斷你的方案的正確性。
  樣例輸入
  6 4
  1100
  1001
  1111
  1100
  1110
  1110
  樣例輸出
  (1,2)
  (1,1)
  (2,1)
  (3,1)
  (4,1)
  (5,1)
  (6,1)
  (6,2)
  (6,3)
  (5,3)
  (5,2)
  (4,2)
  (3,2)
  (3,3)
  (3,4)
  (2,4)
  數據規模
  對於30%的數據,n,m<=5;
  對於100%的數據,n,m<=10。
  </BLOCKQUOTE>
  程序代碼:
  <CODE>program garden;
  const
  dir:array[1..4,1..2]of integer=
  ((1,0),(0,1),(-1,0),(0,-1));
  type
  arr=array[1..10]of integer;
  rec=record x,y:integer;end;
  var
  map:array[0..11,0..11]of boolean;
  ans:array[1..100]of rec;
  n,m,max:integer;
  step:integer=1;
  state:arr;
  procedure readp;
  var
  i,j:integer;
  ch:char;
  begin
  readln(m,n);
  for i:=1 to n do
  begin
  for j:=1 to m do
  begin
  read(ch);
  map[i,j]:=(ch='1');
  inc(max,ord( map[i,j] ))
  end;
  readln;
  end;
  end;
  procedure writep;
  var
  i:integer;
  begin
  for i:=1 to step do
  writeln( '(' , ans.x , ',' , ans.y , ')' );
  end;
  procedure solve(x,y:integer);
  var
  tx,ty,d:integer;
  step_cache:integer;
  state_cache:arr;
  begin
  step_cache:=step;
  state_cache:=state;
  if step=max then
  begin
  writep;
  exit;
  end;
  for d:=1 to 4 do
  begin
  tx:=x+dir[d,1];
  ty:=y+dir[d,2];
  while map[tx,ty] and ( not state[tx] and(1 shl (ty-1) )>0) do
  begin
  inc(step);
  ans[step].x:=tx;
  ans[step].y:=ty;
  state[tx]:=state[tx] or ( 1 shl (ty-1) );
  tx:=tx+dir[d,1];
  ty:=ty+dir[d,2];
  end;
  tx:=tx-dir[d,1];
  ty:=ty-dir[d,2];
  if (tx<>x) or (ty<>y) then solve(tx,ty);
  state:=state_cache;
  step:=step_cache;
  end;
  end;
  {====main====}
  var
  i,j:integer;
  begin
  assign(input,'garden.in');
  reset(input);
  assign(output,'garden.out');
  rewrite(output);
  readp;
  for i:=1 to n do
  for j:=1 to m do
  if map[i,j] then
  begin
  ans.x:=i;
  ans.y:=j;
  state:=1 shl (j-1);
  solve(i,j);
  state:=0;
  end;
  close(input);
  close(output);
  end.</CODE>
  對C語言中位運算的一點補充:(位數不同的運算數之間的運算規則)-
  C語言中,位運算的對象可以是整型(int)和字符型(char)數據。(整形數據可以直接轉化成二進製數,字符型數據在內存中以它的ASCII碼值存放,也可以站化成二進製數)當兩個運算數類型不同時,位數亦會不同。遇到這種情況,係統將自動進行如下處理:
  1將兩個運算數右端對齊。
  2 再將位數短的一個運算數往高位擴充,即:無符號數和正整數左側用0補全;負數左側用1補全;然後對位數相等的兩個運算數,按位進行運算。
英文解釋
  1. :  position action
包含詞
逐位運算移位運算符