2023q1 Homework2 (quiz2)

contributed by<charlie0822>

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         36 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz
    CPU family:          6
    Model:               58
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         3900.0000
    CPU min MHz:         1600.0000
    BogoMIPS:            6784.20

測驗一

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 >> AAAA;
    x |= x >> 16;
    x |= x >> BBBB;
    return CCCC;
}

請補完程式碼，使其符合預期。

想法與思考

自己先從8位元開始思考，next_pow2(64)=128，每向右一次就擴展一個0，擴展6次就會有連續7個1，最後加1進位就可以得到下一個2的冪

01000000
    |
    v
01111111 (連續向右擴展 2 )
    |
    v
10000000 (加１可以得到下一個 2 的冪)

把邏輯帶入 64 位元的話就是要將 x 最高位元 1 後面位元都 set 成 1 ，最後加 1 進位到下一個 2 的冪返回。
AAAA=8 BBBB=32 CCCC=x+1

用 __builtin_clzl 改寫

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

測驗二

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 (!(DDDD))
            len++;
        ans = (i | (EEEE)) % M;
    }
    return ans;
}

請補完程式碼，使其符合預期。

想法與思考

if 判斷 i 是否是 2 的冪，因為當 i 是 2 的冪位元需要多一位，所以len需要加 1 ，在判斷中 DDDD 為 i&(i-1)，當 i 是 2 的冪時，i&(i-1)會剛好為 0 ，最後將ans向左移 len 將 i 加入到 ans 裡，故 EEEE為 ans<<len。

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

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0;
    long ans = 0;
    for (int i = 1;i <= n; i++) {
        if(__builtin_popcount(i)== 1){
            len++;                  
        }
        ans = (i | ans << len) % M;
    }
    return ans;
}

Built-in Function: int __builtin_popcount (unsigned int x)
Returns the number of 1-bits in x.

當 i 是２的冪時，代表位元中只會有１個１,需要將 len 需要加１。

測驗三

size_t swar_count_utf8(const char *buf, size_t len)
{
    const uint64_t *qword = (const uint64_t *) buf;
    const uint64_t *end = qword + len >> 3;

    size_t count = 0;
    for (; qword != end; qword++) {
        const uint64_t t0 = *qword;
        const uint64_t t1 = ~t0;
        const uint64_t t2 = t1 & 0x04040404040404040llu;
        const uint64_t t3 = t2 + t2;
        const uint64_t t4 = t0 & t3;
        count += __builtin_popcountll(t4);
    }

    count = (1 << AAAA) * (len / 8)  - count;
    count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD;

    return count;
}

想法與思考

一開始將 char *buf 轉換成 uint64，從處理 1 byte 改成可以 1 次處理８bytes, end 計算出總共有幾組的 8 bytes需要處理,進入迴圈開始計算 count 數，將字串長度減去 count 數就可以得到字元數量，由於 buf 不一定是 8 的倍數，最後有可能會有 0 ~ 7 個 bytes 需要處理, len % 8 = len & 7，故 AAAA=3，BBBB=7，CCCC=7，DDDD=0。

測驗四

#include <stdint.h>
#include <stdbool.h>

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

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

    return true;
}

改寫上述程式碼，使其達到等價行為，但更精簡有效。

bool is_pattern(uint16_t x)
{
    const uint16_t n = EEEE;
    return (n ^ x) < FFFF;
}

想法與思考

先看看一開始的程式碼， x > 0 時將 x 向左位移1個，如果最高位元不是 1 return false，是 1 的話繼續迴圈，所以這個程式是從 MSB ( Most Significant Bit )檢查到 LSB ( Least Significant Bit )是否有連續的 1 。

了解程式邏輯後，就可以開始思考如何修改程式碼，n = ~x + 1，加 1 的目的將最右邊 1 的後面位元變得跟 x 一樣，將 n 跟 x 做 XOR，如果 MSB 沒有夾雜 0 的話， XOR出來的值必會小於 x，所以 EEEE = ~x + 1 ， FFFF = x 。

這邊用 4-bits 做說明
x = 1100
n = 0011 + 1 = 0100
x ^ n = 1000 < x