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

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

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

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

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

C語言上的位運(yùn)算

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

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

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

C語言的邏輯運(yùn)算

C語言中的邏輯運(yùn)算有||、&&和!，這比較容易與剛才的|，&和~搞混。邏輯運(yùn)算比較特別，在這種運(yùn)算的結(jié)果中認(rèn)為所有非0的數(shù)值都是true，而為0的則為false。LZ在此寫了一個(gè)小程序，我們來簡單的看下二者的區(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);
}

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

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

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

C語言的移位運(yùn)算

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

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

本章小結(jié)

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