Bit
Bit
歡迎來到二進位的世界。電腦資料都是以二進位儲存,想當然程式語言的變數也都是以二進位儲存。一個位數是一個位元。一個變數通常有很多個位元。
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繪圖經常要計算平方根倒數。相傳是原作者在開發電腦遊戲「雷神之鎚」時,所發明的方法。
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
字串變整數。我沒有研究。
整數變字串。我沒有研究。
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()是浮點數版本而非整數版本。必須自己動手寫程式。
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
字串變浮點數。我沒有研究。
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