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>,可以統計與修改變數的位元。

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編譯器內建函式,可以統計與修改變數的位元。

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

bitwise trick

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(自然數乘法)

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

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

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(八皇后問題)

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

UVa 11195

fast inverse square root(平方根倒數)

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

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

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

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 ×

演算法(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 ÷

modulo mod

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:

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

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

特殊數字

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

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

精確度

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

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

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

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

scan

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

print

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

division ÷

square root √‾

summation ∑(Kahan summation algorithm)

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

summation ∑(binary splitting)

用來加速分數運算。

利用浮點數進行數學函數運算

我沒有研究。我甚至不知道這個領域如何稱呼。