2023q1 Homework2 (quiz2)

contributed by < csm1735 >

測驗 1

解釋程式碼原理

此題關鍵在於找出最高位元的 1 ，並將從此位元到最低位元的所有位元 set 為 1 ，再透過對 x + 1 來使其進位成 2 的冪的值。
舉例來說 x 如果是

$(0010$

$1010{)}_2$ ，需要先 set 成

$(0011$

$1111{)}_2$ ，再透過 x + 1 成為

$(0100$

$0000{)}_2$
而因 x 為 64 位元的 uint64_t ，故最多需要右移 63 個位元。
因此程式碼為:

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

並可進一步精簡為:

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

用 __builtin_clzl 改寫

uint64_t my_next_pow2(uint64_t x) {
  int shift = 64 - __builtin_clzl(x);
  return 1UL << shift;
}

__builtin_clzl 的功能為找出最高位的 1 前面總共有幾個 0
而透過 shift = 64 - __builtin_clzl(x) 可以算出 x 在二進位下的 bits 長度，那只要對 1 左移 shift 個位元，即可得到答案。
舉例來說， x =

$(0010$

$1010{)}_2$ ，則 shift = 64 - 58 = 6 ，因此我們對 1 左移 6 個位元，即可得到答案

$(0100$

$0000{)}_2$

對應的 x86 指令

my_next_pow2:
.LFB16:
        .cfi_startproc
        endbr64
        bsrq    %rdi, %rdi
        movl    $64, %ecx
        movl    $1, %eax
        xorq    $63, %rdi
        subl    %edi, %ecx
        salq    %cl, %rax
        ret
        .cfi_endproc

產生對應的 x86 指令，可以看到 bsrq 指令。

---

測驗 2

解釋程式碼原理

此題關鍵在於 len 這個變數，代表的是當前 i 值在二進制表示下的 bits 長度，也影響到了 ans 每次需要左移幾個位元，以 ans = 1 , i = 2 為例，由於 i 的二進位表示為

$(10{)}_2$ ，也就是 len 為2，因此需先將ans 左移 2 位成

$(100{)}_2$ ，再將 i 的值

$(10{)}_2$ set 上去成

$(110{)}_2$ 。

而以下的 if 判斷影響到了 len 的值。

if (!(DDDD))
    len++;

可以發現在 i 在增加為 2 的冪次時，長度也會增加，例如 i 從 111 變為 1000 時，因此這邊需要判斷 i 是否為 2 的冪次，正確程式碼應如下:

if (!(i & i - 1))
    len++;

如果 i 為 2 的冪次， (i & i - 1) 將為 0 ，即 !(i & i - 1) 為 1 。
接著則是將 ans 左移 len 個，並 set 上 i 的值。

ans = (i | (ans << len)) % M;

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

int myConcatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0; 
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        len = 32 - __builtin_clz(i);
        ans = (i | (ans << len)) % M;
    }
    return ans;
}

__builtin_clz 的功能為找出最高位的 1 前面總共有幾個 0
透過 shift = 32 - __builtin_clz(x) 可以算出 x 在二進位下的 bits 長度，也就是變數 len 的值，即可用其來算出 ans

---

測驗 3

const uint64_t *end = qword + len >> 3;

這邊將 len 右移了 3 個位元，也就是等同於除以八，因為我們為了增加執行速度，需要一次處理 8 bytes ，這樣做可以算出能完整放入 64 bits 的共有幾組，至於不足 8 bytes 的則之後處理。

count = (1 << 3) * (len / 8)  - count;

(1 << 3) * (len / 8) 用來計算出總長度中能完整放入 64 bits 的 8 bytes 組共有幾個 bytes ，然後再減去 count (即 continuation bytes 的數量)。

count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;

最後再透過 len & 7 檢查是否有不足 8 bytes 的部份需要處理，如果有則透過 count_utf8 來計算出扣除 continuation bytes 的字元數量，然後再相加以得到結果。

---

測驗 4

解釋程式碼原理

bool is_pattern(uint16_t x)
{
    if (!x)
        return 0;

    for (; x > 0; x <<= 1) {
        if (!(x & 0x8000))
            return false;
    }

    return true;
}

上述程式碼一開始會先檢查 x 是否為 0 ，如果是則直接 return 0; ，之後迴圈內會將 x 左移一個位元，如果 x 為 0 則跳出迴圈，可發現如果 x 不為 0 且最高位不為 1 則會 return false; ，因此我們可看出 x 只有在以下形式會 return true;

1000 0000 0000 0000
1100 0000 0000 0000
1110 0000 0000 0000
.
.
.
1111 1111 1111 1111

根據此性質，可以做以下的改寫

bool is_pattern(uint16_t x)
{
    const uint16_t n = ~x + 1;
    return (n ^ x) < x;
}

將 ~x + 1 (即 -x) 和 x 做 xor 並判斷是否會小於 x
這邊以 8 bits 情況下的

$(1110$

$0000{)}_2$ 和

$(1110$

$1010{)}_2$ 來當例子:

$(1110$

$0000{)}_2$ xor

$(0010$

$0000{)}_2$ =

$(1100$

$0000{)}_2$
這邊會將原先最低位的 1 給改成 0 ，所以會小於原本的 x

$(1110$

$1010{)}_2$ xor

$(0001$

$0110{)}_2$ =

$(1111$

$1100{)}_2$
這邊會將原先中間的 0 給改成 1 ，所以會大於原本的 x