Binary Number

「二進位數字」。底數是2的數字。使用2個符號01。

C++程式語言，0b字首可以建立二進位數字。C程式語言，不支援0b字首。

int n = 0b1010111100011100; // 44828

Hexadecimal Number

「十六進位數字」。底數是16的數字。使用16個符號0123456789abcdef，大小寫視為相同。

C/C++程式語言，0x字首可以建立十六進位數字。二進位太過冗長瑣碎，十六進位比較常見。

int n = 0xaf1c; // 44828

Leading Digit / Trailing Digit

「最高位數」與「最低位數」。數字的最左位數與最右位數。

例如0b1010111100011100，最高位數是1，最低位數是0。

Bit

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

例如C/C++程式語言當中，char變數型態是8位元，short變數型態是16位元，int變數型態是32位元、long long變數型態是64位元。

int n = 0b1010111100011100; // 儲存為00000000000000001010111100011100，總共32位元。

Byte

「位元組」。8位元。

byte與bite諧音，bite意思是咬一口。早期的中央處理器一次讀入8位元，咬一口是8位元。另一方面，8位元剛好是兩個十六進位符號，簡潔方便。就這樣定下來了。

也因此程式語言的變數型態，以byte做為基本單位，位元數量均是8的倍數。例如C/C++程式語言當中，char變數型態是1位元組，short變數型態是2位元組，int變數型態是4位元組、long long變數型態是8位元組。

cout << sizeof(int); // 得到4

Most Significant Bit / Least Significant Bit

「最高有效位元」與「最低有效位元」。程式語言的變數型態的最左位元與最右位元。大家習慣縮寫成MSB與LSB。

例如int變數型態，00000000000000001010111100011100，最左位元是0，最右位元是0。

Bitwise Operation

C/C++的位元運算子：<<、>>、&、|、^、~，可以修改變數的位元。

UVa 10469 10264

Bitwise Left Shift <<
Bitwise Right Shift >>

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

<<和>>將一個變數的所有位元向左/向右移動。最左位元/最右位元消失，最右位元/最左位元補0。

   00000000000000000000000001110100   -> 116
<<                                1
-----------------------------------
   00000000000000000000000011101000   -> 232

   00000000000000000000000001110100   -> 116
>>                                2
-----------------------------------
   00000000000000000000000000011101   -> 29

<<和>>可以把位元挪到特定位置。例如讓第五位元是1。

int n = 1 << 4; // 00000000000000000000000000010000

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

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

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

Bitwise NOT ~

~ 0 = 1
~ 1 = 0

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

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

&和~可以把位元強制標記成0。例如把第五位元標成0。

int clear_5th_bit(int n) { return n & ~(1 << 4); }

延伸閱讀：unsigned

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

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

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

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

用到最左位元、也用到<<和>>的時候，必須改用unsigned變數，才會得到正確結果。

Bitwise Function

C++的內建函式庫<bit>，可以統計與修改變數的位元。

https://en.cppreference.com/w/cpp/header/bit

rotl             cicular left rotation
rotr             cicular right rotation
bit_width        find position of leading 1
bit_floor        get leading 1 / (int)log2(n)
bit_ceil         -1, bit_floor, <<1
countl_zero      count leading 0s
countl_one       count leading 1s
countr_zero      count trailing 0s
countr_one       count trailing 1s
popcount         count bit 1
has_single_bit   only one bit 1 / is_power_of_2(n)

gcc編譯器內建函式，可以統計與修改變數的位元。

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

__builtin_clz        count leading 0s
__builtin_ctz        count trailing 0s
__builtin_popcount   count bit 1

Bitwise Trick

專著《Hacker's Delight》。

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

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/

Bit Shift Multiplication（自然數乘法）

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

因為左移右移運算快於乘法除法運算，所以很多程式設計師以左移右移運算取代乘法除法運算。優點是程式執行速度上升，缺點是程式碼可讀性下降。

int n = 5; n = n << 1; // 即是 n = n * 2; n >>= 1; // 即是 n /= 2; int n = -5; n = n >> 1; // 負數的情況下，不是 n = n / 2。

Bitset（自然數集合）

一個int變數當作一個集合，一個位元當作一個元素。

void add(int& bitset, int element) { bitset |= (1 << element); } void remove(int& bitset, int element) { bitset &= ~(1 << element); }

Number of 1 Bits（計算有幾個位元是1）

// __builtin_popcount // 僅適用32位元無號數 unsigned int count_1_bit(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; }

Bit Reversal（顛倒位元順序）

// 僅適用32位元無號數 unsigned int bit_reverse(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; }

Least Significant 1 Bit（找到最低位的1）

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

Power of 2 Test（判斷一個正整數是否為2的次方）

bool is_power_of_2(int x) { return !(x & (x-1)); // x & (x-1)消去最低位的1 }

XOR Swap（交換兩個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; }

Missing Number Problem（檢查缺少的正整數）

陣列放入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; }

Nim（捻）

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

這個問題的解答，跟每堆石子的數量多寡有關。神奇的是，竟然跟二進位表示法有很大關連。

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的最高位數，然後整體左移一位，最後加上一。

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

Fast Inverse Square Root（平方根倒數）

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

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。

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

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

Unsigned Number

「無號數」。普通的二進位整數，沒有正負號，於是沒有負數。簡單來說就是「非負整數」。

C/C++程式語言當中，可以直接使用unsigned char、unsigned short、unsigned int、unsigned long long建立無號數。

例如unsigned int變數型態是32 bit，可以儲存數值範圍為0到2³² - 1的整數，大約是4後面再接九個零。unsigned long long變數型態是64 bit，可以儲存數值範圍為0到2⁶⁴ - 1的整數。

切記，數值範圍有固定的上下限。如果超過上下限，稱作「溢位overflow」。依照C/C++程式語言規格書，無號數溢位，等同取模數。超過上限時，捨去高位數，保留低位數。低於下限時，從最大值開始減少，頭尾循環。

雖然unsigned int、unsigned long long的數值大小已經夠用了，但是人的慾望是無止盡的，總是想讓電腦能夠處理更大的數字、算得更精準。這種時候就得使用大數了。

Two's Complement

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

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

C/C++程式語言當中，可以直接使用char、short、int、long long建立二補數。

二補數挪用了最左位元作為正負號，可以儲存負整數。例如int變數型態是32 bit，可以儲存數值範圍為-2³¹到2³¹ - 1的整數，大約是2後面再接九個零。long long變數型態是64 bit，可以儲存數值範圍為-2⁶³到2⁶³ - 1的整數。

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

延伸閱讀：Implicit Conversion導致的陷阱

C/C++程式語言當中，無號數與二補數一起進行計算，背後機制相當複雜，非常容易出現意想不到的事情。若非必要，別這麼做。

例如加減法、比大小。例如函數參數是二補數，但是呼叫函數時卻傳入無號數。

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 Method）

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

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

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

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

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

演算法（Double-and-Add Algorithm）

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

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

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

unsigned int mul(unsigned int a, unsigned int b) { unsigned 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()是浮點數版本而非二補數版本。必須自己動手寫程式。

unsigned int pow(unsigned int a, unsigned int b) { unsigned int n = 1; for (unsigned int i=0; i<b; ++i) n *= a; return n; }

演算法（Divide-and-Conquer Method）

a的b次方。要解決這個問題，不外乎就是把a乘上b次，就能得到答案。然而更好的解決方案是Divide-and-Conquer Method。以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。不能成功對半分的時候，事情變得很複雜。

unsigned int pow(unsigned int a, unsigned int b) { if (b == 0) return 1; // if (b == 1) return a; unsigned 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。

unsigned int pow(unsigned int a, unsigned int b) { unsigned int x = 1; for (; b; b >>= 1) { if (b & 1) x *= a; a *= a; } return x; }

Floating-point

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

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

C/C++程式語言當中，可以直接使用float、double、long double建立浮點數。

切記，數值範圍有固定的上下限。如果超過上下限，稱作「溢位overflow」。依照IEEE 754規格書，浮點數溢位將產生特殊數字，而且特殊數字仍然可以用於運算！不會當機！

特殊數字

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

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

精確度

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

// 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

用來加速分數運算。