Bit

Binary Number

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

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

Hexadecimal Number

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

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

Leading Digit / Trailing Digit

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

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

Bit

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

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

Byte

「位元組」。8位元。

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

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

Most Significant Bit / Least Significant Bit

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

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

Bitwise Operation

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。

Bitwise AND &

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

&將兩個變數的對應位元進行AND邏輯運算。

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

&可以判斷位元是不是1。例如統計有幾個位元是1。

Bitwise OR |

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

|將兩個變數的對應位元進行OR邏輯運算。

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

|可以把位元強制標記成1。例如把第五位元標成1。

Bitwise XOR ^

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

^將兩個變數對應的位元進行XOR邏輯運算。

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

^可以顛倒位元的0和1。例如顛倒第五位元。

Bitwise NOT ~

~ 0 = 1
~ 1 = 0

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

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

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

延伸閱讀:unsigned

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

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

signed變數,負值(最左位元為1),實施左移運算:
Undefined Behavior

signed變數,負值(最左位元為1),實施右移運算,最左位元應該補0還是補1:
Implementation-defined Behavior

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

Bitwise Function

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

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/

Bit Shift Multiplication(自然數乘法)

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

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

Bitset(自然數集合)

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

Number of 1 Bits(計算有幾個位元是1)

Bit Reversal(顛倒位元順序)

Least Significant 1 Bit(找到最低位的1)

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

XOR Swap(交換兩個int變數)

Missing Number Problem(檢查缺少的正整數)

陣列放入1到10的正整數,但是少了一個。找出少了哪一個。

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

Nim(捻)

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

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

UVa 10165

Josephus Problem(約瑟夫斯問題)

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

Letter Case Conversion(大小寫轉換)

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

8 Queen Problem(八皇后問題)

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

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

UVa 11195

Fast Inverse Square Root(平方根倒數)

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

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

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

Number資料結構: Two's Complement

楔子

計算學家利用位元運算,發明了整數的資料結構:二補數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

字串變二補數。我沒有研究。

print

二補數變字串。我沒有研究。

addition +

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

subtraction −

multiplication ×

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

演算法(Divide-and-Conquer Method)

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

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

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

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

演算法(Double-and-Add Algorithm)

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

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

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

division ÷

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

modulo mod

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

exponentiation ^

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

演算法(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。不能成功對半分的時候,事情變得很複雜。

UVa 374 1374 ICPC 3621

演算法(Multiply-and-Square Algorithm)

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

Number資料結構: Floating-point

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互除、負數開根號。

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

精確度

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

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

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

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

scan

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

print

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

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

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

用來加速分數運算。