Bit

歡迎來到二進位的世界。電腦資料都是以二進位儲存，想當然程式語言的變數也都是以二進位儲存。一個位數是一個位元。一個變數通常有很多個位元。

https://hackmd.io/@sysprog/c-bitwise

Bitwise Operation

C/C++的位元運算子：<< SHIFT LEFT、>> SHIFT RIGHT、& AND、| OR、^ XOR、~ NOT，可以修改變數的位元。

UVa 10469 10264

<< SHIFT LEFT
>> SHIFT RIGHT

0001 << 1 = 0010
1000 >> 1 = 0100

這兩個運算子的功能主要是移動一個變數中的所有位元，位元向左/向右移動之後，最高位/最低位的位元會消失，最低位/最高位的位元補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。 */ int n = -5; n = n >> 1; // 不是 n = 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

延伸閱讀：unsigned

實施位元運算時，使用unsigned變數是最理想的。

unsigned變數與singed變數實施位元運算，其實沒有太大差異。唯一的差異之處，在於位移運算。

當signed變數為負值（最高位位元為1），實施左移運算：
Undefined Behavior

當signed變數為負值（最高位位元為1），實施右移運算，最高位補0還是補1：
Implementation-defined Behavior

當用到最高位元、也用到<<和>>的時候，必須改用unsigned int、unsigned long long int等變數型態，才會得到正確結果。

延伸閱讀：unsigned的陷阱

勿將unsigned與signed變數一起進行計算，非常容易出現意想不到的事情。例如拿unsigned與signed變數進行加減法、比大小；例如把unsigned變數傳入函數，但是函數參數卻是signed變數。

Bitwise Trick

各種怪招。例如滑鼠左鍵連點三下，再按右鍵選擇開啟連結。

http://www.aggregate.org/MAGIC/
http://graphics.stanford.edu/~seander/bithacks.html
https://github.com/keon/awesome-bits
https://www.geeksforgeeks.org/bit-tricks-competitive-programming/
https://www.geeksforgeeks.org/bitwise-hacks-for-competitive-programming/

gcc內建函式

http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

__builtin_clz        count leading 0. find leading 1. log2(n).
__builtin_ctz        count tailing 0. divide by 2^n.
__builtin_popcount   count bit 1.

交換兩個int變數

// 注意：比直接交換還要慢。 void swap(int& x, int& y) { x = x ^ y; y = x ^ y; x = x ^ y; } // 下面的寫法有暫存變數存取順序問題。 // Unspecified Behavior，不同的編譯器可能產生不同結果。 // 千萬不要如此取巧。 void swap(int& x, int& y) { x ^= y ^= x ^= y; }

計算有幾個位元是1（僅適用32位元無號整數）

// __builtin_popcount unsigned int count_bits(unsigned 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); return x; }

顛倒位元順序（僅適用32位元無號整數）

unsigned int reverse_bits(unsigned 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); return x; }

找到最低位數的1

int least_significant_bit_1(int x) { return x & -x; }

檢查缺少的正整數

陣列裡放入1到10的正整數，最後發現少了一個，請找出少了哪一個。

使用Counting Sort雖然時間複雜度低，但是空間複雜度高。

int array[9] = {2, 3, 5, 9, 4, 6, 10, 8, 1}; int find_lack_number() { int n = 0; // 1到10全部xor起來 for (int i=0; i<10; ++i) n ^= i; // 陣列裡的數字全部xor起來，與先前結果做xor。 for (int i=0; i<9; ++i) n ^= array[i]; return n; }

Letter Case Conversion（大小寫轉換）

大寫字母和小寫字母的ASCII數值，剛好只差一個位元。

int tolower(int c) { return (c >= 'A' && c <= 'Z') ? c ^ 32 : c; // return (c >= 'A' && c <= 'Z') ? c ^ (1<<5) : c; // return (c >= 'A' && c <= 'Z') ? c ^ ' ' : c; } int toupper(int c) { return (c >= 'a' && c <= 'z') ? c ^ 32 : c; }

8 Queen Problem（八皇后問題）

http://www.matrix67.com/blog/archives/266

使用回溯法。變數代替陣列，位元代替陣列元素。

const int N = 8; // 皇后數目 const int mask = (1 << N) - 1; // 弄出8個1 int ans = 0; // 合理的排列數目 void eight_queen() { backtrack(0, 0, 0); // 以橫線為單位遞迴 } // 皇后已占據的直線們、左斜線們、右斜線們。占據為1。 void backtrack(int col, int ld, int rd) { if (col == mask) {ans++; return;} // 找到一組解 int pos = mask & ~(col | ld | rd); // 可以放皇后的空位。空位為1。 while (pos /*!= 0*/) // 依序嘗試各個空位。 { int p = pos & -pos; // 最低位的1。一個可以放皇后的空位。 pos = pos - p; // 該空位消失，待會放皇后。 // 放上皇后，算好皇后占據的位置，然後遞迴至下一條橫線。 backtrack(col+p, (ld+p)<<1, (rd+p)>>1); } }

UVa 11195

Nim（捻）

這是兩個人玩的小遊戲。桌面上有N堆石子，兩個人輪流從桌上取走石子，每人每次只能取其中一堆石子，至少取一顆，至多搬走整堆。最後淨空桌面的人勝利，請判斷誰會勝利。

這個問題的解答，跟每堆石子的數量多寡有關。神奇的是，竟然跟二進位表示法有很大關連： http://oddest.nc.hcc.edu.tw/math152.htm。

int stone[10] = {2, 3, 4, 6, 6, 2, 3, 4, 8, 9}; void nim() { int x = 0; for (int i=0; i<10; ++i) x ^= stone[i]; if (x) cout << "先手贏"; else cout << "後手贏"; }

UVa 10165

Josephus Problem

模數為二的時候，答案為：去除n的最高位元，然後整體左移一位，最後加上一。

Fast Inverse Square Root（平方根倒數）

原理是牛頓法，避開了開根號和除法運算，節省了很多計算時間。除此之外還使用了很多神奇的技巧，包括電腦結構和程式語言的冷知識。

3D繪圖經常要計算平方根倒數。相傳是原作者在開發電腦遊戲「雷神之鎚」時，所發明的方法。

http://en.wikipedia.org/wiki/Fast_inverse_square_root

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; }

楔子

計算學家利用位元運算，發明了整數的資料結構：二補數Two's Complement、實數的資料結構：浮點數Floating-point。

這些資料結構暨演算法（加減乘除運算），已經製作成電路，放在中央處理器裡面。我們不必重新實作。我們直接在程式語言當中宣告變數、使用運算子即可。

注意到，由於數值精確度的緣故，這些資料結構並不符合數學家的定義！

Two's Complement

「二補數」。請參考維基百科：

http://en.wikipedia.org/wiki/Two's_complement

C與C++語言當中，可以直接使用char、short、int、long long建立整數資料結構，再以unsigned調整數值範圍。

切記，數值範圍有固定的上下限。如果超過上下限，稱做「溢位overflow」。依照C程式語言規格書，整數溢位是未定義行為，可能導致當機。

此處不介紹轉型規則、位元運算、型態大小、cstddef。這些不是演算法，大家自己查程式語言規格書吧。

scan

字串變整數。我沒有研究。

// atoi sscanf istringstream // scanf cin

print

整數變字串。我沒有研究。

// itoa sprintf ostringstream // printf cout

addition +

時間複雜度O(N)，其中N是數字的位數。

int add(int a, int b) { return a + b; }

subtraction −

int sub(int a, int b) { return a - b; }

multiplication ×

https://en.wikipedia.org/wiki/Multiplication_algorithm

int mul(int a, int b) { return a * b; }

演算法（Divide and Conquer）

a×b，其本質是a複製出b份，通通加起來。

如果b是偶數，將原問題分成兩個小問題：b/2份相加、b/2份相加（一模一樣，不必重算），兩者答案相加。

如果b是奇數，則分成三個小問題：b/2份、b/2份、1份，三者答案相加。

時間複雜度O(N²)，其中N是位數。

int mul(int a, int b) // a×b { if (b == 0) { return 0; } else if (b % 2 == 0) // 可以剛好對半 { int value = mul(a, b/2); return value + value; // 別寫成 return mul(a, b/2) + mul(a, b/2); // 這樣會多遞迴一次，比較慢。 } else /* if (b % 2 == 1) */ { int value = mul(a, b/2); return value + value + a; } }

演算法（Double-and-Add Algorithm）

b視作二進位，從低位數到高位數，分別計算每個位數與a的乘積，並且累加。

位數增加時，十進位數字變成十倍，二進位數字則是變成兩倍。b的位數逐漸增加，a隨著逐漸翻倍。

時間複雜度O(N²)，其中N是位數。

int mul(int a, int b) // a×b { int x = 0; for (; b > 0; b >>= 1) // b從低位數到高位數 { if (b & 1) x = x + a; // 累加乘積 a = a + a; // b位數增加，a隨著翻倍。 } return x; }

division ÷

http://en.wikipedia.org/wiki/Division_algorithm

int div(int a, int b) { return a / b; }

modulo mod

https://en.wikipedia.org/wiki/Barrett_reduction

int mod(int a, int b) { return a % b; }

exponentiation ^

C/C++沒有次方運算子。內建函式庫的pow()是浮點數版本而非整數版本。必須自己動手寫程式。

// b不能是負數 int pow(int a, int b) { int n = 1; for (int i=0; i<b; ++i) n *= a; return n; }

演算法（Divide and Conquer）

a的b次方。要解決這個問題，不外乎就是把a乘上b次，就能得到答案。然而更好的解決方案是Divide and Conquer。以7¹³來說好了，我們嘗試將它分成這樣：

7¹³ = 7⁷ × 7⁶
7⁶  = 7³ × 7³
7³  = 7² × 7¹

那麼我們只要知道7¹、7²、7³、7⁶、7⁷五個數字，就可以算出7¹³。以這種計算方式，不需要乘13次就可以得到答案了。

要怎麼求出7¹、7²、7³、7⁶、7⁷五個數字呢？這不是跟原問題很類似嗎？這都是求aᵇ呀！這樣我們就可以寫一個遞迴程式解決問題了！

一般來說，我們習慣採用對半分。不能對半的，也儘量對半。像是7⁶就分成7³ × 7³。7¹³則分成相差不多的7⁷ × 7⁶，而7⁷只要用7⁶乘個7就出來了。這種分法下，求出aᵇ的時間複雜度是O(logb)，以2為底的logb。

為什麼不三等分、四等分呢？當然也可以囉。不過，這些等分方法會讓乘的次數，比二等分來的要多。大家可以自行觀察。

順便介紹一個問題「Addition Chain Exponentiation」，找到最少的相乘次數，NP-complete。不能成功對半分的時候，事情變得很複雜。

// b不能是負數 int pow(int a, int b) // aᵇ { if (b == 0) return 1; // if (b == 1) return a; int x = pow(a, b/2); return b & 1 ? x * x * a : x * x; }

UVa 374 1374 ICPC 3621

演算法（Multiply-and-Square Algorithm）

仿照乘法的Double-and-Add Algorithm。

// b不能是負數 int pow(int a, int b) // aᵇ { int x = 1; for (; b; b >>= 1) { if (b & 1) x *= a; a *= a; } return x; }

summation ∑

int sum(int a[], int N) { int n = 0; for (int i=0; i<N; ++i) n += a[i]; return n; }

sequence production ∏

int mul(int a[], int N) { int n = 1; for (int i=0; i<N; ++i) n *= a[i]; return n; }

summorial ∑k=1nk

數學家稱作三角數。英文俗稱summorial，中文俗稱階加。

int sum(int n) { int a = 1; for (int i=1; i<=n; ++i) a += i; return a; }

階加已有許多經典公式，例如梯形公式：1+2+...+n = n(n-1)/2，例如正方形的L形分解：1+3+5+7+...+(2n-1) = n²。

int sum(int n) { // 上底加下底括號乘以高除以二 return (1 + n) * n / 2; }

factorial !

int fac(int n) { int a = 1; for (int i=1; i<=n; ++i) a *= i; return a; }

Floating-point

「浮點數」。已經有標準規格，請參考IEEE 754：

http://en.wikipedia.org/wiki/IEEE_floating_point

C與C++語言當中，可以直接使用float、double、long double建立浮點數資料結構。切記，數值範圍有固定的上下限。

特殊數字

浮點數溢位，依照IEEE 754規格書，將產生特殊數字，而且特殊數字仍然可以用於運算！

 INF：無限大。　例如：正數除以0、兩個超大的正數相加。
-INF：負無限大。例如：負數除以0、兩個超小的負數相加。
  -0：負零。　　例如：負數乘以0。
 NaN：非數。　　例如：無限大與零互除、負數開根號。

此處不介紹特殊數字的運算規則，請讀者自行上網查詢。

精確度

浮點數，位數有限。當位數過多，將剔除低位數。剔除的詳細過程，請大家自行研究規格書。

// C/C++的常數，若帶小數點、若是科學標記法，預設是double。 // 想要設定變數型態，在數字後面添加英文字母。 // float加f，double加l，long double加ll。大小寫都可以。 float f = 1234567890.5f; cout << fixed << f; // 1234567936.000000 // 32bit不夠存，剔除末位數。 double d = 1234567890.5; cout << fixed << d; // 1234567890.500000 // 64bit足夠存，精準無誤。

有些十進位小數，換成二進位之後，是循環小數。由於位數有限，剔除低位數，使得數值變動了。

float f = 0.3f; cout << f; // 0.3 // 暗中處理，看不出端倪。 cout << fixed << setprecision(50) << f; // 0.30000001192092895507812500000000000000000000000000 double d = 0.3; cout << fixed << setprecision(50) << d; // 0.29999999999999998889776975374843459576368331909180 cout << (f == 0.3f); // 等號兩邊都是0.30000001192...，結果為真。 cout << (f == d); // 首先f隱性轉型為double // 然後0.30000001192... > 0.299...，結果為非。 cout << (f == 0.3); // 首先f隱性轉型為double // 然後0.30000001192... > 0.299...，結果為非。

加減乘除運算，將預先比較兩數的數量級誰大誰小。如果數量級太懸殊，那麼數量級較低者，將剔除低位數，才進行計算。詳細計算過程，請自行研究規格書。

double a = 1e+100; double b = 1e-100; double c = a + b; cout << scientific << c; // 1.000000e+100

總而言之，浮點數的運算，要特別當心精確度問題。

scan

字串變浮點數。我沒有研究。

print

http://www.zhihu.com/question/22498967

浮點數變字串。主要有三個演算法：Dragon4、Grisu3、Ryū。龍系列，有興趣的讀者請自行研究。

cout << fixed << 1e+50; // 100000000000000007629769841091887003294964970946560.000000 cout << scientific << 1e+50; // 1.000000e+050 cout << fixed << 1e+38; // 99999999999999997748809823456034029568.000000 cout << scientific << 1e+38; // 1.000000e+038

division ÷

http://en.wikipedia.org/wiki/Division_algorithm

http://casdc.ee.ncku.edu.tw/class/CA/CH16.pdf

square root √‾

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

http://stackoverflow.com/questions/17410382/

summation ∑（Kahan Summation Algorithm）

http://en.wikipedia.org/wiki/Kahan_summation_algorithm

加總一連串大小差異很大的浮點數，盡量保持精確。

summation ∑（Binary Splitting）

http://en.wikipedia.org/wiki/Binary_splitting

用來加速分數運算。

factorial !（Stirling's Formula）

http://en.wikipedia.org/wiki/Stirling's_approximation

http://en.wikipedia.org/wiki/Gamma_function

UVa 1185