Mathematics in Computer

阿貝爾群

代數系統

要介紹代數系統之前要先了解二元運算

二元運算

$\ast :A\times B\to C$為一個函數

$\mathrm{\forall }a\in A,\mathrm{\forall }b\in B$ 唯一存在

$c\in C$ 使得

$\ast (a,b)=c$, 則稱

$\ast$為二元運算(binary operation)

舉幾個例子

$S=Z,a\ast b=a+b$, 則

$\ast$為

$S$上的一個二元運算

$S=R,a\ast b=a/b$, 因為

$3\ast 0$無定義所以

$\ast$不是在

$S$上的二元運算

而代數系統的正式定義如下

$S\ne \mathrm{\varnothing }$, 則

$S$和數個

$S$上的二元運算就稱為代數系統

$(S,{\ast }_1,{\ast }_2,\cdots ,{\ast }_k)$

性質

代數系統上具有許多性質
以下介紹最常見的幾個

名稱	定義	備註
封閉性(closed)	$\mathrm{\forall }a,b\in S$滿足 $a\ast b\in S$
結合性(associative)	$\mathrm{\forall }a,b,c\in S,(a\ast b)\ast c=a\ast (b\ast c)$
交換性(commutative)	$\mathrm{\forall }a,b\in S,a\ast b=b\ast a$
單位元素(identity)	元素和單位元素做二元運算後依然等於自己	分為左單位元素與右單位元素(同時存在會相等)
反元素(inverse element)	元素和反元素做二元運算後等於單位元素	分為左右反元素(不一定相等)
反元素性質	$\mathrm{\forall }a\in S,a$的反元素存在
消去性	左消去性: $a\ast b=a\ast c\Rightarrow b=c$ , 右消去性: $b\ast a=c\ast a\Rightarrow b=c$

而群(group)又分為以下幾種

名稱	定義	備註
半群(semi group)	滿足封閉性, 結合性的代數系統
單群(monoid)	滿足封閉性, 結合性, 具有單位元素的代數系統	有單位元素的半群, 單位元素唯一
群(group)	滿足封閉性, 結合性, 具有單位元素, 反元素性質的代數系統	具有反元素性質的單群, 且必定具有消去性
交換群(abelian group)	滿足封閉性, 結合性, 交換性, 且具有單位元素, 反元素性質的代數系統	具有交換性的群

重要的有限群

定義

$Z_n=\{[0],[1],[2],\cdots ,[n-1]\}$ , 為n個等價類所成的集合
定義二元運算

${+}_n$ , 滿足

$\mathrm{\forall }[a],[b]\in Z_n,[a]{+}_n[b]=[a+b]=[r],r=(a+b)modn$

$(Z_n,{+}_n)$為一個代數系統且具有

• 良致性(well-defined)
• 封閉性
• 結合性
• 具有單位元素
• 具有反元素性質
• 交換性
• 為一個交換群

阿貝爾群的性質與細節

Abelian group

阿貝爾群就是一個代數系統並滿足以下特性

$(A,\cdot )$

• $a,b,c\in A,(a\cdot b)\cdot c=a\cdot (b\cdot c)$
• $\mathrm{\exists }e\in A,\mathrm{\forall }a\in A,e\cdot a=a\cdot e=a$ ,
  $e$ is called identity element
• $\mathrm{\forall }a\in A,\mathrm{\exists }b\in A,a\cdot b=b\cdot a=e$ , 反元素性質
• $\mathrm{\forall }a,b\in A,a\cdot b=b\cdot a$

經典阿貝爾群

• $(Z,+)$ , 0 is the identity element
  • $\mathrm{\forall }a,b,c\in Z,(a+b)+c=a+(b+c)$
  • $\mathrm{\forall }a\in Z,0+a=a+0=a$
  • $\mathrm{\forall }a\in Z,a+(-a)=(-a)+a=0$
  • $\mathrm{\forall }a,b\in Z,a+b=b+a$
• Integers modulo
  $n$
• real numbers under addition
• nonzero real numbers under multiplication

2's complement

首先要了解什麼是complement, 補數
在做減法的時候, 例如111 - 79, 這個看似單純的算式卻因為要做到借位而變複雜
如果考慮以下設計111 - 79 = 111 + (100 - 79) + (1 - 100)
利用兩個減法取代原本的算式從而避免借位的操作
(100 - 79) 可以稱為-79的nine's complement

過往我們學到什麼是2補數呢？就是把某個二進位表示法(binary string)的數字取1補數(每個位元反轉), 之後加上1
例如以4個bits表示的數字當中, 0010的二補數就是1101 + 0001 = 1110
並且可以觀察到任何數和自己的2補數相加之後都會得到10000, 變成5 bits, 因為溢位處理會是0000, 這難道是巧合？

這時候要考慮到阿貝爾群, 計算機這樣設計編碼是有意義的
因為群的特性的關係, 任何兩數做了binary operation之後依舊會在原本數的集合當中, 這可以避免溢位帶來的錯誤
並且不管怎麼設計, 0 (identity element)的表示法是唯一的

以8位元表示法為例, 0是00000000, 而1的表示法是00000001, 而1的反元素(-1)呢？
在阿貝爾群中的元素都滿足

$x+(-x)=e$, 我們知道(-1)存在並且唯一, 和(1)進行binary operation後會是identity element, 0
所以(-1)必然是11111111
但是如果從0開始不斷加1, 加了

$2^8-1$次後同樣也會得到11111111
那11111111到底是正數還負數?

此處不該以正數, 負數的觀點來思考電腦中的數字, 也就是他不是一個直線並且向兩側無限延伸的座標軸, 而是一個環形
(-x)並非負方向的x, 而是x的反元素

因此我們知道在阿貝爾群這樣的代數系統當中, 我們應當捨棄過往使用正數, 負數來看數字和符號的觀點, 從而用群的概念來思考數字

正負號只是端看電腦怎麼處理這些數字而已

以上討論的範圍還只涵蓋了整數還有加法形成的代數結構呢！
關於實數和乘法所形成的代數結構也有待探討

允許溢位的加減法和整數構成一個群
允許溢位的乘法構成一個環

處理器的指令集和數值編碼

注意到從以上阿貝爾群再推論到電腦設計編碼的方式可以知道

• 阿貝爾群讓我們操作數字的時候不再用傳統正負號的概念, 正負數的解讀完全交給電腦, 數值操作則因為阿貝爾群的性質, 根本不存在正負號的概念
• '溢位'的處理至關重要, 要是沒有溢位的處理就沒辦法使電腦當中運算真正成為一個環形的架構

看到這裡可能有人會想, 程式語言通常會區分signed, unsigned等不同資料型態, 那是否就要對正負號做額外處理？
實際上完全不需要, 因為電腦中的數字完全遵守阿貝爾群的定義, 因此不管你是用什麼正數負數丟進去, 對電腦來說他不會知道正數負數的概念, 他只會利用遵守阿貝爾群的二元運算來操作這些數字, 因此不需要區分指令集

然而這裡也牽涉到一個問題, 由於'溢位'的操作是把第i個bit後面的數字全部忽略, 這就牽涉到我們的電腦到底用幾個bits表示一個數字
然而現代電腦有8位元, 16位元,32甚至64位元表示法

每一種表示法就是一個阿貝爾群, 因為identity element 0 表示法不一樣
如果我們想要把資料搬遷到另一種表示法的環上, 例如8位元的1丟到16位元的1
則是把00000001, 左邊填充8個0即可
不過如果是1的反元素(-1)呢？在unsigned的情況, 一樣可以直接填充8個0
但若是signed的情況11111111丟到16位元的表示法依然應該要是(-1), 也就是1111111111111111, 這種情況就需要考慮符號

Bitwise operation

C bitwise operation

Operator	Function	Example
&	bitwise AND
|	bitwise OR
^	bitwise XOR
~	NOT
<<	bitwise left shift
>>	bitwise right shift

Practice

在開始了解bitwise實用的地方前
應該先完成以下練習以熟悉基本的bitwise算數

C Bitwise Operators
Practice with bit operations
Stanford Bitwise Practice

Characteristics

利用man ascii來觀察ascii code編碼
不需要硬背, 但需要瞭解規則

• lowercase letter和uppercase letter的關係是什麼?
  Ans: 每個uppercase letter都是由對應lowercase letter加上32所得到, 所以只要將lowercase letter編碼的bit 5給翻轉就行(0 + 1 = 1, 1 + 1 = 0 (溢位))
• Special number bit patter
  • -1 : 全為1 (-1和~1不同)
  • INT_MAX : msb為0, 剩下全為1
  • INT_MIN : msb為1, 剩下全為0
  • UINT_MAX : 全為1

bitvector
bitvector有以下幾種經典操作
通常要針對某個bit做操作, 要搭配bitmask
而bitmask的功能就是使得操作只對某個bit有效, 把剩下的bit給遮住
假設a, b是bitvector

• check a least significant bit : (a & 1)
• set lsb for a : (a | 1)
• set ith bit for a (counting from right most) : (a | (1 << i))
  任何bit和0做bitwise OR之後依然是自己, 所以和0做bitwise OR的bits等於是被遮住一樣, 只有右邊數來第i個bit和1做的bitwise OR有影響
• clear lsb for a : (a & ~1)
• clear ith bit for a (counting from right most) : (a & ~(1 << i))
  和1做bitwise AND等於是被遮住, 只有右邊數來第i個bit會和0做bitwise AND並得到有影響的操作
• toggle lsb in a : (a ^ 1)
• toggle ith bit in a : (a ^ (1 << i))
  和0做bitwise XOR等於是被遮住
• union a with b : a | b
• intersect a with b : a & b
• remove b from a : a & ~b

除了針對單一個bit做操作, 也可以對數個bit操作
只要掌握mask的技巧

• test if a has either of two lowest bits on : a & 0x3
• test if a has both of two lowest bits on : (a & 0x3) == 0x3
• set lowest 8 bits of a : a &= 0xff

Constant mask應該要用16進位來表示, 因為人很難直覺地將10進位數字轉為2進位, 但是16進位轉2進位只需要一瞥
並且與其每次都要hard-coding 一個神奇的數字
不如利用C語言的前處理器#define CONSTANT VALUE這樣的形式來定義mask

• all bits on : -1 or ~0
• one bit in position n, all others off : 1 << n
• n least significant bits on, all others off : (1 << n) - 1
• msb on, all others off : 1 << 32, MIN_INT
• k most significant bits on, all others off : ~(-1 >> k) , ~(~0U >> k)

Bitwise Manipulation
假設x, y都是32-bit有號數

• 1 << x : 2的x次方
• ~x + 1 : x的2補數, 也就是-x
• x >> 31 : x的正負號
• x &= (x-1) : clear lowest "on" bit in x (清除x當中最低位的1)
• (x ^ y) < 0 : 如果x, y不為同號數則為true