# 2020q3 Homework2 (quiz2)
{%hackmd QnyEFBdERZebn4iQDXNPnA %}
contributed by < `jeff14994` >
###### tags: `sysprog2020` `2020` `quiz` `hw2` `week2`
## 測驗1 - 判斷指定的記憶體範圍內是否全是有效的 ASCII 字元
### 題目
目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。如果我們明確界定 7 位元編碼的字元隸屬於 ASCII，可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元:

#include <stddef.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    for (int i = 0; i < size; i++)
        if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */
            return false;
    return true;
}

其中 str 是開頭的記憶體地址，size 則是要檢驗的範圍。逐一字元比對的效率低，在 64 位元的架構下，我們嘗試一次比對 64 位元的資料 (即 word size)，程式碼改寫如下:

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    int i = 0;
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & MMM)
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

==請補完程式碼。==

==MMM = ?==

(a) 0x0080008000800080
(b) 0x8000800080008000
\(c\) 0x0808080808080808
(d) 0x8080808080808080
(e) 0x8888888888888888
答案是(d) MMM = 0x8080808080808080

### 回答
透過 Mac 內建計算機可得：
8個位元組的最高位皆為1，所代表含義即為判斷是否隸屬 ASCII 的範圍。題目程式碼第13行即代表，一次從字串取8個8位元組(byte)，判斷這8個位元組是否為ASCII，若否 return false。而第17行所代表的含義為，若字串不是8的倍數，則一次取一個byte進行檢驗是否為 ASCII。

## 測驗2 - 16 進位轉換成數值
### 題目
給定的程式碼：

uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & MASK;
    const uint8_t shift = (letter >> AAA) | (letter >> BBB);
    return (in + shift) & 0xf;
}

>前提：已知 in 一定隸屬於 '0', '1', '2', …, '9' 及 'a', 'b', 'c', …, 'f' (小寫) 及 'A', 'B', 'C', …, 'F' (大寫) 這些字元。預期 hexchar2val('F') 和 hexchar2val('f') 回傳 15，且 hexchar2val('0') 回傳 0，其他輸入都有對應的數值。

### 回答
看完程式碼後，沒有頭緒。不過看到選項是有限的(MASK 的選項5個，AAA 的選項4個，BBB 的選項4個)，我預估測80(5\*4\*4)次的運算應該就會有結果，因此嘗試使用暴力法去預測選項，因此寫了以下的程式碼去運算(使用三個迴圈帶入選項)：

#include <stdint.h>
#include <stdio.h>
uint8_t hexchar2val(uint8_t in, int ans) 
{
  unsigned char MASK[] = {0x10, 0x20, 0x40, 0x60, 0x80};
  int AAA[] = {3, 2, 1, 0};
  int BBB[] = {7, 6, 5, 4};
  for (int i = 0; i < sizeof(MASK); i++) {
    for (int j = 0; j < sizeof(AAA); j++) {
      for (int k = 0; k < sizeof(BBB); k++) {
        const uint8_t letter = in & MASK[i];
        const uint8_t shift = (letter >> AAA[j]) | (letter >> BBB[k]);
        if (((in + shift) & 0xf) == ans) {
          printf("0x%x\n", MASK[i]);
          printf("%d\n", AAA[j]);
          printf("%d\n", BBB[k]);
        }
      }
    }
  }
}

void main() {
  char input1 = 'f';
  int input1_ans = 15;
  char input3 = 'F';
  int input3_ans = 15;
  printf("[+] Processing... Please wait\n");
  hexchar2val(input3, input3_ans);
  printf("==================\n");
  hexchar2val(input1, input1_ans);
};

得到的結果如下。接著，取完交集後，發現答案的確是 MASK = 0x40, AAA = 3, BBB = 6。不過實驗完的結果跟我的預期不大相同，我以為只有滿足條件只有唯一解，沒想到居然得到多重解。

[+] Processing... Please wait
0x40
3
6
0x60
3
6
==================
0x20
2
5
0x40
3
6
0x60
2
6

接著，我嘗試揣測並逐項驗證給定的程式碼。
首先，由給定的程式碼第5行開始回推，(in + shift) & 0xf 。若 in 代入 "F" 或 "f"，其回傳結果皆為15(10進位)。若將15(10進位)，化作2進位，可得0000 1111，根據題意。其與 0xf 做 AND 運算應得0000 1111，而 0xf 化作2進位可得0000 1111，換句話說，可推得(in + shift)至少為0000 1111 (因為若(in + shift) 等於 0000 1111 與 0xf 做 AND 運算可得0000 1111，也就是15(10進位))。

接著，推論 MASK是什麼？此時，根據 [ASCII Code：](https://zh.wikipedia.org/zh-tw/ASCII)
可得知 "F" 其 16 進位為 0x46，而 "f"，其 16 進位為 0x66。化作二進位分別可得，"F" 為0100 0110 ，"f" 為0110 0110。不難發現，其共通點在前半段的0100，MASK 即為 0100 0000，化作16進位為 0x40，因為如此能取得 "F" 與 "f"的共通部分。

接著，推論 AAA 與 BBB 是什麼？在這之前，根據給定的程式碼第4行發現，是 letter 向右位元位移並做 OR 運算，而 letter 來自 in 與 MASK 做 AND 運算。因此，若 in 使用 "f" 帶入的話，可得 letter 為 0100 0000(因為 0110 0110 & 0100 0000 = 0100 0000)。透過上述描述，已知 in 與 shift，便可推得 AAA 與 BBB。推論如下，因為已知 in + shift 必為0000 1111，而現在 in 為 0110 0110 ，可推得 shift 至少必為0000 1001(如此 (in + shift) & 0xf 才有可能為15(2進位為000 1111 ))，而1001 即 0100 0000 >> 3 與 0100 0000 >> 6 做 OR 運算的結果。因此，可推得 AAA 為3，BBB 為6，或相反。根據選項，AAA 最大只到3因此選3， BBB 選6。
[參考資料](http://www2.mta.ac.il/~hbinsky/c%20content/Bits.pdf)
>延伸問題:
>>1. 解釋上述程式的運作原理;
>> 2. 將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值
Hexspeak

## 測驗3
## 測驗4

## 測驗5
## 測驗6
### 題目
>LeetCode 137. Single Number II:

>>Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2]
Output: 3
Example 2:
Input: [0,1,0,1,0,1,99]
Output: 99

考慮以下程式碼為 LeetCode 137. Single Number II 的題解:

int singleNumber(int *nums, int numsSize)
{
    int lower = 0, higher = 0;
    for (int i = 0; i < numsSize; i++) {
        lower ^= nums[i];
        lower &= KKK;
        higher ^= nums[i];
        higher &= JJJ;
    }
    return lower;
} 

==請補完程式碼。==

作答區

==KKK = ?==
KKK = (c\) 選項

(a) higher
(b) lower
\(c\) ~higher
(d) ~lower
(e) 0xFFFFFFFF
==JJJ = ?==
JJJ = (d)選項

(a) higher
(b) lower
(c\) ~higher
(d) ~lower
>延伸問題:
>>1. 解釋上述程式的原理;
>>2. 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時;
>>3. 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼;
### 回答