Bitwise Operation

Bitwise operator in C/C++

歡迎來到二進位的世界。電腦資料都是以二進位儲存,想當然程式語言的變數也都是以二進位儲存。在C/C++當中有幾個位元運算子:<< SHIFT LEFT、>> SHIFT RIGHT、& AND、| OR、^ XOR、~ NOT,可以對變數進行位元運算。接下來要介紹位元運算的一些用途。

<< SHIFT LEFT
>> SHIFT RIGHT

這兩個運算子的功能主要是移動一個變數中的所有位元,位元向左/向右移動之後,最高位/最低位的位元會消失,最低位/最高位的位元補0:

5 << 1 = 10	// 00101 的全部位元向左移動一位數變成 01010。
5 << 2 = 20	// 00101 的全部位元向左移動兩位數變成 10100。
5 >> 1 = 2	// 00101 的全部位元向右移動一位數變成 00010。
5 >> 2 = 1	// 00101 的全部位元向右移動一位數變成 00001。

在十進位當中,當全部位數向左移動一位時,數值大小會變成原來的十倍,向左移動兩位時,會變成原來的百倍。這種情形在二進位也是成立的,當全部位元向左移動一位時,會變成原來的兩倍,向左移動兩位時,會變成原來的四倍。至於往右移動也是類似道理,變成了除法而已。

由於電腦進行位元運算比乘法、除法運算快上許多,所以有很多專業的程式設計師,會利用位元運算來取代乘法、除法運算。優點是程式執行效率增加,缺點是程式碼可讀性變低:

& AND

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

&的功能是將兩個變數對應的位元進行AND邏輯運算,然後產生新變數。

   00000000000000000000000001110100 -> 116
 & 00000000000000000000000000101001 -> 41
 ----------------------------------
   00000000000000000000000000100000 -> 32

&的特色,就是可以判斷出位元是不是1。例如我們想要數一個變數有幾個位元是1:

| OR

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

|的功能是將兩個變數對應的位元進行OR邏輯運算,然後產生新變數。

   00000000000000000000000001110100 -> 116
 | 00000000000000000000000000101001 -> 41
 ----------------------------------
   00000000000000000000000001111101 -> 125

|的特色,就是把位元強制標記成1。例如我們想要把五位數標成1:

^ XOR

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

^的功能是將兩個變數對應的位元進行XOR邏輯運算,然後產生新變數。

   00000000000000000000000001110100 -> 116
 ^ 00000000000000000000000000101001 -> 41
 ----------------------------------
   00000000000000000000000001011101 -> 93

^的特色,就是把位元的0和1顛倒。例如我們想要顛倒第五位數:

~ NOT

~ 0 = 1
~ 1 = 0

~的功能是顛倒一個變數每一個位元的0和1。

 ~ 00000000000000000000000000000011 -> 3
 ----------------------------------
   11111111111111111111111111111100 -> -4

UVa 10469 10264

Bitwise Trick

交換兩個int變數

判斷一個整數是不是2的次方

整數加一與減一

整數變號

判斷一整數是偶數還是奇數

非負整數取模數,模數是二的冪次方。

整數取絕對值

平方根倒數

3D繪圖經常用到的一個運算,原理是牛頓法。

http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf

計算32位元整數有幾個位元是1

顛倒32位元整數的位元順序

32位元整數的最高位位元位置

原理是Binary Search。