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。

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

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

int n = 5; n = n >> 1; // 即是 n = n / 2 之意。 /* 該式子也可寫成 n >>= 1 或 n /= 2。 */

& AND

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

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

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

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

int count_bit_1(int n) { // 由右往左看n的每一個位元。 int c = 0; for (int i=0; i<32; ++i) // int變數有32個位元 if (n & (1 << i)) c++; return c; } int count_bit_1(int n) { // 一樣是由右往左，但是每次都刪掉n的最左邊位元。 int c = 0; for (; n; n>>=1) if (n & 1) c++; return c; }

| OR

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

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

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

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

int mark_5th_bit(int n) { return n | (1 << 4); }

^ XOR

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

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

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

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

int reverse_5th_bit(int n) { return n ^ (1 << 4); }

~ NOT

~ 0 = 1
~ 1 = 0

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

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

UVa 10469 10264

交換兩個int變數

void swap(int& x, int& y) { x = x ^ y; y = x ^ y; x = x ^ y; } void swap(int& x, int& y) { x ^= y ^= x ^= y; }

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

bool ispow2(int n) { return (n & -n) == n; }

整數加一與減一

// 注意：比直接加一和減一還要慢。 void add_one(int& x) { return -~x; // ++x } void sub_one(int& x) { return ~-x; // --x }

整數變號

void negative(int& x) { return ~x + 1; // -x; } void negative(int& x) { return (x ^ -1) + 1; // -x; }

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

// 若回傳true則為偶數，false則為奇數 bool even_or_odd(int& x) { return x & 1; // x % 2; }

非負整數取模數，模數是二的倍數。

void mod(int& x, int& m) // m是二的倍數 { return x & (m - 1); // x % m; }

整數取絕對值

int abs(int& x) { // x < 0 ? -x : x; return (x ^ (x >> 31)) - (x >> 31); }

平方根倒數

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

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

// 1.0 / sqrt(x) float InvSqrt(float x) { float xhalf = 0.5f*x; int i = *(int*)&x; i = 0x5f3759df - (i>>1); x = *(float*)&i; x = x*(1.5f-xhalf*x*x); return x; }

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

void count_bits(int& x) { x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1); x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2); x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4); x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8); x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16); }

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

void reverse_bits(int& x) { x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa); x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc); x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0); x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00); x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000); }

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

原理是Binary Search。

void highest_bit_position(int x) { x--; x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x++; return x; }