2023q1 Homework2 (quiz2)

ontributed by < OWaitsInTime >

測驗 1

uint64_t next_pow2(uint64_t x)
{
    x |= x >> 1;    //1
    x |= x >> 1;    //2
    x |= x >> 1;    //3
    x |= x >> 1;    //4
    x |= x >> 1;    //5
    x |= x >> 1;    //6
    x |= x >> 1;    //7
    x |= x >> 8;    //8
    x |= x >> 16;   //9
    x |= x >> 32;   //10
    return x + 1;   //11
}

假定 x = 0010000000000000 根據上述程式得下列結果
(用半形空格隔開方便閱讀)

x = 0010 0000 0000 0000
x = 0011 0000 0000 0000    //1
x = 0011 1000 0000 0000    //2
x = 0011 1100 0000 0000    //3
x = 0011 1110 0000 0000    //4
x = 0011 1111 0000 0000    //5
x = 0011 1111 1000 0000    //6
x = 0011 1111 1100 0000    //7
x = 0011 1111 1111 1111    //8
x = 0011 1111 1111 1111    //9
x = 0011 1111 1111 1111    //10
x = 0100 0000 0000 0000    //11

可以發現到程式目標是將最高位 1 右側所有位元變更為 1

//8 可以變更 1 右側距離8位元的 bit 為1 ，連續8個 1 則會實現向右複製8個 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 改寫

__builtin_clzl的功能是回傳高位元 0-bits 的數量
64 - __builtin_clzl可以得到最高 1 的 bit 位置

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

測驗 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 (!(i & (i - 1)))
            len++;
        ans = (i | (ans << len)) % M;
    }
    return ans;
}

if it is power of 2, we increase the bit length 要求對 n 進行判斷，若為 2 的冪次方則 len + 1

從二進位表示觀察，確實發現在 2 的冪次方時 len 會增加 1 ， i & (i - 1)可以用來判斷 i 是否為 2 的冪次方

0 = 0
1 = 1
2 = 10
3 = 11
4 = 100
5 = 101
6 = 110
7 = 111
8 = 1000

i | (ans << len) 用來將 i 與 1 ~ (i-1) 做串接

為何是

$mod{10}^9+7$ ？

1. ${10}^9+7$ 是一個質數
2. int32 的最大值是
   $2^{31}-1$ ，所以對於 int32 來說
   ${10}^9+7$ 足夠大
3. int64 的最大值是
   $2^{63}-1$ ，
   ${10}^9+7$ 的平方不會在 int64 中溢出
4. 因為 (a∗b)%c=((a%c)∗(b%c))%c ，
   $mod{10}^9+7$ 不會在 int64 中溢出

用 __builtin_{clz,ctz,ffs} 改寫

clz : Counting Leading Zero
ctz : Counting Trailing Zero
ffs : Find First Set

__builtin_ffsl(long) 會回傳最高位 1 的位置

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

測驗 3

測驗 4

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

for迴圈可以看出 pattern 為連續的 1 ，所給程式碼樣式可以明顯觀察到此結果(用半形空格隔開方便閱讀)

pattern: 8000 (1000 0000 0000 0000)
pattern: c000 (1100 0000 0000 0000)
pattern: e000 (1110 0000 0000 0000)
pattern: f000 (1111 0000 0000 0000)
pattern: f800 (1111 1000 0000 0000)
pattern: fc00 (1111 1100 0000 0000)
pattern: fe00 (1111 1110 0000 0000)
pattern: ff00 (1111 1111 0000 0000)
pattern: ff80 (1111 1111 1000 0000)
pattern: ffc0 (1111 1111 1100 0000)
pattern: ffe0 (1111 1111 1110 0000)
pattern: fff0 (1111 1111 1111 0000)
pattern: fff8 (1111 1111 1111 1000)
pattern: fffc (1111 1111 1111 1100)
pattern: fffe (1111 1111 1111 1110)
pattern: ffff (1111 1111 1111 1111)

可精簡成下方程式碼

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

以 1111 1111 0000 0000為例，先取其 2 的補數

 x = 1111 1111 0000 0000
-x = 0000 0001 0000 0000

接著進行XOR運算

    x = 1111 1111 0000 0000
    n = 0000 0001 0000 0000
 -------------------------------
n ^ x = 1111 1110 0000 0000

在這種 pattern 下 (n ^ x) 一定會小於 x

假設不是此種 pattern ，(n ^ x) 就不會小於 x

    x = 1111 1110 0001 0000
    n = 0000 0001 1111 0000
 -------------------------------
n ^ x = 1111 1111 1110 0000