2020q3 Homework2 (quiz2)

contributed by < quantabase13 >

Table of Contents

• 2020q3 Homework2 (quiz2)
• Table of Contents
  • 程式運作原理
    • 測驗 1
    • 測驗 2
    • 測驗 3
    • 測驗 4
    • 測驗 5
    • 測驗 6

---

程式運作原理

測驗 1

#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 & 0x8080808080808080/*MMM*/)
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

• ASCII code 共有128個字元，以7位 bit 進行編碼 ; 另外， char 類的大小為8個 bits。所以若要確定一個 char 是否為 ASCII code ，只要確認其最高位是否為1即可。
• is_ascii 的 while loop 裡聲明了長度為64 bits 的 payload，並且透過 memcpy 從地址 str + i 複製8個 bytes 到 payload。由於一個 char 長1個 byte，payload 裝有8個 bytes，因此對 payload 做 bitwise operation 可以一次檢測 8 個 char 是否屬於 ASCII code。
• 當剩餘的 char 數量 < 8 時(也就是 i + 8 > size)，就換成一次檢查1個 byte。

測驗 2

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

數字的 ASCII code 高4位為0011，大寫英文字母的高4位為 0100， 小寫英文字母的高4位為 0110。
於是取 MASk 為0x40的話，letter 在 in 為字母時數值為 0100 ，in 為數字時數值為 0。另外，不論大小寫字母，低四位皆是從0001開始遞增，因此要輸出其代表的十進位數值的話，只要將低四位+9即可(因為 a 表示十進位的10)。
整體程式碼的思路如下：

1. 計算 shift 值（0 => in為數字, 9 => in 為字母）
2. 取低四位 + shift 的值

測驗 3

const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF/*XXX*/) / (D) + 1))

/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n)
{   uint64_t quotient = ((__uint128_t) M * n) >> 64;
    return n - quotient * D;
}

此題參考 jemalloc 原始碼中 include/jemalloc/internal/div.h和src/div.c 的註解，可以知道實現的思路(以下的除法是實際除法，不是 C 的 rounding 版本)：

$$\begin{array}{rl}\lfloor (\lceil {\displaystyle \frac{2^k}{d}}\rceil \cdot {\displaystyle \frac{n}{2^k}})\rfloor & =\lfloor ({\displaystyle \frac{2^k+r}{d}}\cdot {\displaystyle \frac{n}{2^k}})\rfloor \\ & =\lfloor ({\displaystyle \frac{2^k\cdot n}{d\cdot 2^k}}）+({\displaystyle \frac{r\cdot n}{d\cdot 2^k}})\rfloor \\ & =\lfloor ({\displaystyle \frac{n}{d}}）+({\displaystyle \frac{r\cdot n}{d\cdot 2^k}})\rfloor \\ & =\frac{n}{d}+\lfloor ({\displaystyle \frac{r\cdot n}{d\cdot 2^k}})\rfloor \end{array}$$
其中

$r=-(2^k)modd,n=q\cdot d$。
由於

$r<q$ , 要讓最後的 flooring function 為 0 只要使

${\displaystyle \frac{n}{2^k}}<1$ 即可(原始碼取 k = 32)，就能達成利用

$\lfloor (\lceil {\displaystyle \frac{2^k}{d}}\rceil \cdot {\displaystyle \frac{n}{2^k}})\rfloor$ 計算

${\displaystyle \frac{n}{d}}$ 的目標。
了解上述數學式後，就可以對此題的程式碼作相同的數學分析：
此處

$$\begin{array}{rl}\lfloor (\lceil {\displaystyle \frac{2^k-1}{d}}\rceil \cdot {\displaystyle \frac{n}{2^k}})\rfloor & =\lfloor ({\displaystyle \frac{2^k+r\prime }{d}}\cdot {\displaystyle \frac{n}{2^k}})\rfloor \\ & =\lfloor ({\displaystyle \frac{2^k\cdot n}{d\cdot 2^k}}）+({\displaystyle \frac{r\prime \cdot n}{d\cdot 2^k}})\rfloor \\ & =\lfloor ({\displaystyle \frac{n}{d}}）+({\displaystyle \frac{r\prime \cdot n}{d\cdot 2^k}})\rfloor \\ & =\lfloor ({\displaystyle \frac{n-t}{d}}）+{\displaystyle \frac{t}{d}}+({\displaystyle \frac{r\prime \cdot n}{d\cdot 2^k}})\rfloor \\ & =\frac{n-t}{d}+\lfloor ({\displaystyle \frac{t}{d}}+{\displaystyle \frac{r\prime \cdot n}{d\cdot 2^k}})\rfloor \end{array}$$
其中

$r\prime =1+(-(2^k)modd),{\displaystyle \frac{n-t}{d}}=\lfloor {\displaystyle \frac{n}{d}}\rfloor$ ，

$t<d$。
我們只需讓

$({\displaystyle \frac{t}{d}}+{\displaystyle \frac{r\prime \cdot n}{d\cdot 2^k}})$ < 1 即可。

固定

$k=64$，分析邊界情況。
當

${\displaystyle \frac{r\prime }{d}}=1$ ,

${\displaystyle \frac{n}{2^k}}={\displaystyle \frac{2^{32}-1}{2^{64}}}$(兩者都達到最大值)時，
取

${\displaystyle \frac{t}{d}}={\displaystyle \frac{(2^{32})-1}{2^{32}}}$
會發現

$({\displaystyle \frac{t}{d}}+{\displaystyle \frac{r\prime \cdot n}{d\cdot 2^k}})$ < 1 ，
由於

${\displaystyle \frac{(2^{32}-1)-1}{2^{32}-1}}<{\displaystyle \frac{(2^{32})-1}{2^{32}}}$，
因此就算

${\displaystyle \frac{t}{d}}$為最大值(

${\displaystyle \frac{(2^{32}-1)-1}{2^{32}-1}}$)，

$({\displaystyle \frac{t}{d}}+{\displaystyle \frac{r\prime \cdot n}{d\cdot 2^k}})$ < 1。
所以可以用

$\lfloor (\lceil {\displaystyle \frac{2^k-1}{d}}\rceil \cdot {\displaystyle \frac{n}{2^k}})\rfloor$求得

$\lfloor {\displaystyle \frac{n}{d}}\rfloor$。

測驗 4

bool divisible(uint32_t n)
{
    return n * M <= M - 1/*YYY*/;
}

因為

$M=\lfloor {\displaystyle \frac{2^{64}-1}{d}}\rfloor +1=0x5555555555555556$ , 當 M 與其他數相乘時可以分成三種 case:

1. $M\cdot (3m)=(0x\stackrel{\mathrm{共}16\mathrm{個}}{\overbrace{5555....5555}}+1)\cdot (3m)=0+2m$
2. $M\cdot (3m+1)=(0x\stackrel{\mathrm{共}16\mathrm{個}}{\overbrace{5555....5555}}+1)\cdot (3m+1)=0+2m+(M-1)$
3. $M\cdot (3m+2)=(0x\stackrel{\mathrm{共}16\mathrm{個}}{\overbrace{5555....5555}}+1)\cdot (3m)=0+2m+2(M-1)$
   當 m >= 0 時，只有
   $M\cdot (3m)<(M-1)$。故要判定某數 n 是否為 3 的倍數時，只要確定
   $M\cdot (n)<(M-1)$即可。

測驗 5

#include <ctype.h>
#include <stddef.h>
#include <stdint.h>

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)

/* vectorized implementation for in-place strlower */
void strlower_vector(char *s, size_t n)
{
    size_t k = n / 8;
    for (size_t i = 0; i < k; i++, s += 8) {
        uint64_t *chunk = (uint64_t *) s;
        if ((*chunk & PACKED_BYTE(0x80/*VV1*/)) == 0) { /* is ASCII? */
            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + 0/*VV2*/); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + (-1)/*VV3*/);
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80/*VV4*/)) >> 2;
            *chunk ^= mask;
        } else
            strlower(s, 8);
    }
    
    k = n % 8;
    if (k)
        strlower(s, k);
}

從程式碼的後半段開始倒著分析，可以發現關鍵在

 uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80/*VV4*/)) >> 2;

這行，因為 0x80 >> 2 = 1 << 5，而大寫字母 A ^= (1 << 5) 就會轉為小寫。所以只要控制 (A ^ Z) 的值就能決定8個 char 中那一個要轉小寫。
PACKED_BYTE(0x80) =

$0x\stackrel{\mathrm{共}8\mathrm{個}80}{\overbrace{8080...8080}}$，我們需要控制每個80最左邊的1，也就是說(A^Z)的每8個 bits 需要長得像以下形式：
1xxxxxxx、0xxxxxxx。
於是我們必須設定只有當 char 確實是大寫字母時， A 和 Z 的 most significant bit 會不同。
可以使用

• $128+char{-}^{\prime }{A}^{\prime }$
  以及
• $128+char{-}^{\prime }{Z}^{\prime }-1$

的結果來判斷。只有當 char 為大寫字母時兩個數的 most significant bit 不同。所以我們令：

$A=128+char{-}^{\prime }{A}^{\prime }$

$B=128+char{-}^{\prime }{Z}^{\prime }-1$>，
透過 (A ^ B)&0x80 來決定對應 mask 的其中8 bits。
以向量的形式表示，就能寫成：

            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + 0/*VV2*/); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + (-1)/*VV3*/);
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80/*VV4*/)) >> 2;

測驗 6

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

以下參考csdn yutianzuijin：
如果題目改成除了 Single Number 外每個數皆出現兩次，那只要這麼寫即可：

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

每個 bit 的狀態隨 input 的變化可以用以下真值表表示：

bit state	input	output
0	0	0
0	1	1
1	1	0
1	0	1
可以發現因為只有兩個狀態需要記錄(數出現0次或1次)，所以只需要1個 bit 記錄1個 bit 的變化。
換成原題的話，有三個狀態(數出現0、1、2次)，所以需要2個 bit 記錄狀態(00->01->10->00)。
記錄狀態的 bit 由higher 和 lower 構成，bit 隨input 的變化可以用以下真值表表示：
higher	lower	input
-	-	-
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
lower_bit output 即是所求的 Single Number。
可以用以下邏輯表達式表達 lower_bit output:
$$
\begin{aligned}
lower&=lower\cdot\bar{higher}\cdot\bar{input}+\bar{lower}\cdot\bar{higher}\cdot{input}\
&=\bar{higher} \cdot(lower\cdot\bar{input}+\bar{lower}\cdot{input})\
&=\bar{higher}\cdot(lower\oplus{input})
\end{aligned}
$$
另外，higher 更新時的所用的 lower 值為新的 lower 值。將新的 lower 值作為輸入，可以畫出以下真值表：
higher	lower	input
-	-	-
0	0	0
0	1	1
0	1	0
0	0	1
1	0	0
1	0	1
可以用以下邏輯表達式表達 higher_bit output:
$$
\begin{aligned}
higher&=\bar{lower}\cdot{higher}\cdot\bar{input}+\bar{lower}\cdot\bar{higher}\cdot{input}\
&=\bar{lower} \cdot(higher\cdot\bar{input}+\bar{higher}\cdot{input})\
&=\bar{lower}\cdot(higher\oplus{input})
\end{aligned}
$$
至此我們得出 higher 和 lower bit 的邏輯表達式，轉換成 C 程式後即得原問題的解。