# 2023q1 Homework2 (quiz2)
contributed by < `dodo920306` >
## 測驗`1`
### 延伸問題
#### 解釋上述程式碼原理，並用 __builtin_clzl 改寫

題目敘述為：給定無號 64 位元數值 x，找出最接近且大於等於 2 的冪的值。
解法很簡單：找出 x 中最高位元位置 k，2^k+1^即為解答。
題目程式碼原理為：利用 x 為除了 0 以外的數值時，其為 1 的最大位元 k 一定存在，來使得最高位元到最低位元全部被設定 (set)。最後再加 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;
}

digraph graphname {
    nodesep=1.0
    size="4,6"
    edge[style=invis]
    step1[label="x", shape=plaintext]
    step2[label="x |= x >> 1;", shape=plaintext]
    step3[label="x |= x >> 2;", shape=plaintext]
    step4[label="x |= x >> 4;", shape=plaintext]
    step5[label="x |= x >> 8;", shape=plaintext]
    step6[label="x |= x >> 16;", shape=plaintext]
    step7[label="x |= x >> 32;", shape=plaintext]
    step8[label="x + 1", shape=plaintext]
    struct1[label="1|z|z|z|z|z|z|z|z|z", shape=record]
    struct2[label="1|1|z|z|z|z|z|z|z|z", shape=record]
    struct3[label="1|1|1|1|z|z|z|z|z|z", shape=record]
    struct4[label="1|1|1|1|1|1|1|1|z|z", shape=record]
    struct5[label="1|1|1|1|1|1|1|1|1|1", shape=record]
    struct6[label="1|1|1|1|1|1|1|1|1|1", shape=record]
    struct7[label="1|1|1|1|1|1|1|1|1|1", shape=record]
    struct8[label="1|0|0|0|0|0|0|0|0|0|0", shape=record]
    
    step1->step2
    step2->step3
    step3->step4
    step4->step5
    step5->step6
    step6->step7
    step7->step8
    struct1->struct2
    struct2->struct3
    struct3->struct4
    struct4->struct5
    struct5->struct6
    struct6->struct7
    struct7->struct8
}

至於 x == 0 時，x + 1 = 2^0^ 即為所求。因此這方法是放諸64位元皆準的。
##### 用 __builtin_clzl 改寫

初步想法如下：

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

這樣在 x != 0，的時候結果也是相同的。