2023q1 Homework2 (quiz2)

contributed by < visitorckw >

測驗一

說明

其思想為從 x 的最高有效位開始直到最低有效位都設為 1 。
利用演算法之中的倍增法的思想來快速設定位元的值。

x |= x >> 1; 可以保證最高有效位以及其較其低一位的位元都設為1。
x |= x >> 2; 可以保證最高有效位以及其較其低三位的位元都設為1。
x |= x >> 4; 可以保證最高有效位以及其較其低七位的位元都設為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;
}

使用__builtin_clzl改寫

uint64_t next_pow2(uint64_t x)
{
    return 1 << (64 - __builtin_clzl(x));
}

測驗二

說明

透過迴圈從 1 開始跑到 n 。
變數 len 用來紀錄當前迴圈所尋訪到的變數 i 的二進位位元長度。
因此每當遇到 i 是 2 的冪時，就應該要將 len 的值增加 1 。
判斷的方法為:

!(x & (x - 1))

然後將 i 的二進位串接到 ans 的尾端，其實作如下:

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

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

判斷 i 是否為2的冪可以採用以下實作:

!(i ^ (1 << __builtin_ctz(i)))

測驗三

count = (1 << 3) * (len / 8)  - count;
count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;

在 count 加上 __builtin_popcountll(t4) 過後，仍然需要對 count 進行調整。
此時的 count 所代表的是後續位元組數量，因此要將字串的長度減去後續位元組數量。
最後則是要處理不能被 8 整除的部份。

測驗四

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

首先取 x 的二補數，可以用 ~x + 1 或者 -x 。
二補數的效果相當於保持最低有效位元是 1 ，此外比最低有效位元更高的位元都取 not 。
若 x 的左側的 bits 都是 1 的話，在 x 跟 x 的二補數做 xor 操作過後，相當於只把最低有效位元設為 0 ，其餘位元皆維持不變，因此必定小於 x 。