# 2022q1 Homework2 (quiz2)
contributed by < [haoyu0970624763](https://github.com/haoyu0970624763) >
### 測驗1
避免overflow 的初始解法
```c
uint32_t average(uint32_t low, uint32_t high)
{
return low + (high - low) / 2;
}
```
缺點： 限制 input 的輸入 , low 的值必定要小於 high 才可以正常運行
改進解法一 : 使 input順序可以不受限制
```c
uint32_t average(uint32_t a, uint32_t b) {
// input scan order doesn't limit
return (a >> 1) + (b >> 1) + (a & b & 0x01);
}
```
思路: 兩數相加取平均有3種 case
* 奇數+奇數
* 奇數+偶數（不考慮順序）
* 偶數+偶數
**case1:**
右移1位元會捨棄原本數字的 LSB , 若兩數都為奇數 , 則會捨棄 2 個 LSB , 造成結果少2 , 取平均答案則少1。
所以要把答案+1
例如: 3+5 取平均為 4 , 把兩數先右移1位是 1+2 結果為3 再加1
**case2:**
會捨棄一個 LSB , 不影響答案
**case3:**
兩數 >> 1 相加即為答案
所以 EXP1 可推得要處理兩數皆為奇數的情況 EXP1 => a&b&1
改進解法二:
參考 [你所不知道的 C 語言：數值系統篇 當中的 運用 bit-wise operator 部份](https://hackmd.io/@sysprog/c-numerics#%E9%81%8B%E7%94%A8-bit-wise-operator)
先用1位元加法器的概念下去想像 a+b
設 a 的 LSB=x , b 的 LSB=y
* x=0 , y=0 相加為 0
* x=0 , y=1 相加為 1
* x=1 , y=0 相加為 1
* x=1 , y=1 相加為 0 , 進位值=1
可看出一位元加法不考慮進位之結果為 x ^ y
推廣至 n bit來看 , 不考慮每一個位元間的進位值相加結果為`a^b`
一位元進位結果是 (x&y) << 1 , 推廣至 n 位則是 (a&b) << 1
所以 a + b = a ^ b + ( a & b ) << 1
(a+b) / 2 = ((a ^ b) >> 1) + (a & b)
```c
uint32_t average2(uint32_t a, uint32_t b) {
// input scan order doesn't limit
return (a & b ) + ((a ^ b) >> 1);
}
```
將第一個寫出來的 code 開啟最佳化進行編譯
使用 `gcc -O3 -S average.c` 指令
會生成 average.s (組合語言的檔案) , 組合語言中的函式如下
```clike
average:
.LFB39:
.cfi_startproc
endbr64
movl %edi, %eax
movl %esi, %edx
andl %esi, %edi
shrl %eax
shrl %edx
andl $1, %edi
addl %edx, %eax
addl %edi, %eax
ret
.cfi_endproc
```
上面為 (a >> 1) + (b >> 1) + (a & b & 0x01) 的組合語言
使用 `gcc -O3 -S average2.c` 指令
會生成 average2.s (組合語言的檔案) , 組合語言中的函式如下
```clike
average2:
.LFB39:
.cfi_startproc
endbr64
movl %edi, %eax
andl %esi, %edi
xorl %esi, %eax
shrl %eax
addl %edi, %eax
ret
.cfi_endproc
```
上面為 (a & b) + ((a ^ b) >> 1) 的組合語言
:::info
暫時還看不懂 之後研讀
:::
### 測驗2
先從 <[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉一文的「不需要分支的設計」一節提供的程式碼 min 開始解讀
```c
int32_t min(int32_t a, int32_t b) {
int32_t diff = (a - b);
return b + (diff & (diff >> 31));
}
```
倘若輸入數值的資料型態是 32 位元有號整數時，向右位移採用算數位移
此題只會有 2 種情況
* a - b >= 0 , MSB=0 且 a 是較大的值 , diff >> 31 = 0
所以 b + (diff & (diff >> 31)) => b + (diff&0) => b
* a - b < 0 , MSB = 1 且 b 是較大的值 , diff >> 31 = -1 (bit 全為1) 所以 , b + (diff & (diff >> 31)) => b+(diff & 0xFFFFFFFF)
=> b+diff => b+(a-b) => a
解析下面的程式
```c
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
跟上面那題同個邏輯 , 此題會有兩種 case
* a - b >= 0 也就是 a >= b
當 a ^ ((EXP4) & -(EXP5)) 為 a ^ ((EXP4) & -(0)) 時
=> a ^ 0 = a
由此判斷 EXP5 為使 a >= b 為 非的敘述
所以 `EXP5是 a < b`
* a - b < 0 也就是 a < b
把上面判斷的EXP5 納入考量 , 則
a ^ ((EXP4) & -(a<b)) 為 a ^ ((EXP4) & -1)
=> a ^ ((EXP4) & 0xFFFFFFFF ) => a ^ (EXP4)
a ^ (EXP4) 要使答案為 b 所以 `EXP4 為 a ^ b `
```c
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
上述的推導邏輯是從有號數取min值的想法類推而來
如果要適用於有號數應改成下列程式才更為正確
```c
int32_t max(int32_t a, int32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
不然在 一負數與一正數相比的情況 , 用無號數當資料型態會有問題。
例如: 輸入 -1 時 , bits 為 0xFFFFFFFF , 若用無號數的比大小 ,
會發生負數比正數大的情況
無號數取 max 值 就適用於下列程式
```c
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
### 測驗3
```c
uint64_t gcd64(uint64_t u, uint64_t v) {
/* if u or v equal zero , then return the number which is not equal to zero
*/
if (!u || !v)
return u | v;
/* shift is used to record common factor of 2^k */
int shift;
/* if u or v is odd number , then out of the loop*/
for (shift = 0; !((u | v) & 1); shift++) {
u >>= 1, v >>= 1;
}
// 更相減損法
while (!(u & 1))
u >>= 1;
do {
while (!(v & 1))
v >>= 1;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
```
**程式解析:**
```c
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
在 2 進位表示法中可以簡單快速的判斷兩數字是否可被 $2^k$ 整除，所以可以先把 $2^k$ 的公因數提出來再做輾轉相除法。
用`shift`變數紀錄 k 為多少，之後再把算出來之結果乘回原先提出的公因數
透過類似於輾轉相除法的求 GCD 方法：**更相減損法**
主要分成 3 種 case , 且因為我們先把 2 的公因數提出 , 所以不會有皆為偶數的情況
* x 為偶數，y 為奇數
$gcd(x, y) = gcd(x/2, y)$
* x 為奇數，y 為偶數
$gcd(x, y) = gcd(x, y/2)$
* x 為奇數，y 為奇數
$gcd(x, y) = gcd(x - y, y)=gcd((x - y)/2), y)$
因為 x-y 必為偶(2奇數相減) , 回到 case1 , 可再直接化簡
下面即為更相減損法之實做
```c
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
```
最後答案再回傳 $u*2^k$ 也就是 $u << shift$
leetCode相關題 [Water and Jug Problem](https://leetcode.com/problems/water-and-jug-problem/)
使用 `__builtin_ctz` 改寫 gcd
運用到 **測驗2** 同樣邏輯的 min
先找出 2 數分別 right most zero 個數
在 rightmost zero 個數數量很多時 , 法二的效率較好
因為法一的 loop 數要跑很多次
並且法二的實做方法是 deterministic
```c
法一：
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
等價於
法二：
int shift_u = __builtin_ctz(u);
int shift_v = __builtin_ctz(v);
int shift = min(shift_u, shift_v);
u >> shift;
v >> shift;
```
```c
uint64_t min(int64_t a, int64_t b) { return a ^ ((a ^ b) & -(a >= b)); }
uint64_t gcd64(uint64_t u, uint64_t v) {
/* if u or v equal zero , then return the number which is not equal to zero
*/
if (!u || !v)
return u | v;
/*
__builtin_ctz is used to count the rightmost zero number
shift is used to record common factor of 2^k which means the smaller __builtin_ctz
*/
int shift_u = __builtin_ctz(u);
int shift_v = __builtin_ctz(v);
int shift = min(shift_u, shift_v);
u >> shift;
v >> shift;
// 更相減損法
if (!(u & 1))
u >>= __builtin_ctz(u);
do {
if (!(v & 1))
v >>= __builtin_ctz(v);
if (u < v) {
v -= u;
} else {
uint32_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
#### Linux kernel 中的 gcd 實做
```c
unsigned long gcd(unsigned long u, unsigned long v) {
unsigned long r = u | v;
/* if a = 0 or b = 0 , then return a | b
* which means return the number is not zero
*/
if (!u || !v)
return r;
v >>= __ffs(v);
if (v == 1)
return r & -r;
for (;;) {
/*check whether u is the form of 2^k
* if so , just return r & -r , like the code above it*/
u >>= __ffs(u);
if (u == 1)
return r & -r;
/* 如果提出 2的冪次方之後的 u 等於 提出 2的冪次方之後的 v
* 則表示他們的最大公因數為
* 提出之後的結果 乘上 兩數分別提出的冪次方中較小的2的冪次方
* 即 v << __ffs(r) 要寫成 u << __ffs(r) 也行
* */
if (u == v)
return v << __ffs(r);
/* 確保 u >= v , 使 u-=b 成立
* 且運用 gcd(x, y) = gcd(x - y, y)
* */
if (u < v)
swap(u, v);
u -= v;
}
}
```
**要先知道 __ffs(b) 等價於 __builtin_ctz(b)**
**r & -r** 解析 :
簡單假設 r 的 bit 形式為 00010010 ,
那麼 -r 就是 11101101再加1(取 not 再+1) 所以是 11101110
00010010 & 11101110 為 00000010 也就是取出最低位非0 的數字
r 又等於 a | b , 所以 r & -r 表示 取出 a | b 最低位非 0 的數
```c
int shift_u = __builtin_ctz(u);
int shift_v = __builtin_ctz(v);
int shift = min(shift_u, shift_v);
u >> shift;
v >> shift;
```
上面這段程式跟下面這段 linux kernel 意思有一些接近
```c
v >>= __ffs(v);
if (v == 1)
return r & -r;
```
如果用上面的 code 去理解 linux kernel 中的 code
可理解成我們先算出 v 的 rightmost zero number , 然後直接假設他是 u 跟 v 當中較小的 __ffs 並進行 shift
也就是先提出 $2^k$ 的概念
如果提出 $2^k$ , v 等於 1 的話 代表 v 的值就是 $2^k$
若 v 等於 $2^k$ , 也就是 bits 的形式 有唯一一個bit等於１
這時候 u 跟 v 的分佈會有以下情況
* u 比 v 小的情況
* u 為偶數 , 此時 u 跟 v 的最大公因數即取出 u | v 中 非0 的最低位數字的 bit 形式。
例如： v = 32 = $2^5$ = u = 6 , 則 u | v = 00100110
取出 u | v 中 非0 的最低位數字的 bit 形式為 00000010
最大公因數為 2
* u 為奇數 , 此時最大公因數必為 1 , 取出 u | v 中 非0 的最低位數字的 bit 形式 也會是 1
* u 比 v 大的情況
* u 為 偶數 , 此時 u 跟 v 的最大公因數即取出 u | v 中 非0 的最低位數字的 bit 形式。
例如： v = 32 = $2^5$ = u = 68 , 則 u | v = 01100100
取出 u | v 中 非0 的最低位數字的 bit 形式為 00000100
最大公因數為 4
* u 為奇數 , 此時最大公因數必為 1 , 取出 u | v 中 非0 的最低位數字的 bit 形式 也會是 1
我們可以發現 若 v 為 $2^k$ 的形式 , 不論 u 的值為多少
最大公因數皆為 `r & -r`
若 v 不為 $2^k$ 的形式 , 則繼續底下的 code
```c
for (;;) {
/*check whether u is the form of 2^k
* if so , just return r & -r , like the code above it*/
u >>= __ffs(u);
if (u == 1)
return r & -r;
/* 如果提出 2的冪次方之後的 u 等於 提出 2的冪次方之後的 v
* 則表示他們的最大公因數為
* 提出之後的結果 乘上 兩數分別提出的冪次方中較小的2的冪次方
* 即 v << __ffs(r) 要寫成 u << __ffs(r) 也行
* */
if (u == v)
return v << __ffs(r);
/* 確保 u >= v , 使 u-=b 成立
* 且運用 gcd(x, y) = gcd(x - y, y)
* */
if (u < v)
swap(u, v);
u -= v;
}
```
### 測驗4
先從函數的原始版本開始解析：
```c
#include <stddef.h>
#include <stdint.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out) {
size_t pos = 0;
for (size_t k = 0; k < bitmapsize; ++k) {
/* bitset 的 value等於原始陣列的第 k 個元素的 value
* p 用來紀錄原始陣列的第 k 個元素 對應到 out 陣列的初始位置
*/
uint64_t bitset = bitmap[k];
size_t p = k * 64;
/* 檢查原始陣列的第 k 個元素的 bit 形式(64位元)
* 紀錄 第 k 個元素的 bit 形式當中 總共有幾個 bit 為 1
* pos 用來紀錄 bitmap 的每一個數值的二進位形式中 1 的總數量
* 將 out 陣列的值 透過函數的轉換即可知道當初在原始陣列中的值的哪個 bit 為
* 1
* */
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}
}
return pos;
}
```
本函數的目標是: 紀錄 bitmap 數值的2進位形式 為 1 的位元編號於 out 陣列 並回傳 bit 為 1 的總數量 (也就是 out 陣列的大小)
**優化版**
```c
#include <stddef.h>
#include <stdint.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
uint64_t bitset;
for (size_t k = 0; k < bitmapsize; ++k) {
bitset = bitmap[k];
while (bitset != 0) {
uint64_t t = bitset & -bitset;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
改寫前的程式碼中是對於 bitmap 中的每一個值的每一個 bit (64位元) 所以一個值要跑 64 次的 loop
然而其實不用針對每一個 bit 都去跑一次 loop
改寫後的版本是透過 `t = bitset & -bitset`
把 bitset 中 rightmost 的 1 保存起來 , 在測驗三當中已經說明過了
透過`r = __builtin_ctzll(bitset)` 去看是在 64位元中的哪個位置
並將其紀錄在 out 陣列
最後對 bitset 做 XOR 會把 剛剛保存的 `1` 變成 `0` ,其餘的部份則會複製原本的 bitset
這樣可以減少迴圈跑的次數。
**此 code 為 漢明權重(又稱漢明重量)** , 跟 bit 全為 0 之間的 漢明距離 , 在密碼學當中有廣泛的運用
### 測驗5
```c
#include "list.h"
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct rem_node {
int key;
int index;
struct list_head link;
};
static int find(struct list_head *heads, int size, int key) {
struct rem_node *node;
int hash = key % size;
list_for_each_entry(node, &heads[hash], link) {
if (key == node->key)
return node->index;
}
return -1;
}
char *fractionToDecimal(int numerator, int denominator) {
int size = 1024;
char *result = malloc(size);
char *p = result;
// 如果分母等於 0 , 則字串馬上接終止符號
if (denominator == 0) {
result[0] = '\0';
return result;
}
// 如果分子等於 0 , 字串為0 然後馬上接終止符號
if (numerator == 0) {
result[0] = '0';
result[1] = '\0';
return result;
}
/* using long long type make sure there has no integer overflow */
long long n = numerator;
long long d = denominator;
/* deal with negtive cases */
if (n < 0)
n = -n;
if (d < 0)
d = -d;
bool sign = (float)numerator / denominator >= 0;
// set negative sign
if (!sign)
*p++ = '-';
long long remainder = n % d;
long long division = n / d;
/* 原本是 sprintf(p, "%ld", division > 0 ? (long)division : (long)-division);
* 但因為 n 跟 d 我們在上面處理過了有負號的情況
* 所以這邊不需要再判斷正負號
* */
sprintf(p, "%ld", (long)division );
if (remainder == 0)
return result;
p = result + strlen(result);
*p++ = '.';
/* Using a map to record all of reminders and their position.
* if the reminder appeared before, which means the repeated loop begin,
*/
char *decimal = malloc(size);
memset(decimal, 0, size);
char *q = decimal;
size = 1333;
struct list_head *heads = malloc(size * sizeof(*heads));
for (int i = 0; i < size; i++)
INIT_LIST_HEAD(&heads[i]);
for (int i = 0; remainder; i++) {
int pos = find(heads, size, remainder);
if (pos >= 0) {
while (pos-- > 0)
*p++ = *decimal++;
*p++ = '(';
while (*decimal != '\0')
*p++ = *decimal++;
*p++ = ')';
*p = '\0';
return result;
}
struct rem_node *node = malloc(sizeof(*node));
node->key = remainder;
node->index = i;
list_add(&node->link, &heads[remainder % size]);
*q++ = (remainder * 10) / d + '0';
remainder = (remainder * 10) % d;
}
strcpy(p, decimal);
return result;
}
```
Sign in with Wallet
Connect another wallet