# 2022q1 Homework2 (quiz2)
contributed by < [haoyu0970624763](https://github.com/haoyu0970624763) >

### 測驗1

避免overflow 的初始解法

uint32_t average(uint32_t low, uint32_t high)
{
    return low + (high - low) / 2;
}

缺點： 限制 input 的輸入 , low 的值必定要小於 high 才可以正常運行

改進解法一 : 使 input順序可以不受限制

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)

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 (組合語言的檔案) , 組合語言中的函式如下

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 (組合語言的檔案) , 組合語言中的函式如下

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 開始解讀

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

解析下面的程式

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 `

uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((a ^ b) & -(a < b));
}

上述的推導邏輯是從有號數取min值的想法類推而來

如果要適用於有號數應改成下列程式才更為正確

int32_t max(int32_t a, int32_t b)
{
    return a ^ ((a ^ b) & -(a < b));
}

不然在 一負數與一正數相比的情況 , 用無號數當資料型態會有問題。

例如: 輸入 -1 時 , bits　為 0xFFFFFFFF , 若用無號數的比大小 ,
會發生負數比正數大的情況

無號數取 max 值 就適用於下列程式

uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((a ^ b) & -(a < b));
}

### 測驗3

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;

**程式解析:**

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 , 可再直接化簡

下面即為更相減損法之實做

 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

法一：
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;

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 實做

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

 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 意思有一些接近

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

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

先從函數的原始版本開始解析：

#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 陣列的大小)

**優化版**

#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

#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;
}