你所不知道的C 語言：bitwise 操作 - HackMD

2024-11-23

文章推薦指數： 80 %

投票人數：10人

延伸閱讀: Bitwise Operators in C (連結失效). Uses of Bitwise Operations or Why to Study Bits. Compression; Set operations; Encryption. The Magic of XOR. ownedthisnote Published LinkedwithGitHub Like8 Bookmark Subscribe Edit --- title:你所不知道的C語言：bitwise操作 image:https://imgur.com/IpzUymh.png description:複習數值系統，從應用案例引導學員掌握bitwise操作，從而邁向專業的程式開發 tags:DYKC,CLANG,CLANGUAGE --- #[你所不知道的C語言](https://hackmd.io/@sysprog/c-prog/):bitwise操作 Copyright(**慣C**)2020[宅色夫](http://wiki.csie.ncku.edu.tw/User/jserv) ==[直播錄影](https://youtu.be/S800OmVnN5o)== ##複習數值系統 *短片:[10進位、16進位，和60進位從何而來？](https://www.youtube.com/watch?v=8J7sAYoG50A) *複習[數值系統篇](https://hackmd.io/@sysprog/c-numerics) *[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation) *[BinaryandNumberRepresentation](https://www.bottomupcs.com/chapter01.xhtml):notes:記得要按右下方的Next >以下圖例取自[CS:APP第2章重點提示和練習](https://hackmd.io/@sysprog/CSAPP-ch2) ![](https://i.imgur.com/H33tREX.png) 不是所有的位元組合都能表示合理的數字，存取某些位元組合在特定機器上可能會造成嚴重錯誤，此種組合稱作陷阱表示法(traprepresentation)。

除非使用位元運算或是違反標準其他規定(如溢位)，一般的運算不可能產生陷阱表示法。

C語言標準明確允許實作自行決定在以下兩種狀況下是否是陷阱表示法： *型態為有號整數且正負號及值位元為特定組合時(三種格式各有一特殊組合) *填充位元為某些組合時:notes:[N1256註腳#44,45](http://port70.net/~nsz/c/c99/n1256.html#note44) ![](https://i.imgur.com/DGJUVgk.png) 位元運算會忽略填充位元，因此（等級不低於unsignedint的）無號整數可安心使用。

為求最大可攜性，位元運算不應該用在有號整數上。

在C11規格6.2.6.2Integertypes指出 >Forunsignedintegertypesotherthanunsignedchar,thebitsoftheobjectrepresentationshallbedividedintotwogroups:valuebitsandpaddingbits(thereneednotbeanyofthelatter).IfthereareNvaluebits,eachbitshallrepresentadifferentpowerof2between1and2^N−1^,sothatobjectsofthattypeshallbecapableofrepresentingvaluesfrom0to2^N−1^usingapurebinaryrepresentation;thisshallbeknownasthevaluerepresentation.Thevaluesofanypaddingbitsareunspecified. `uintN_t`和`intN_t`保證沒有填充位元，`intN_t`一定是二補數，而且`intN_t`不可能有陷阱表示法，堪稱是最安全的整數型態。

實作可能不提供這些型態，不過一旦提供，即保證符合性質。

:notes:[N12567.18.1.1](http://port70.net/~nsz/c/c99/n1256.html#7.18.1.1)p1~p3 位移運算子(Shiftoperator): *左移:`x<>y`:x右移y位元，右移出的位元會被丟棄。

兩種位移: *邏輯位移(Logicalshift):左側會補上0 *算術位移(Arithmeticshift):補上號數(signbit)也就是最高有效位元的值在左側例: X=10100010; Logicalshift:`x>>2`=`00101000` Arithmeticshift:`x>>2`=`11101000` 注意位移運算的兩種未定義狀況 *左移超過變數長度，其結果未定義; ```cpp inti=0xFFFFFFFF; i=i<<32;//此結果未定義 ``` *右移一個負數時，可能是邏輯位移或是算術位移，C語言標準未定義; 算術位移的應用，若要判斷一個int型態的變數`n`是否為正數，可用`n>>31`其等價於`n>=0?0:-1`. *右移如果是一個負數時，會變成正或著是負值，要注意編譯器如何實作。

編譯器甚至可以有編譯選項可改變此語意，gcc的實作上是使用arithmeticshift。

![](https://i.imgur.com/HAhmxxQ.png) 有號數x到無號數(U結尾)映射機制：非負數不變為x，負數轉換為大的正數(x+2^w^，最靠近0的負數映射最大，最小的負數被映射為剛好在二補數表達之外的無符號數)。

*例如w=4，二補數能表示的有號數範圍是-8[`1000`]～7[`0111`] 當無號數與有號數在C語言混合在單一表示式時，有號數會被轉換為無號數。

在運算子操作時會有些意外的結果。

有號數負值會因為轉換成2補數後，反而負值會大於正值。

因此要注意混用時的運算狀況。

案例: |變數1|變數2|比較結果|轉換後| |------------|-----------------|----|--------| |0|0U|==|unsigned| |-1|0||unsigned| |2147483647|-2147483647-1|>|signed| |2147483647U|-2147483647-1||signed| |(unsigned)-1|-2|>|unsigned| |2147483647|2147483648U||signed| 一個導致意外結果的案例: ```cpp intn=10; for(inti=n-1;i-sizeof(char)>=0;i--) printf("i:0x%x\n",i); ``` 這個例子會造成無窮迴圈，因為`sizeof`會回傳值是unsignedint型態，i變數也會被轉換為unsigned的形式，無號數0再減1就會變為`0xFFFFFFFF`而產生無窮迴圈。

![](https://i.imgur.com/G2AXbpz.png) 在有號整數上都可能產生陷阱表示法補充資訊:[WritingTMininC](http://csapp.cs.cmu.edu/3e/waside/waside-tmin.pdf) *Figure1列出ISOC90和ISOC99對於資料型態定義的落差 *注意Implications ![](https://i.imgur.com/7YvR10S.png) 延伸閱讀:[SignedandUnsignedNumbers](https://chi_gitbook.gitbooks.io/personal-note/content/signed_and_unsigned_numbers.html) 在[WhirlwindTourofARMAssembly](http://www.coranac.com/tonc/text/asm.htm)指出，若n是有號32-bit整數，那麼`n>>31`相當於`n>=0?0:-1` :-1:[bitwiseleftshiftoperationinvokesUndefinedBehaviourwhentheleftsideoperandhasnegativevalue](https://stackoverflow.com/questions/3784996/why-does-left-shift-operation-invoke-undefined-behaviour-when-the-left-side-opera) :-1:[Weirdbehaviorofrightshiftoperator(1>>32) ](https://stackoverflow.com/questions/3394259/weird-behavior-of-right-shift-operator-1-32/3394302#3394302) 若n是32-bit整數，那麼`abs(n)`等同於`((n>>31)^n)-(n>>31)` *當n是正數時: >`n>>31`是0;`n^0`仍是n;`n-0`仍是n *當n是負數時: >`n>>31`是-1;`-1`以2補數表示為`0xFFFFFFFF`;`n^(-1)`等同於1補數運算;最後再減`-1`，得到2補數運算的值 ![](https://i.imgur.com/cWiCbnq.png) 例如:unsignedinttounsignedshort ##BitwiseOperator *[CBitwiseOperatorsQuiz](http://doc.callmematthi.eu/C_Bitwise_Operators.html) *[線上測驗](https://pconrad.github.io/old_pconrad_cs16/topics/bitOps/)(附上解答) *[BitwisePractice](https://web.stanford.edu/class/archive/cs/cs107/cs107.1202/lab1/practice.html) ##做中學 Linux核心原始程式碼存在大量bit(-wise)operations(簡稱`bitops`)，頗多乍看像是魔法的C程式碼就是bitops的組合。

這裡舉個案例，觀察下方ASCII字元編號的二進位數值，可知道大寫'A'字元的編號是十進位65，對應於二進位的100_0001(請略去底線，只是為了視覺方便)，即2的6次方加1，那麼小寫'a'字母是緊接在大寫'Z'字母之後嘛？不是！小寫'a'字母的編號是十進位97，恰好跟大寫'A'字母相隔32，即2的5次方。

![](https://i.imgur.com/AipH6Qc.png) 為什麼ASCII採用不直覺的設計呢？我們繼續觀察： *大寫'G'=>71=>0100_0111 *小寫'g'=>103=>0110_0111 從二進位表示法清楚得知，`G`和`g`其實相差1個位元，換言之，透過XOR0010_0000(或C語言的`^32`)，就可實作出「大寫字母轉小寫」和「小寫字母轉大寫」的效果。

小提示：在GNU/Linux,FreeBSD,macOS上輸入"manascii"即可得到精美的ASCII表格，有八進位和十進位表示(至於為何UNIX系統和C語言存在八進位表示法，這是另外的故事)。

![](https://i.imgur.com/u1TaJ3s.png) 許多人使用的[vim](https://www.vim.org/)啟發自[BillJoy](https://en.wikipedia.org/wiki/Bill_Joy)在加州大學柏克萊分校就讀時所發展的`vi`編輯器，後者若干特性被[vim](https://www.vim.org/)保留，包含使用==hjkl==等按鍵分別表示游標的向左、向下、向上，及向右。

採用hjkl作為方向鍵的因素是，BillJoy當時採用的ADM-3A鍵盤沒有獨立方向鍵，不過後續的問題是：既然方向鍵和字母按鍵共用，那為何挑==hjkl==，而非asdf一類在[QWERTY鍵盤](https://en.wikipedia.org/wiki/QWERTY)橫向連續的按鍵呢？當我們回顧1967年ASCII的編碼規範，可發現前32個字元都是控制碼，讓人們得以透過這些特別字元來控制畫面和相關I/O，早期鍵盤的"control"按鍵就搭配這些特別字元使用。

"control"組合按鍵會將原本字元的第1個bit進行XOR，於是`H`字元對應ASCII編碼為100_1000(過去僅用7bit編碼)，組合"control"後(即Ctrl+H)會得到000_1000，也就是backspace的編碼，這也是為何在某些程式中按下backspace按鍵會得到`^H`輸出的原因。

相似地，當按下Ctrl+J時會得到000_1010，即linefeed 不只是上述ADM-3A鍵盤如此，當時大部分的電傳打字機(teletyper)也採用相同的慣例。

既然相鄰的H和J都有其對應游標移動的控制碼，也很自然地延伸到K和L按鍵。

###Setabit :::info wherenisthebitnumber,and0istheleastsignificantbit ::: ```cpp unsignedchara|=(1< /*bitclear: a:int, pos:bitpositiontoclear*/ #defineCLEARBIT(a,pos)(a&=~(1<>8)&0xff;/*leftmost(mostsignificant)byte*/ ``` ###signbit assuming16bit,2-byteshortinteger,two'scomplement: ```cpp boolsign=val&0x8000;//signbit ``` ###SettingandClearingaBit Thecodebelowshowshowtosetorclearabitofaninteger. ```cpp #include #include voidbinary(unsignedintn){ for(inti=256;i>0;i/=2){ if(n&i) printf("1"); else printf("0"); } printf("\n"); } boolgetBit(intn,intindex){ return((n&(1<0); } intsetBit(intn,intindex,boolb){ if(b) return(n|(1<=0;i--) printf("%d",getBit(num,i)); printf("\n"); /*setbit*/ index=6; printf("#Setting%d-thbit\n",index); num=setBit(num,index,true); for(inti=7;i>=0;i--) printf("%d",getBit(num,i)); printf("\n"); /*unset(clear)bit*/ index=4; printf("#Unsetting(Clearing)%d-thbit\n",index); num=setBit(num,index,false); for(inti=7;i>=0;i--) printf("%d",getBit(num,i)); printf("\n"); return0; } ``` Outputis: ``` Input 00010000 #Setting6-thbit 01010000 #Unsetting(Clearing)4-thbit 01000000 ``` 延伸閱讀:[BitwiseOperatorsinC(連結失效)](http://www2.mta.ac.il/~hbinsky/c%20content/Bits.pdf) *UsesofBitwiseOperationsorWhytoStudyBits *Compression *Setoperations *Encryption *TheMagicofXOR >`x^y==(~x&y)|(x&~y)` --- ##bitwise練習題 *[2018q1考古題](https://hackmd.io/s/rJh9U4Guf)/[參考解答](https://hackmd.io/s/S1f0tSyTG) *[2018q3考古題](https://hackmd.io/s/S1a9-YO_Q)/[參考解答](https://hackmd.io/s/By5KCaZam) *[2019q1考古題1](https://hackmd.io/@sysprog/SyrZMGYr4)/[參考解答](https://hackmd.io/@chenishi/S1DHQ3KrE)/[延伸閱讀](https://medium.com/fcamels-notes/%E4%BD%BF%E7%94%A8%E4%BD%8D%E5%85%83%E8%A8%88%E7%AE%97%E5%8A%A0%E9%80%9F%E6%B1%82%E8%A7%A3-n-queen-d20442f34110) *[2019q1考古題2](https://hackmd.io/@sysprog/H1Pik8M8E)/[參考解答](https://hackmd.io/@1IzBzEXXRsmj6-nLXZ9opw/B1vrcKcu4) *[2020q1考古題](https://hackmd.io/@sysprog/linux2020-quiz3)/[參考解答](https://hackmd.io/@Hsuhaoxiang/2020q3) *[2020q3考古題](https://hackmd.io/@sysprog/2020-quiz2)/[參考解答](https://hackmd.io/@RinHizakura/SJ5NuIANP) --- ##影像處理和bitwiseoperation ![](https://i.imgur.com/Lw7Qcln.png) 可從rasterization,equalizer,和算術去思考。

*[Jitblt:EfficientRun-timeCodeGenerationforDigitalCompositing](http://vpri.org/pdf/tr2008002_jitblt.pdf) *[GitHub](https://github.com/damelang/jitblt) -[]pipeline-1 ![](https://i.imgur.com/OdTz4zy.png) -[]pipeline-2 ![](https://i.imgur.com/ZXwTw4J.png) *新的發展:[Blend2D](https://blend2d.com/) *2DvectorgraphicsenginewritteninC++. *Itfeaturesabuilt-inJITcompilerthatgenerateshighperformance2Dpipelinesatruntime,whicharemuchfasterthanstaticpipelinesusedintoday's2Dengines.DynamicpipelineconstructionisthemaindifferencebetweenBlend2Dandother2Dengines,andguaranteesthehighestpossiblethroughtputbytakingadvantageofCPUextensionsdetectedatruntime. *Blend2Dprovidesalsoadeferredandasynchronousrendering,whichmakesitseamlesstointegratewithevent-basedenvironmentssuchasnode.jsandnextgenerationUItoolkits. 像素處理的程式碼片段: ```cpp unsignedshortblend(unsignedshortfg, unsignedshortbg, unsignedcharalpha){ //Splitforegroundintocomponents unsignedfg_r=fg>>11; unsignedfg_g=(fg>>5)&((1u<<6)-1); unsignedfg_b=fg&((1u<<5)-1); //Splitbackgroundintocomponents unsignedbg_r=bg>>11; unsignedbg_g=(bg>>5)&((1u<<6)-1); unsignedbg_b=bg&((1u<<5)-1); //Alphablendcomponents unsignedout_r=(fg_r*alpha+bg_r*(255-alpha))/255; unsignedout_g=(fg_g*alpha+bg_g*(255-alpha))/255; unsignedout_b=(fg_b*alpha+bg_b*(255-alpha))/255; //Packresult return(unsignedshort)((out_r<<11)| (out_g<<5)| (out_b); } ``` 其中"Alphablendcomponents"可透過改寫為以下: ```cpp unsignedout_r=fg_r*a+bg_r*(255-alpha); unsignedout_g=fg_g*a+bg_g*(255-alpha); unsignedout_b=fg_b*a+bg_b*(255-alpha); out_r=(out_r+1+(out_r>>8))>>8; out_g=(out_g+1+(out_g>>8))>>8; out_b=(out_b+1+(out_b>>8))>>8; ``` 參考資料: [what(r+1+(r>>8))>>8does?-stackoverflow](https://stackoverflow.com/questions/30237567/what-r1-r-8-8-does) ###案例分析給定每個pixel為32-bit的RGBA的bitmap，其轉換為黑白影像的函式為： ```cpp voidrgba_to_bw(uint32_t*bitmap,intwidth,intheight,longstride){ for(introw=0;row>24)&0xff; uint32_tr=(pixel>>16)&0xff; uint32_tg=(pixel>>8)&0xff; uint32_tb=pixel&0xff; uint32_tbw=(uint32_t)(r*0.299+g*0.587+b*0.114); bitmap[col+row*stride/4]=(a<<24)+ (bw<<16)+ (bw<<8)+ (bw); } } } ``` 人眼吸收綠色比其他顏色敏感，所以當影像變成灰階時，僅僅將紅色、綠色、藍色加總取平均，這是不夠的，常見的方法是將red*77,green*151+blue*28，這三個除數的總和為256，可使除法變簡單提出效能改善的方案： *建立表格加速浮點數操作(L1cache?) *減少位移數量 -[]考慮以下寫法 ```cpp bwPixel=table[rgbPixel&0x00ffffff]+rgbPixel&0xff000000; ``` :::info 16MB;表格太大 ::: -[]如果先計算針對「乘上0.299」一類的運算，先行計算後建立表格呢？ ```cpp bw=(uint32_t)mul_299[r]+(uint32_t)mul_587[g]+(uint32_t)mul_144[b]; bitmap[col+row*strike/4]=(a<<24)+(bw<<16)+(bw<<8)+bw; ``` :::info 降到32KB以內;cachefriendly ::: ###實作程式碼原始程式碼:[RGBAtoBW](https://github.com/charles620016/embedded-summer2015/tree/master/RGBAtoBW) BMP(BitMaP)檔是是很早以前微軟所開發並使用在Windows系統上的圖型格式，通常不壓縮，不像JPG,GIF,PNG會有破壞性或非破壞性的壓縮。

雖然BMP缺點是檔案非常大，不過因為沒有壓縮，即使不借助OpenCV、ImageMagick或.NETFramework等等，也可以很容易地直接用StandardCLibrary作影像處理。

BMP主要有四個部份組成: 1.BitmapFileHeader：MagicNumber(’BM’)、filesize、Offsettoimagedata 2.BitmapInfoHeader：imagewidthandheight、thenumberofbitsperpixel、Compressiontype 3.ColorTable(Palette) 4.Imagedata ![](https://hackpad-attachments.s3.amazonaws.com/charles620016.hackpad.com_U4inYKbSPUp_p.431773_1440518623822_Selection_001.bmp) -[]原始版本以下是使用一張1920x1080的BMP圖片，所得知的檔案資訊: ``` ====Header==== Signature=4D42 FileSize=8294456 DataOffset=54 ====Info====== Infosize=40 Width=1920 Height=1080 BitsPerPixel=32 Compression=0 ================ RGBAtoBWisinprogress.... Savethepicturesuccessfully! ExecutiontimeofrgbaToBw():0.034494 ``` ![](https://hackpad-attachments.s3.amazonaws.com/charles620016.hackpad.com_U4inYKbSPUp_p.431773_1440765925898_01_after.bmp) :::info 執行時間：0.034494sec ::: -[]Version1:[LookupTable](https://en.wikipedia.org/wiki/Lookup_table)(LUT) RGB分別都是8bit，可以建立三個大小為256bytes的table，這樣就不用在每次轉bw過程中進行浮點數運算。

*原本:`bw=(uint32_t)(r*0.299+g*0.587+b*0.114);` *查表:`bw=(uint32_t)(table_R[r]+table_G[g]+table_B[b]);` :::info 執行時間:`0.028148sec` ::: -[]Version2 使用pointer的offset取代原本的繁雜的bitwiseoperation。

```C uint32_t*pixel=bmp->data; r=(BYTE*)pixel+2; g=(BYTE*)pixel+1; b=(BYTE*)pixel; ``` :::info 執行時間:`0.020379sec` ::: -[]Version3 將上述Version1和Version2合併在一起 :::info 執行時間:`0.018061sec` ::: 用RaspberryPi2測試： ```shell CC=gcc-4.8 CFLAGS=-O0-Wall-ftree-vectorize-mcpu=cortex-a7-mfpu=neon-vfpv4-mfloat-abi=hard ``` *Original *ExecutiontimeofrgbaToBw():0.353600 *Version1:usingRGBtable *ExecutiontimeofrgbaToBw():0.319600 *Version2:usingpointerarithmetic *ExecutiontimeofrgbaToBw():0.251800 *Version3:versoin1+versoin2` *ExecutiontimeofrgbaToBw():0.226800 ##案例探討 *[位元旋轉實作和Linux核心案例](https://hackmd.io/@sysprog/bitwise-rotation) *[revsersebit原理和案例分析](https://hackmd.io/@sysprog/bitwise-reverse) 8 × Signin Email Password Forgotpassword or Byclickingbelow,youagreetoourtermsofservice. SigninviaFacebook SigninviaTwitter SigninviaGitHub SigninviaDropbox SigninviaGoogle NewtoHackMD?Signup