Bit

Bit

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

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

Bitwise Operation

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。

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

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

& AND

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

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

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

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

| OR

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

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

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

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

^ XOR

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

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

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

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

~ 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

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變數

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

顛倒位元順序(僅適用32位元無號整數)

找到最低位數的1

檢查缺少的正整數

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

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

Letter Case Conversion(大小寫轉換)

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

8 Queen Problem(八皇后問題)

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

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

UVa 11195

Nim(捻)

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

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

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

Number資料結構: Two's Complement

楔子

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

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

print

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

addition +

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

subtraction −

multiplication ×

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

演算法(Divide and Conquer)

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)

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

UVa 374 1374 ICPC 3621

演算法(Multiply-and-Square Algorithm)

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

summation ∑

sequence production ∏

summorial k=1nk

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

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

factorial !

Number資料結構: Floating-point

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:非數。  例如:無限大與零互除、負數開根號。

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

精確度

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

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

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

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

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

用來加速分數運算。

factorial !(Stirling's Formula)

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

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

UVa 1185