2023q1 Homework2 (quiz2)

contributed by < peter91015 >

題目

測驗一

解釋程式碼

原來的程式碼如下：

uint64_t next_pow2(uint64_t x)
{
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return x+1;
} 

程式碼到 return 之前的動作都在將 x 在 leading 0-bits 以前的所有位元皆設成 1。 在不考慮 x==0 的情況下， x |= x >> 1 可以將最高位元的 1 下一個位元也設成 1 ，再做一次便可以將再下一個位元也設成 1 ， 如此重複 7 次可確保最前面八個位元必定為 1 ，接著 x |= x >> 8 可以將再往後面八位的位元也設成 1 形成最多 16 個 1， x |= x >> 16 x |= x >> 32 也是相似的操作，便可以把 leading 0-bits 以前的所有位元設為 1 ，其結果再加上 1 便是 大於 x 最小 2 的冪的數值。

用 __builtin_clzl 進行改寫

uint64_t next_pow2(uint64_t x)
{
    return 1 >> (8*sizeof(x) - __builtin_clzl(x)-1);
}

測驗二

解釋程式碼

原來的程式碼：

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0; /* the bit length to be shifted */
    /* use long here as it potentially could overflow for int */
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        /* removing the rightmost set bit
         * e.g. 100100 -> 100000
         *      000001 -> 000000
         *      000000 -> 000000
         * after removal, if it is 0, then it means it is power of 2
         * as all power of 2 only contains 1 set bit
         * if it is power of 2, we increase the bit length
         */
        if (!(i&(i-1)))
            len++;
        ans = (i | (ans << len)) % M;
    }
    return ans;
}

迴圈內部主要在做的事情有兩個：

• 判斷 i 是否為 2 的冪，代表在二進位之中有發生進位， len (記錄 i 的二進位表示的位元數)需要 +1
• 將 i 合併到 ans 裡面

要將 i 合併到 ans 裡面，我們需要先知道 i 的數值在二進位表示需要幾個位元，可以用變數 len 來記錄，而 len 的起始值為 0 ，只有 i 在二進位的表示之中有進位時 +1。在得知 i 的長度是多少後，我們就可以使用 ans << len 讓 ans 向左移出 i 所需要的位元數，再使用 | 運算子就可以把 i 合併進去。
而要判斷 i 是否為 2 的冪，可以使用 bitwise 操作 i & (i-1) ，其結果是將 i 去掉最右邊的 1 所得到的結果，如果是 0 就代表 i 為 2 的冪，同時也代表此時 i 在二進位表示有進位，需要讓 len +1 去更新 len 的數值。

嘗試使用 _builtin{clz,ctz,ffs} 改寫

測驗三

解釋程式碼原理

目標是算出有幾個 UTF-8 的字元，我們只需要找出有幾個 continuation byte ，再用 byte 的總數去扣除就可以得到字元的個數有多少。程式碼的架構是把原先一次處理一個 byte 變成一次處理八個 byte，最後如果未滿八個位元組則是套用到原本的 count_utf8 進行運算。

SWAR的處理方法

要找出 continuation byte ，我們只需要檢查每個 byte 之中的第 6 位元和第 7 位元(以 0 為開頭)並且符合 第 6 位元為 0 且第7位元為 1 ，可以參考測驗三 的舉例說明 1~6；先對整個輸入做 not 運算並且對常數 0x40404040 做 & 運算(步驟 2、3)，目的是為了消除第 6 位元和第 7 位元以外的所有資訊並且得到 not bit6 的結果(此結果為舉例說明中的 t2)，接著步驟 4 讓 t2的位元向右移一個位元，並且步驟 5 讓原來的輸入(t0) 和 t2 做 & 運算，可以在每個 byte 的第 7 位元上得到 bit7 and not bit6 的結果，並且其他的位元都會為 0 ，所以 continuation byte 的個數可以整個結果之中 1 的個數來計算，步驟6 使用函式 popcount 來計算。

測驗四

解釋程式碼原理

這個函式的目的在於檢測輸入符合正規表示式

$1^{+}{0}^{\ast }$ 這樣的形式，意即

$1\cdots 10\cdots 0$ 或

$1\cdots 1$ 的形式。原先的程式碼在檢測時會使用迴圈一直對輸入 x 進行左移直到 x 歸零，在歸零之前如果有檢測到最高位元為 0(和 0x8000 進行 & 運算判斷是否為 0)，代表在前面的位元已經出現 0 的情況下後面還有 1 (否則整個數值為 0)。
後面改寫的程式碼原理則是，先取 n 為 x 的負數，意即 1 補數再 +1，如果輸入的樣式符合上述的型式的話，會得到除了最右邊1以外其餘都是 0 的結果，將 n 和 x 做 XOR 運算的話會使 x 最右邊的 1 設成 0 而使的 n^x 的結果必定小於 x。
舉例說明：

x = 1111 0000 
n = 0001 0000 = -x
n^x = 1110 0000 < 1111 0000
(把最右邊的 1 減去所以結果小於 x)

如果是不符合輸入的樣式的話，意即連續的 1 之中會存在至少 1 個 0 ，在執行 n^x 的時候會使得夾在連續 1 之中的 0 被設成 1 導致得到的結果會比 x 來的大
舉例說明：

x = 1101 0000
n = 0011 0000
n^x = 1110 0000 > 1101 0000
(x^n 把原先夾在 1 裡面的"破洞(0)"補起來了 所以會讓結果大於x)