2020q3 Homework2 (quiz2)

contributed by < Holycung >
2020q3 Homework2 (quiz2) 題目

目錄

• 2020q3 Homework2 (quiz2)
  • 目錄
  • 測驗 1
    • 作答
    • 延伸問題
  • 測驗 2
    • 作答
    • 延伸問題
  • 測驗 3
    • 作答
    • 延伸問題
  • 測驗 4
    • 作答
  • 測驗 5
    • 作答
    • 延伸問題
  • 測驗 6
    • 題目
    • 作答
    • 延伸問題
  • 延伸閱讀

測驗 1

目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (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;
}

請補完程式碼。

作答

0x80 在二進位表示如下。

Hexadecimal	Binary	Decimal
0x80	1000 0000	128
0x7F	0111 1111	127

透過變數 payload 型別為 uint64_t，可以在 stdint.h 的 header 當中看到這個 macro 的定義如下，在 64 位元的架構下， uint64_t 其實就是 unsigned long int ，在大多數 linux 的環境下其大小是 64 bits。
使用 memcpy 一次 copy 8 個 bytes 到 payload 進行檢查，也就是一次檢查八個字元，所以對應的 MMM 就是 0x8080808080808080。

// stdint.h
#if __WORDSIZE == 64
typedef unsigned long int        uint64_t;
#else
__extension__
typedef unsigned long long int        uint64_t;
#endif

延伸問題

解釋上述程式的運作原理，特別是為何用到 memcpy 呢？

作答

參考到網路上的 memcpy 的說明

memcpy 的實做是先檢查 memory address 是否 word aligned，如果不是會先 copy 前幾 bytes 使目前位址到 word aligned 的地方，然後以 word 而不是 byte 為單位做資料 copy。同樣一個 instruction 可以搬多個 bytes，會比用迴圈每個 byte 逐一 copy 要快，有時候甚至可以用 Intel cpu 特殊的專用指令做一次 copy 整個區塊。

TODO
將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」

承上，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對

提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對，詳見: Schema Validation with Intel® Streaming SIMD Extensions 4

測驗 2

開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值，例如 '0xF' (大寫 F 字元) 和 '0xf' (小寫 f 字元) 都該轉換為 15。考慮以下不需要分支 (branchless) 的實作:

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，其他輸入都有對應的數值。

以下摘自 ASCII 表格

• '0', '1', '2', …, '9' 對應到 0x30, 0x31, 0x32, … 0x39
• 'a', 'b', 'c', …, 'f' (小寫) 對應到 0x61, 0x62, 0x63, …, 0x66
• 'A', 'B', 'C', …, 'F' 對應到 0x41, 0x42, 0x43, …, 0x46

請補完程式碼。

作答

先觀察 hexchar2val 其函式，一開始對輸入進來的 in 先跟一個 mask 進行 bitwise and 的動作存到變數 letter，猜測其是用來判斷輸入是否為 letter，所以看了一下 ASCII-Table，字母跟數字的差別就在第 7 個 bit，所以 MASK = 0100 0000。

char	binary
0	0011 0000
…	…
9	0011 1001
A	0100 0001
…	…
F	0100 0110
a	0110 0001
…	…
f	0110 0110
0x40	0100 0000

然後再觀察到最後 return 會跟 0xf 進行 bitwise and，也就是只取最低 4 個位元回傳，這個四個位元就代表範圍是 0~15。那再看到跟 0xf 進行 and 的是 (in + shift)，輸入加上一個 shift 的變數，所以猜測原本字母的二進位後面四個位元 應該可以直接加上某的值就可以成功轉換，再回來觀察其二進位的表。

其實大小寫英文字母在 ASCII 是有設計過的，只有第六個位元不同，其他的位元都是相同的，這樣就簡單了，只要看最低的四個位元跟要回傳的數值差多少就可以了。所以觀察到 A a 的最低四個位元為 0001，而 A 代表的值為 10 二進位是 1010，所以要加上的值為 1001 就是正確的回傳值。

char	binary
A	0100 0001
a	0110 0001
10	0000 1010
…	…
F	0100 0110
f	0110 0110
15	0000 1111

接下來就可以回推到變數 shift，是透過剛剛得到的 letter 向右 shift 並進行 bitwise or，已知我們要得到的 shift 為 1001，所以就是 (letter >> 3) | (letter >> 6)，那如果傳進來的不是 letter 是 0-9 的數字了話，letter 就會是 0，在這邊得到的 shift 也會是 0，最後就直接回傳 letter，因此這樣就可以實現 branchless 的設計。

const uint8_t shift = (letter >> 3) | (letter >> 6);

延伸問題

將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值。

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>

#define MASK 0x40

uint32_t hexchar2val(char *in)
{
    size_t len = strlen(in);
    assert(len);
    assert(in[0] == '0' && (in[1] == 'x' || in[1] == 'X'));

    uint32_t val = 0;
    for (int i = 2; i < len; i++) {
        const uint8_t letter = in[i] & MASK;
        const uint8_t shift = (letter >> 3) | (letter >> 6);
        val |= ((in[i] + shift) & 0xf) << 4 * (len - i - 1);
    }
    return val;
}

int main(int argc, char const *argv[])
{   
    printf("%u\n", hexchar2val("0xF"));
    // 15
    printf("%u\n", hexchar2val("0xf"));
    // 15
    printf("%u\n", hexchar2val("0xFF"));
    // 255
    printf("%u\n", hexchar2val("0xCAFEBABE"));
    // 3405691582
    printf("%u\n", hexchar2val("0x8BADF00D"));
    // 2343432205
    return 0;
}

測驗 3

除法運算的成本往往高於加法和乘法，於是改進的策略被引入。其中一種策略是將除法改為乘法運算，例如

$\frac{n}{d}$ 在分子和分母分別乘上

$2^N$ 後，得到等價的

$n\times \frac{\frac{2^N}{d}}{2^N}$，其中對 2 的 N 次方 (power of 2) 進行除法，在無號整數的操作就等同於右移 (shift) N 個位元，又當

$d$ (除數) 的數值是已知的狀況下，

$\frac{2^N}{d}$ 可預先計算，也就是說，

$\frac{n}{d}$ 可轉換為乘法和位移操作，進而減少運算成本。不過，顯然

$\frac{2^N}{d}$ 無法總是用整數來表達 (僅在

$d$ 是 power of 2 的時候才可)，因此，我們可先估算，並將差值補償回去。

下方程式碼展示這概念，請補完程式碼。

const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(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;
}

其中 __uint128_t 是 GCC extension，用以表示 128 位元的無號數值。

預期 quickmod(5) 會得到 2, quickmod(55) 得到 1, quickmod(555) 得到 0 (555 是 3 的倍數)。

作答

透過題目有初步的理解後觀察程式碼，可以看出預先計算

$\frac{2^N}{d}$ 是透過 macro M 來完成，但是這邊

$\frac{2^N}{d}$ 無法總是用整數來表達，所以這邊的實作會要考慮的這部分的差值(後面會討論)。再看到第 6 行這邊很明顯是

$n\times \frac{\frac{2^N}{d}}{2^N}$ ，除 2^N 就是右移 (shift) N 個位元，所以這邊就知道是

$N=64$，那就可以回去想地 2 行的 macro 就可以猜測是

$\frac{2^{64}}{d}$，不過因為

$2^{64}$ 會發生溢位，並且還會有無法整除的問題，所以初步推測是把

$\frac{2^N}{d}$ 換成

$\lfloor \frac{2^N-1}{d}\rfloor +1$ (後面會討論)，所以

$2^{64}-1$ 代表XXX = 0xFFFFFFFFFFFFFFFF。最後，找到

$q$ 就可以透過

$r=n-q\ast d$ 找到餘數，過程中只會用到乘法和位移操作，降低運算成本。

其中第 2 行 UINT64_C 用意如下，詳細可以參考 UINT64_C。

Appends the correct suffix to a 64-bit unsigned integer literal.

接下來，就要來推導剛剛 macro M 的部分，可以先看到延伸問題中提到 facebook jemalloc 在其原始程式碼 include/jemalloc/internal/div.h 和 src/div.c 也有類似的實作，先看到 src/div.c 當中的註解有一段證明。

觀察 jemalloc 證明

Suppose we have

$n=q\ast d$, all integers. We know n and d, and want

$q=n/d$.
For any k, we have (here, all division is exact; not C-style rounding):

$$\begin{array}{rl}\lfloor \lceil \frac{2^k}{d}\rceil \times \frac{n}{2^k}\rfloor & =\lfloor \frac{2^k+r}{d}\times \frac{n}{2^k}\rfloor ,wherer=({-2}^k)modd\\ & =\lfloor \frac{2^k}{d}\times \frac{n}{2^k}+\frac{r}{d}\times \frac{n}{2^k}\rfloor \\ & =\lfloor \frac{n}{d}+\frac{r}{d}\times \frac{n}{2^k}\rfloor \\ & =\frac{n}{d}+\lfloor \frac{r}{d}\times \frac{n}{2^k}\rfloor \because \text{the assumption that d divides n exactly}\end{array}$$

推導到這邊只要

${\displaystyle \frac{r}{d}}\times {\displaystyle \frac{n}{2^k}}<1$ 就剩下

${\displaystyle \frac{n}{d}}$ 也就是我們一開始要求的

$q$。
那分開來看

${\displaystyle \frac{r}{d}}$ 會小於一，因為

$r$ 是

$modd$ 的餘數，因此

$r<dand{\displaystyle \frac{r}{d}}<1$。
最後

${\displaystyle \frac{n}{2^k}}$ 只要

$2^k$ 設定的夠大等式就會成立，在程式當中可以很容易的實現，因此這個想法可以把除法轉換為乘法和位移操作。

進一步推導

但是他的 case 與我們不同，因此透過這個想法，稍微修改一下並進行推導。

Suppose we have

$n=q\ast d+r$ for some

$q,0<=r<d$ . Then, we have

$$\begin{array}{rl}\lfloor \lceil \frac{2^k}{d}\rceil \cdot \frac{n}{2^k}\rfloor & =\lfloor \frac{2^k+r^{\prime }}{d}\cdot \frac{n}{2^k}\rfloor ,where{r}^{\prime }=({-2}^k)modd\\ & =\lfloor \frac{2^k}{d}\cdot \frac{n}{2^k}+\frac{r^{\prime }}{d}\times \frac{n}{2^k}\rfloor \\ & =\lfloor \frac{n}{d}+\frac{r^{\prime }}{d}\cdot \frac{n}{2^k}\rfloor \\ & =q+\lfloor \frac{r}{d}+\frac{r^{\prime }}{d}\cdot \frac{n}{2^k}\rfloor \because n=q\cdot d+r\\ & =\lfloor \frac{n}{d}\rfloor \text{if}\frac{r}{d}+\frac{r^{\prime }}{d}\cdot \frac{n}{2^k}<1\end{array}$$

所以只要

${\displaystyle \frac{r}{d}}+{\displaystyle \frac{r^{\prime }}{d}}\cdot {\displaystyle \frac{n}{2^k}}<1$ 最後的結果就會等於

$q$，稍微整理一下這邊所得到的資訊。

$$\begin{array}{rl}\lfloor \frac{n}{d}\rfloor & =\lfloor \lceil \frac{2^k}{d}\rceil \cdot \frac{n}{2^k}\rfloor \\ & =q\text{if}\frac{r}{d}+\frac{r^{\prime }}{d}\cdot \frac{n}{2^k}<1\end{array}$$

這邊如果能成立的話，我們就可以把除法轉換為乘法和位移操作，是一個很棒的想法。

回到題目

好，推導到這邊再扣回去我們的題目作法。想要透過

$\lfloor \frac{n}{d}\rfloor =q$，得到 quotient 再進一步找到餘數，但是為了加速要把除法轉換成乘法跟移位操作，於是結合上面的推導如下。

$$\begin{array}{rl}\lfloor \frac{n}{d}\rfloor & =\lfloor n\times \frac{\frac{2^N}{d}}{2^N}\rfloor \\ & =\lfloor \lceil \frac{2^N}{d}\rceil \cdot \frac{n}{2^N}\rfloor \text{if}\frac{r}{d}+\frac{r^{\prime }}{d}\cdot \frac{n}{2^N}<1\end{array}$$

這邊的 ceiling 可以轉換成 floor，可以參考 wikipedia 的 Quotients 的部分。這樣剛好驗證了前面的猜測，可以避免 overflow 且符合程式的運作邏輯。

$$\begin{array}{rl}\lfloor \frac{n}{d}\rfloor & =\lfloor n\times \frac{\frac{2^N}{d}}{2^N}\rfloor \\ & =\lfloor \lceil \frac{2^N}{d}\rceil \cdot \frac{n}{2^N}\rfloor \text{if}\frac{r}{d}+\frac{r^{\prime }}{d}\cdot \frac{n}{2^N}<1\\ & =\lfloor (\lfloor \frac{2^N-1}{d}\rfloor +1)\cdot \frac{n}{2^N}\rfloor \end{array}$$

探討此方法的限制

我們對再來深入探討條件成立的情形，也就是

$\frac{r}{d}+\frac{r^{\prime }}{d}\cdot \frac{n}{2^N}<1$，已知都是整數且

$r,r^{\prime }<d$。

$$\begin{array}{rl}\frac{r}{d}+\frac{r^{\prime }}{d}\cdot \frac{n}{2^N}& \le \frac{d-1}{d}+\frac{d-1}{d}\cdot \frac{n}{2^N}<１\end{array}$$

經過化簡如下

$$\begin{array}{rl}\frac{d-1}{d}+\frac{d-1}{d}\cdot \frac{n}{2^N}& <１\\ (d-1)+(d-1)\cdot \frac{n}{2^N}& <d\\ (d-1)\cdot \frac{n}{2^N}& <1\\ n\cdot (d-1)& <2^N\end{array}$$

因此，可以觀察到

$n$ 跟

$d$ 的大小取決於我們怎麼決定

$2^N$，所以要想辦法讓 n 跟 d 兩者的範圍最大，

$n$ 跟

$d-1$ 的最大值都要小於

$2^{N/2}$。 Bingo! 到這邊我們得到一個很重要訊息，只要在給定的 N 設定好 n, d 的範圍，我們就可以把

$\lfloor \frac{n}{d}\rfloor =q$ 轉換成

$\lfloor (\lfloor \frac{2^N-1}{d}\rfloor +1)\cdot \frac{n}{2^N}\rfloor$ 進而得到 quotient。然後這個範圍可以很輕易的在程式當中來實作，今天以題目的範例程式為例如下。

const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(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;
}

$N=64$，所以

$n$ 跟

$d-1$ 要小於

$2^{32}$，所以可以看到題目的變數 D, n 的型別都是 uint32_t，在這個範圍內是可以滿足我們的證明，也可以得知 XXX 其實就是

$2^{32}-1$ 也就是 0xFFFFFFFFFFFFFFFF。

延伸問題

include/jemalloc/internal/div.h 和 src/div.c 的運作原理已在上面敘述。

TODO: 抽離快速除法實作為獨立的程式碼，撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距
RinHizakura
WeiCheng14159

測驗 4

延伸測驗 3，我們想判斷某個數值能否被指定的除數所整除，在 D 和 M 都沿用的狀況下，程式碼如下:

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

以 D = 3 來說，divisible(7) 要得到 0 (即 7 無法被 3 整除)，divisible(87) 要得到 1 (即白痴是三的倍數)

請補完程式碼。

作答

在回答之前先詳細閱讀 Faster remainders when the divisor is a constant: beating compilers and libdivide。

重新檢視

$\frac{n}{d}=n\times \frac{\frac{2^N}{d}}{2^N}$，當我們想將

$n$ 除以

$4$ 時，就相當於乘以

$0.25$，所以我們可將

$\frac{5}{4}$ 改為

$5\times 0.25$，我們得到整數的部分 (即

$1$)，和小數部分 (即

$0.25$)，後者乘以

$4$ 就是

$1$，也就是餘數。

在程式當中的 macro

$M=\lfloor \frac{2^N-1}{d}\rfloor +1$，這邊就是把除

$d$ 的動作改成乘

$1/d$，然後乘上最大值

$2^N-1$，不過這邊還是有可能會遇到循環小數除不盡的狀況，所以會做 floor 之後再加一回去，例: 0x5555555555555555 + 1 = 0x5555555555555556，其實這邊代表的就是

$\frac{1}{d}$ 的小數部分。

因此我們今天把

$n\times M$，整數的部分會因為超過最大值會被 overflow 只剩下小數，所以這邊代表的就是

$\frac{n}{d}$ 的小數部分。

• $n\times M=n\times (\lfloor {\displaystyle \frac{2^N-1}{d}}\rfloor +1)=>{\displaystyle \frac{n}{d}}\mathrm{的}\mathrm{小}\mathrm{數}\mathrm{部}\mathrm{分}$
• $M-1=\lfloor {\displaystyle \frac{2^N-1}{d}}\rfloor =>{\displaystyle \frac{1}{d}}\mathrm{的}\mathrm{小}\mathrm{數}\mathrm{部}\mathrm{分}，\mathrm{沒}\mathrm{有}\mathrm{補}1$

所以今天我們只要透過判斷

$n\times m\le M-1$，就可以輕易的判斷

$n$ 使否能被

$d$ 整除。

測驗 5

在 64 位元處理器架構 (以下針對 x86_64, little endian)，我們可引入向量化 (vectorized) 的手段，避免一次比對一個字元，而是直接操作一整個 word (對 x86_64 來說，就是 64 bits，或 8 個位元組)。沿用上述的 strlower 函式，我們用這樣的思路實作向量化的 strlower，程式碼列表如下:

#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(VV1)) == 0) { /* is ASCII? */
            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3);
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;
            *chunk ^= mask;
        } else
            strlower(s, 8);
    }
    
    k = n % 8;
    if (k)
        strlower(s, k);
}

請補完程式碼。

作答

這邊的作法跟前面的判斷 ascii 字元的方法類似，先來看到 PACKED_BYTE 這個 macro，把吃進來的變數先轉成 uint64_t，然後取最後一個 byte，擴充成八個 byte。

看到第 13 行的判斷，透過註解可以知道這邊是判斷 chunk，這八個 byte 是否都是 ascii 的字元，透過前面題目 1 可以知道這邊要填入 0x80。

看到第 17 行 *chunk ^= mask，這邊是透過 xor mask 對 chunk 進行 tolower 的動作，那已知大寫換成小寫是透過第 6 個 bit 做 XOR 1，所以如果是 A-Z 的字元 mask 每個 byte 要是第 6 個 bit 為 1，其餘為 0，而如果不是 A-Z 了話，mask 要是 0，xor 才會是原本的值。回來看到上一行 mask 是如何成生的，最後有一個向右 shift 兩個的動作，所以前面 (A ^ Z) & PACKED_BYTE(VV4) 第 8 個 bit 為 1，其餘為 0，那可以看出 (A ^ Z) 是用來判斷是否為 A-Z 的字元，PACKED_BYTE(VV4) 這邊的 VV4 = 0x80。

最後看到 (A ^ Z) 要跟 0x80 bitwise and，這樣我們就只要確保第八個位元，如果是 A-Z 的字元第八個 bit 就要是 1，其他字元則是 0，所以往前看到 14 15 行，稍微觀察一下就可以發現，128-'A' 128-'Z'，因為 128 在二進位就是 1000 0000，運用這樣的方法可以判斷出字元是否在 A-Z 之間，參考了 sammer1107 畫出了下面的表格幫助理解。

字元 c	c + 128-'A'	c + 128-'Z'-1
< A	< 128	< 128
A - Z	> 128	< 128
> Z	> 128	> 128

所以今天只有字元是在 A-Z 之間的我們 (A ^ Z) 的第八個位元才會是 1，其餘的都是 0，這樣就可以得到正確的 mask。

延伸問題

將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為。

作答

參考國際標準 C 語言標準 ISO/IEC 9899，C11 The latest freely available draft。

3.4.3 undefined behavior

behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements.

這邊定義了 undefined behavior，以下簡稱 UB。

J.2 Undefined behavior

The program attempts to modify a string literal (6.4.5).

在規格書當中有明確定義一連串的 UB，其中就有一條是企圖修改一個 string literal。

6.4.5 String literals

A character string literal is a sequence of zero or more multibyte characters enclosed in double-quotes, as in "xyz".
In translation phase 7, a byte or code of value zero is appended to each multibyte character sequence that results from a string literal or literals. The multibyte character sequence is then used to initialize an array of static storage duration and length just sufficient to contain the sequence.

It is unspecified whether these arrays are distinct provided their elements have the appropriate values. If the program attempts to modify such an array, the behavior is undefined.

這邊可以看到 string literals 的定義，然後是 static storage duration，嘗試去更動其內容是 undefined behavior。

6.7.9 Initialization

32 EXAMPLE 8 The declaration
char s[] = “abc”, t[3] = “abc”;
defines ‘‘plain’’ char array objects s and t whose elements are initialized with character string literals. This declaration is identical to

char s[] = { ‘a’, ‘b’, ‘c’, ‘\0’ },
t[] = { ‘a’, ‘b’, ‘c’ };

The contents of the arrays are modifiable. On the other hand, the declaration

char *p = “abc”;

defines p with type ‘‘pointer to char’’ and initializes it to point to an object with type ‘‘array of char’’ with length 4 whose elements are initialized with a character string literal. If an attempt is made to use p to modify the contents of the array, the behavior is undefined

這邊可以看到明確的例子說明，string literal 的兩種用不同，第一種是會當成 char array object 的初始化陣列，就等於一搬的宣告一樣，所以是可修改的。

第二種指標則是宣告一個型別為 array of char 的指標指向一個初始化過的物件，用指標修改這個內容的行為是 UB。指標所指向的這個物件，可以在 Frequently Asked Questions 看到第二點有更詳細的說明。

2. Anywhere else, it turns into an unnamed, static array of characters, and this unnamed array may be stored in read-only memory, and which therefore cannot necessarily be modified.

這個用 string literal 初始化的 array of char 會被放在 read-only 的記憶體位置，再將該位置回傳給 pointer to char 這個變數。這個 read-only 的位置介紹可以參考 hankluo6 同學的回答。

測驗 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;
} 

請補完程式碼。

作答

光看程式一開始看不出甚麼端倪，少數的線索只有 bitwise xor and 兩個 operation，還有 lower higer 兩個變數。從這個出現次數的問題來想，假設今天是每個數字出現兩次，那可以利用 xor 的特性，假設今天 1 出現兩次，對一個數字 0 做 xor 1 兩次，就會得到原本的值 0，利用這個特性我們就可以輕易的找到只出現一次的數字。

回到題目，今天是一個數字會重複出現三次，那透過剛剛的想法，我們可以用兩個變數來表達一個數字出現幾次的狀態，分別是 lower 跟 higher，可以把他想成是一個狀態機的 state machine 的概念，如下表。

出現次數	higher	lower
0	0	0
1	0	1
2	1	0
3	0	0

沒出現過兩個都是 0，第一次出現 lower 變成 1，以此類推，然後出現到第三次後兩個變數都要變成 0。

那再回來看到程式，lower ^= nums[i] 這邊 xor 的動作可以把他想成將當前出現的數字加入或移除，假設該數字沒出現過就是第一次做 xor 所以是加入，假設該數字出現過就是再做一次 xor 也就是移除。
lower &= ~higher 則是如果當前出現的數字已經在 higher 出現過了，代表出現了第三次，則 lower 就要把他移除。如果沒有在 higher 出現過，就放到 lower 當中。

higher 的部分就是反之亦然，這樣就可以符合狀態機的行為，而最後 lower 就會只剩下出現過一次的數字，所以回傳 lower 就是正確答案。

延伸問題

將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼;

作答

TODO

延伸閱讀

• 64-bit computing
• memcpy 小常識
• ASCII-Table
• C語言 - uint8_t, uint16_t, uint32_t, uint64_t
• UINT64_C
• jemalloc src/div.c
• jemalloc include/jemalloc/internal/div.h
• LaTeX/Mathematics
• Floor and ceiling functions
• Faster remainders when the divisor is a constant: beating compilers and libdivide
• ISO/IEC 9899
• C11 The latest freely available draft
• Frequently Asked Questions