布爾代數(shù)上的位運算

布爾代數(shù)是一個數(shù)學知識體系，它在0和1的二進制值上演化而來的。

我們不需要去徹底的了解這個知識體系，但是里面定義了幾種二進制的運算，卻是我們在平時的編程過程當中也會遇到的。這四種運算分別是或、與、非和異或。下圖展示了在布爾代數(shù)的知識體系中，對這四種運算的定義。

從左至右依次是非、與、或以及異或。這個圖闡述的是針對一位二進制的運算結果，我們可以將其擴大到N位二進制。比如兩個二進制[aw,aw-1...a1]和[bw,bw-1...b1]，它們的四種運算則是對兩者每一個相對應的位上做相應的運算。

也就是說，倘若假設結果是[cw,cw-1...c1]的話，那么對于任意ci都滿足 ci = ai (|,&,^) bi，如果是對[aw,aw-1...a1]進行非運算的話，那么ci = ~ai。

C語言上的位運算

在C語言中，也支持位運算，而它的計算方式就是布爾代數(shù)中的位運算。位運算我們最常使用的是掩碼的方式。比如我們知道一個整數(shù)x，如果我們想取得這個整數(shù)的最后一個字節(jié)的整數(shù)值的話，就可以采用位運算。就像下面這樣。

#include <stdio.h>
   
int main(){
    unsigned int i = 0x12345678;
    unsigned int j = 0xFF;
    unsigned int k = i & j;
    printf("%X\n",k);
}

最終我們希望得到的結果是78，也就是整數(shù)i的最后一個字節(jié)的值，我們使用掩碼0xFF以及與運算過濾掉整數(shù)i的高位的三個字節(jié)。以下是結果。

C語言的邏輯運算

C語言中的邏輯運算有||、&&和!，這比較容易與剛才的|，&和~搞混。邏輯運算比較特別，在這種運算的結果中認為所有非0的數(shù)值都是true，而為0的則為false。LZ在此寫了一個小程序，我們來簡單的看下二者的區(qū)別。

#include <stdio.h>
   
int main(){
     unsigned int x = 0x12345678;
     unsigned int i = !x;
     unsigned int j = ~x;
     unsigned int m = !!x;
     unsigned int n = ~~x;
     printf("%u %u\n",i,j);
     printf("%u %u\n",m,n);
}

從這個程序的結果可以很明顯的看出!和~運算的區(qū)別，我們來直接看結果吧。

結果很明顯，左邊是!x以及!!x的結果，只有0和1，而右邊則是~x和~~x的結果。這里可以很明顯的看出邏輯非與位的非運算的區(qū)別。前者只有0和1，而后者則是對每一位二進制值取反。

除了結果上的區(qū)別之外，它們二者還有一個區(qū)別，就是邏輯運算倘若可以根據(jù)第一個表達式確定結果的話，那么將不會計算第二個表達式。舉個簡單的例子，假設有兩個表達式a和b，對于a && b，倘若a為假，則不會計算b表達式的值。但是對于a & b則不同，無論a表達式的值為何，都要計算b表達式的值。

C語言的移位運算

移位運算分為兩種，左移和右移。對于一個二進制數(shù)[aw,aw-1,...a1]來說，如果將它進行左移運算，則x << k = [aw-k,aw-k-1,...a1,0,...0]。此時相當于最高的那k位都被丟棄了，在最右端補了k個0。而對于x >> k來說，也就是右移運算，與左移是類似的，只不過為了照顧有符號數(shù)，有時候需要在左端補最高位而不是0。而對于補0的情況，則稱為邏輯右移，補最高位的則稱為算術右移。

也就是說，對于邏輯右移來說，x >> k = [0,...0,aw,aw-1,...ak+1]，而對于算術右移來說，x >> k = [aw,...aw,aw,aw-1,...ak+1]。

本章小結

本章主要只是簡單的介紹了下C語言中的位運算，下一章將會介紹一下整數(shù)的表示方式。