2023q1 Homework2 (quiz2)

contributed by < ShallowFeather >

測驗 1

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

AAAA 為 8
BBBB 為 32
CCCC 為 x + 1
也能將該段 code 縮短成

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

可以這樣運算是因為可以知道當右移一位並做 | 運算後會將他的右項倍增
就像是
1000000 在跟 0100000 | 後會是 1100000
也因此可以直接將下一次運算時直接右移 2 位來節省運算次數。
以此類推。

測驗 2

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

DDDD 為 i & (i - 1)
EEEE 為 ans << len
i & (i - 1) 此操作將會移除最右邊的那個 1
那如果說他是 2 的冪次方就需要多一個 bit 來存他的二進位數值，因此將 len++ 並在後面左移 len 位數並將 i 附加在 ans 右側

測驗 3

測驗 4

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

EEEE = -x
FFFF = x
此題目要求為 確認 x 的 binary 是否符合在最右邊的 1 後皆為 0
-x 為 x 的二補數
EX:
如 x = 1100 0000 0000 0000 則他的補數為 0100 0000 0000 0000
因此並不會比 x 還要大
不過如果 x 為 1100 0000 0000 0001 其補數則為 0011 1111 1111 1111
則必定大於 x