2024q1 Homework4 (quiz3+4)

contributed by < chloe0919 >

第三週測驗題

測驗一

測驗中的程式碼透過多項式乘法逐步拆解，例如:

(a + b + c)^{2} = a^{2} + b^{2} + c^{2} + 2 (a b + b c + a c)

也就是將

a^{2}

、

b^{2}

、

c^{2}

相加後再加上兩倍的兩兩元素相乘
現在逐步將

N^{2}

展開 :

\begin{aligned} N^{2} & = (a_{n} + a_{n - 1} + a_{n - 2} + . . . + a_{0})^{2}, a_{m} = 2^{m} o r a_{m} = 0 (對 應 第 m 個 b i t 是 1 還 是 0) \\ = a_{n}^{2} + a_{n - 1}^{2} + a_{n - 2}^{2} + . . . + a_{0}^{2} + 2 [a_{n} (a_{n - 1} + a_{n - 2} + . . . + a_{0}) + a_{n - 1} (a_{n - 2} + a_{n - 3} + . . . + a_{0}) + . . . + a_{1} a_{0}] \\ = a_{n}^{2} + a_{n - 1}^{2} + a_{n - 2}^{2} + . . . + a_{0}^{2} + 2 [a_{n} a_{n - 1} + (a_{n} + a_{n - 1}) a_{n - 2} + (a_{n} + a_{n - 1} + a_{n - 2}) a_{n - 3} + . . . + (a_{n} + a_{n - 1} . . . a_{2} + a_{1}) a_{0}] \\ = a_{0}^{2} + {a_{n}^{2} + a_{n - 1}^{2} + a_{n - 2}^{2} + . . . + a_{1}^{2} + 2 [a_{n} a_{n - 1} + (a_{n} + a_{n - 1}) a_{n - 2} + . . . + (a_{n} + a_{n - 1} . . . + a_{2}) a_{1}]} + 2 (a_{n} + a_{n - 1} + . . . + a_{2} + a_{1}) a_{0} \\ = a_{0}^{2} + 2 P_{1} a_{0} + P_{1}^{2} \\ P_{m} & = a_{n} + a_{n - 1} + . . . + a_{m} \end{aligned}

所以最後可以獲得以下式子，也就是

P_{0}

即為所求平方根

\begin{aligned} N^{2} & = a_{0}^{2} + 2 P_{1} a_{0} + P_{1}^{2} = (a_{0} + P_{1})^{2} = P_{0}^{2} \end{aligned}

而且

P_{m} = P_{m + 1} + a_{m}

因為目標是要求出

P_{0}

，也就是從

a_{0}

累加到

a_{n}

，所以要試出從

m = n

到

m = 0

所有的

a_{m}

，

a_{m} = 2^{m}

還是

a_{m} = 0

，只要計算出

N^{2} - P_{m}^{2}

即求得解，但因為運算成本過高，所以提供了一個想法是利用以下推導將此輪的差值 (

N^{2} - P_{m}^{2}

) 用上一輪的差值 (

X_{m + 1}

) 和

Y_{m}

表示

\begin{aligned} N^{2} - P_{m}^{2} & = N^{2} - (P_{m + 1} + a_{m})^{2} \\ = N^{2} - (P_{m + 1}^{2} + 2 P_{m + 1} a_{m} + a_{m}^{2}) \\ = (N^{2} - P_{m + 1}^{2}) + (2 P_{m + 1} a_{m} + a_{m}^{2}) \\ = X_{m + 1} - (2 P_{m + 1} a_{m} + a_{m}^{2}) \\ = X_{m + 1} - Y_{m} \end{aligned}

接下來將

Y_{m}

拆解成

c_{m}

和

d_{m}

，

c_{m} = 2 P_{m + 1} a_{m}

，

d_{m} = a_{m}^{2}

Y_{m} = {\begin{cases} c_{m} + d_{m} & i f a_{m} = 2^{m} \\ 0 & i f a_{m} = 0 \end{cases}

藉由位元運算可以從

c_{m}

，

d_{m}

推出下一輪的

c_{m - 1}

，

d_{m - 1}

(假設

a_{m - 1} = 2^{m - 1}

，

c_{m} = 2 (2^{m}) P_{m + 1}

，

d_{m} = (2^{m})^{2}

)

$c_{m - 1} = 2 P_{m} a_{m - 1} = 2 (2^{m - 1}) P_{m} = 2^{m} P_{m} = 2^{m} (P_{m + 1} + a_{m}) = {\begin{cases} c_{m} / 2 + d_{m} & i f a_{m} = 2^{m} \\ c_{m} / 2 & i f a_{m} = 0 \end{cases}$
$d_{m - 1} = a_{m - 1}^{2} = (2^{m - 1})^{2} = d_{m} / 4$

綜合上述的推導後，演算法求

P_{0}

從

a_{n}

開始算到

a_{0}

，所以需要算到

c_{- 1}

，即為所求的

N

將程式碼改為用以上推導使用到的變數做表示，因為首項

d_{n} = (2^{n})^{2} = 2^{2 n}

所以先用 (31 - __builtin_clz(n) 算出 MSB，再來 & ~1UL 是為了要把將 MSB 扣回最接近的偶數 (

2 n

)，最後再向左移

2 n

個 bit 算出

2^{2 n}

，而且每次迭代都會將 d >>= 2 對應到

d_{m} / 4

的數學公式

y = c + d 對應到的是執行

c_{m} / 2 + d_{m}

後算出

y

，而每次迭代也會執行 c >>= 1 將

c

除以 2

int i_sqrt(int n)
{
    if (n <= 1) /* Assume x is always positive */
        return n;

    int c = 0;
    for (int d = 1UL << ((31 - __builtin_clz(n)) & ~1UL); d; d >>= 2) {
        int y = c + d;
        c >>= 1;
        if (n>= y)
            n -= y, c += d;               
    }
    return c;
}

舉例

n = 36

n	d	c	y	c(after shift)	n>=y	n	c(after add)
36	16	0	16	0	True	20	16
20	4	16	20	8	True	0	12
0	1	12	13	6	False	-	-

最後 return 6

測驗二

carry = tmp / 10;
tmp = tmp - carry * 10;

根據除法原理：

f = g \times Q + r

，其中

$f$ : 被除數 (對應上述程式碼中的
$t m p$ )
$g$ : 除數 (對應上述程式碼中的
$10$ )
$Q$ : 商 (對應上述程式碼中的
$c a r r y$ )
$r$ : 餘數 (對應上述程式碼中的
$t m p - c a r r y * 10$ )

採用 bitwise operation 來實作除法，但是因為 10 無法直接用 2 的冪項來表示，而且在以下程式碼中因為 b[i] 和 a[i] 都是介於 0-9 的個位數，carry 則為 0 or 1，所以 tmp 的範圍介於 19~0

int tmp = (b[i] - '0') + (a[i] - '0') + carry;

因此為了得到精確的

t m p / 10

，要先找出除數 (

x

) 的範圍，假設需要計算的被除數 (

n

) 為

n = a b

(

a

為十位數

b

為個位數)，且

l = c d

(

c

為十位數

d

為個位數) 為比

n

小的非負整數，我們可以得到此不等式:

a . b \leq \frac{n}{x} \leq a . b 9 \Rightarrow \frac{n}{a . b 9} \leq x \leq \frac{n}{a . b}

因為

\frac{n}{a . b} = \frac{a b}{a . b} = 10

，所以一定在精確度內
再來需要證明左邊的式子成立:

\frac{n}{a . b 9} \leq x \Rightarrow \frac{a . b 9}{n} \geq \frac{1}{x}

一樣先假設

c . d \leq \frac{l}{x} \leq c . d 9

因為需要證明的是

\frac{1}{x}

最大只有到

\frac{a . b 9}{n}

，所以假設

\frac{1}{x} = \frac{a . b 9}{n}

代入上述式子中也會成立:

c . d \leq l \times \frac{a . b 9}{n} \leq c . d 9 \Rightarrow c . d \leq c d \times \frac{a . b 9}{a b} \leq c . d 9

接下來分別去證明左右兩邊的假設皆成立:

$c . d \leq c d \times \frac{a . b 9}{a b} \Rightarrow 0.1 \leq \frac{a . b 9}{a b} \Rightarrow \frac{a . b}{a b} \leq \frac{a . b 9}{a b}$ 成立
$c d \times \frac{a . b 9}{a b} \leq c . d 9 \Rightarrow \frac{c d (0.1 \times a b + 0.09)}{a b} \leq c . d 9 \Rightarrow c . d + \frac{0.09 \times c d}{a b} \leq c . d + 0.09$ 因為
$a b > c d$ 所以也成立

最後可以證明出剛開始的假設是成立的，而且只需要針對 19 討論，代表

x

在此範圍間得到的 tmp / x 直到小數點後第一位都是精確的:

a . b \leq \frac{n}{x} \leq a . b 9 \Rightarrow 1.9 \leq \frac{19}{x} \leq 1.99 \Rightarrow 9.55 \leq x \leq 10

因為10 無法直接用 2 的冪項來表示，所以需要找到接近

\frac{1}{10}

的數字

\frac{a}{2^{N}}

來表示，此測驗中挑選

2^{N} = 128

，

a = 13

，計算出來

\frac{128}{13} \approx 9.84

有落在上述範圍內

接下來透過 bitwise operation 進行計算，首先執行 tmp >> 3) + (tmp >> 1) + tmp 計算出

\frac{t m p}{8} + \frac{t m p}{2} + t m p = \frac{13 \times t m p}{8}

，之後再 << 3 算出

13 \times t m p

，因為直行右移的動作，所以需要將後面被移掉的補回去 (d0、d1、d2)，最後再往右 7 bit 算出

\frac{13 \times t m p}{128}

，也就是

t m p \div 10

的結果

d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
q = ((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2) >> 7;

而餘數的計算方式為

t m p - q \times 10

，也就是先 (q << 2) + q) 計算出

q \times 5

後再左移 1 bit 得到

q \times 10

r = tmp - (((q << 2) + q) << 1);

解釋包裝成函式後

一開始 (in | 1) - (in >> 2) 是再計算

\frac{3}{4} \times i n

，而且如果 in 為偶數需要加一，但仍不清楚為何需要此操作，之後 q = (x >> 4) + x 是要計算

\frac{3}{64} \times i n + \frac{3}{4} \times i n \approx 0.79 \times i n

，為了使算出來的

0.79

更接近

0.8

接下來連續做了 4 次逼近，最後得到一個非常接近

0.8

的值，再將

\frac{8}{10} \times i n

除以 8 後得到

\frac{1}{10} \times i n

此外使用 q & ~0x7 保留除了最後三個 bits 以外的位元，也就是相當於執行 *div << 3，例如

q = 00110011

，

* d i v = 00000110

，而 q & ~0x7 為

00110000

，相當於 *div << 3 =

00110000

。(q & ~0x7) + (*div << 1) 就是在算出 *div * 10，*mod 會等於

i n - * d i v * 10

的結果

#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
    uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
    uint32_t q = (x >> 4) + x;
    x = q;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;

    *div = (q >> 3);
    *mod = in - ((q & ~0x7) + (*div << 1));   
}

測驗三

`ilog2`

i 每次迭代都會往右移 1 bit，直到找到最高位元的位置即結束，最後計算出來的 log 也就是 i 以 2 為底的對數

int ilog2(int i)
{
    int log = -1;
    while (i) {
        i >>= 1;
        log++;
    }
    return log;
}

`size_t ilog2`

此操作是從

x = 2^{16}

開始一直逼近到

2^{1}

，假設有大於

x

的情況就進行累加後再右移

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= 65536) {
        result += 16;
        i >>= 16;
    }
    while (i >= 256) {
        result += 8;
        i >>= 8;
    }
    while (i >= 16) {
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

運用 GNU extension

__builtin_clz(v) 可以計算出 v 的最高位左邊連續 0 的個數

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(v));
}

測驗四

參考 stevendd543

Exponentially Weighted Moving Average
是一種取平均的統計手法，採取 Exponential 主要是為了使越舊的歷史資料的權重更低，以下為計算公式:

S_{t} = {\begin{cases} Y_{0} & t = 0 \\ α Y_{t} + (1 - α) \cdot S_{t - 1} & t > 0 \end{cases}

$α$ 表示歷史資料加權降低的程度，介在 0 ～ 1 之間，越高的
$α$ 會使歷史資料減少的越快
$Y_{t}$ 表示在時間
$t$ 時的資料點
$S_{t}$ 表示在時間
$t$ 時計算出的 EWMA

用以下函式算出 n 是否為 2 的冪，實際操作是去看兩種情況皆滿足時則 return True :

n 不為 0
n 和 n-1 做 and 運算時為 0

其中，只有當 n 為 2 的冪時，n-1 才會是除了最高位為 0 其他皆 1 的情況，所以 n & (n - 1) 就會是 0，例如

n = 8 = 1000

，

n = 7 = 0111

，n & (n - 1) 為 0

static inline int is_power_of_2(unsigned long n)
{
    return (n != 0 && ((n & (n - 1)) == 0));
}

struct ewma

struct ewma {
    unsigned long internal;
    unsigned long factor;
    unsigned long weight;
};

internal : 表示在時間
$t$ 時計算出的 EWMA，也就是
$S_{t}$
factor : scaling factor，用來轉換成定點數時所需的縮放位元
weight : exponential weight，但這邊儲存的是
$α$ 的倒數，也就是
$α^{'}$

ewma_init

void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
{
    if (!is_power_of_2(weight) || !is_power_of_2(factor))
        assert(0 && "weight and factor have to be a power of two!");

    avg->weight = ilog2(weight);
    avg->factor = ilog2(factor);
    avg->internal = 0;
}

因為 weight 和 factor 都要是 2 的冪，所以要先用 is_power_of_2 判斷，接下來要將 weight 和 factor 都分別使用 ilog2，也就是只儲存指數的部分

ewma_add

struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
    avg->internal = avg->internal
                        ? (((avg->internal << avg->weight) - avg->internal) +
                           (val << avg->factor)) >> avg->weight
                        : (val << avg->factor);
    return avg;
}

接下來 ewma_add 主要的操作是假設

α^{'} α = 1

，並且利用

α^{'}

將公式改寫成 :

\begin{aligned} α^{'} S_{t} & = α^{'} (α Y_{t} + (1 - α) \cdot S_{t - 1}) t > 0 \\ = α^{'} α Y_{t} + α^{'} S_{t - 1} - α^{'} α S_{t - 1} t > 0 \\ = Y_{t} + α^{'} S_{t - 1} - S_{t - 1} \end{aligned}

avg->internal 對應到的公式是

S_{t - 1}

(還沒計算出

S_{t}

，所以目前取得的是

S_{t - 1}

)，avg->weight 對應到的是

α^{'}

的指數部分，這是為了進行 bitwise operation

操作對應如下，特別要注意的是 val 需要先進行定點數的轉換，也就是需要左移 avg->factor (scaling factor) 個 bit:

$α^{'} S_{t - 1}$	$S_{t - 1}$	$Y_{t}$
(avg->internal << avg->weight)	avg->internal	val << avg->factor

而最後將整個公式 >> avg->weight，就能算出

S_{t}

測驗五

此測驗和測驗三不同的是這邊已知輸入必為 uint32_t，所以不需要和測驗三一樣採用 while 去做判斷，其中 r = (x > 0xFFFF) << 4 會先去計算出 x 大於

2^{16} - 1

時需要移動的 bit 指數的值，若 x 大於

2^{16} - 1

則 (x > 0xFFFF) 會為 1 並且將 1 往右移 4 bits，也就是乘上

2^{4} = 16

，最後將 x 往右 16(

r

) bits，其中 r |= shift 對應到的是 result += 8 的操作

最後 return 會判斷 x>1 是因為目標要計算的是 log 向上取整數的值，所以要避免忽略掉 x==0x3 和 x==0x2 的情況
而這邊會先將 x-- 再去做判斷，是因為如果不加的話結果會多一

int ceil_ilog2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;                                                                                                                                    
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (r | shift | x > 1) + 1;       
}

第四週測驗題

測驗一

popcount 用來計算數值的二進位表示中位元是 1 的個數，假設 x =

b_{31} b_{30} b_{29} . . . b_{1} b_{0}

，可以得知 popcount 的數學式為：

p o p c o u n t (x) = \sum_{n = 0}^{31} b_{n}

假設每次都將 x 往右移 1 bit ：

\begin{aligned} x & \to 2^{31} b_{31} + 2^{30} b_{30} + . . . + 2^{2} b_{2} + 2^{1} b_{1} + b_{0} \\ x >> 1 & \to 2^{30} b_{31} + 2^{29} b_{30} + . . . + 2^{1} b_{2} + 2^{0} b_{1} \\ x >> 2 & \to 2^{29} b_{31} + 2^{28} b_{30} + . . . + 2^{0} b_{2} \\ . \\ . \\ . \\ x >> 31 & \to 2^{0} b_{31} \end{aligned}

相減後，可以整理出以下數學式：

\begin{aligned} p o p c o u n t (x) & = x - ⌊ \frac{x}{2} ⌋ - ⌊ \frac{x}{4} ⌋ - \dots - ⌊ \frac{x}{2^{31}} ⌋ \\ = (2^{31} - 2^{30} - 2^{29} - . . . - 2^{0}) b_{31} + (2^{30} - 2^{29} - 2^{28} - . . . - 2^{0}) b_{30} + . . . + (2^{1} - 2^{0}) b_{1} + b_{0} \\ = \sum_{n = 0}^{31} (2^{n} - \sum_{i = 0}^{n - 1} 2^{i}) b_{n} \end{aligned}

又因為

2^{n} - \sum_{i = 0}^{n - 1} 2^{i}

為 1，所以可以用

x - ⌊ \frac{x}{2} ⌋ - ⌊ \frac{x}{4} ⌋ - \dots - ⌊ \frac{x}{2^{31}} ⌋

去計算 popcount

popcount_branchless 原理：
為了避免檢查 32 次，popcount_branchless 的實作會以 4 個位元為單位並去計算

x - ⌊ \frac{x}{2} ⌋ - ⌊ \frac{x}{4} ⌋ - ⌊ \frac{x}{8} ⌋

，最後使用 v = (v + (v >> 4)) & 0x0F0F0F0F 將每 4 位元中的 set bit 的個數全部加到 byte 中

Hamming distance ：
A ^ B 會計算出 A 和 B 二進位的每個位元的差，之後再以 __builtin_popcount(A ^ B) 就能計算出 A ^ B 總共的 set bit 個數

int totalHammingDistance(int* nums, int numsSize)
{
    int total = 0;;
    for (int i = 0;i < numsSize;i++)
        for (int j = 0; j < numsSize;j++)
            total += __builtin_popcount(nums[i] ^ nums[j]); 
    return total >> 1;
}

針對 Total Hamming Distance，要計算出 nums 中所有的 Hamming Distance，所以要以兩個迴圈去計算出整個陣列的 Hamming Distance，最後 return total >> 1 是因為多計算了一次

Total Hamming Distance 改進

利用 mask 表示每次需要取出的 bit 的遮罩，並且在 for 迴圈中計算出 nums 中元素該 bit 所有為 1 的個數，並且 total+=(one*(numsSize-one)) 是去計算為 1 和為 0 的個數相乘後的結果再累加

分析時間：
上述方法會使用到兩個 for 迴圈對 nums 中任兩個元素作計算，還有每次都要計算 nums[i] ^ nums[j] 也就是需要

n

的位元長度，因此時間複雜度超過

O (n * n u m s S i z e^{2})

採用改進方法只需要時間複雜度

O (n * n u m s S i z e)

(其中

n

為 32 bits)

int totalHammingDistance(int* nums, int numsSize) {
    int total=0;
    __uint32_t mask=1;
    while(mask!=0){
        int one = 0;
        for(int i = 0 ;i<numsSize;i++){
            __uint32_t bit = nums[i] & mask;
            if(bit) one++;
        }
        total+=(one*(numsSize-one));
        mask <<= 1;
    }
    return total;
}

測驗二

Remainder by Summing digits
當 n 以二進位進行表示時，可以寫成

b_{n - 1} b_{n - 2} . . . b_{1} b_{0}

並且可以利用以下推導將 n 改寫

2^{k} \equiv {\begin{cases} 1 (m o d 3), & k : e v e n \\ - 1 (m o d 3), & k : o d d \end{cases}

改寫後的 n 為以下的表達式，也就是將 n 的偶數位元相加 - 奇數位元相加 ，對應程式碼也就是 n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA)。

\begin{aligned} n & = b_{n - 1} \cdot 2^{n - 1} + b_{n - 2} \cdot 2^{n - 2} + . . . + b_{2} \cdot 2^{2} + b_{1} \cdot 2^{1} + b_{0} \\ \equiv . . . - b_{3} + b_{2} - b_{1} + b_{0} (m o d 3) \end{aligned}

接下來為了將程式碼進一步簡化，用以下的定理進行推導(其中

x

代表

n

，而

m

為

0 x A A A A A A A A

，

\overset{―}{m}

為

0 x 55555555

) :

首先可以將表達式中的奇數位元相加改寫成以下，也就是先將
$x$ 的奇數位元先視為全 1 後，再扣掉
$x$ 實際奇數位元為 0 的總數(以
$k$ 代表)，最後再整理式子得到 :

$\begin{aligned} p o p c o u n t (x & \overset{―}{m}) - p o p c o u n t (x & m) \\ = p o p c o u n t (x & \overset{―}{m}) - (p o p c o u n t (m) - k) \\ = p o p c o u n t (x & \overset{―}{m}) + k) - p o p c o u n t (m) \end{aligned}$
可以發現其中
$p o p c o u n t (x & \overset{―}{m}) + k$ 也就是 x 的偶數位元為 1 的總數 + x 奇數位元為 0 的總數，並且觀察
$x o r$ 的真值表可以發現當
$B$ 為 0 時
$A \oplus B = A \oplus 0 = A$ 而
$B$ 為 1 時
$A \oplus B = A \oplus 1 = \overset{―}{A}$

$A$	$B$	$A \oplus B$
0	0	0
0	1	1
1	0	1
1	1	0

所以計算
$x \oplus m = x \oplus 0 x A A A A A A A A$ 時，偶數位元都會是
$x$ 的原始偶數位元，奇數位元則是
$x$ 的原始奇數位元
$N O T$ 後的結果，
$p o p c o u n t (x \oplus m)$ 也就是計算 x 的偶數位元為 1 的總數 + x 奇數位元為 0 的總數，所以可以得到以下等式:

$\begin{aligned} (p o p c o u n t (x & \overset{―}{m}) + k) - p o p c o u n t (m) \\ = p o p c o u n t (x \oplus m) - p o p c o u n t (m) \end{aligned}$

最後可以將程式碼改寫成 n = popcount(n ^ 0xAAAAAAAA) - 16

程式碼實現

方法一

將上面推導出來的數學式運用後會發現 n = popcount(n ^ 0xAAAAAAAA) - 16 計算出來的結果範圍在

- 16 \leq n \leq 16

之間，在此範例中為了避免

n (m o d 3)

算出來的結果為負數，所以我們要將它加上一個足夠大的 3 的倍數(例如 39)，現在

n

的範圍就會落在

23 \leq n \leq 55

之間，再經過一個

m o d 3

後(這次只需要 6 bit，因為 55 只需要 6 bit 就能表示了)，

n

的範圍為

2 \leq n \leq 4

，最後 -3 是將範圍限定在

- 1 \leq n \leq 1

。

但因為

- 1 \equiv 2 (m o d 3)

，所以最後我們想將範圍限定在 0 到 2 之間，當

n < 0

經過 (n >> 31) & 3 後會為 3，

n \geq 0

則是會得到 0，所以最後就能達成

0 \leq n \leq 2

int mod3(unsigned n)
{
    n = popcount(n ^ 0xAAAAAAAA) + 23;
    n = popcount(n ^ 0x2A) - 3;
    return n + ((n >> 31) & 3);
}

方法二 - look up table

算出 k = popcount(n ^ 0xAAAAAAAA) 後會得到

k

的範圍 :

0 \leq k \leq 32

，也就是對應到 table 中的 33 個元素，例如

k = 0

時

n (m o d 3) = k - 16 = - 16 \equiv 2 (m o d 3)

int mod3(unsigned n)
{
    static char table[33] = {2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1 };
    n = popcount(n ^ 0xAAAAAAAA);
    return table[n];
}

tictactoe 程式碼理解

tictactoe.c

利用 move_masks 定義棋盤中九個位置各自的連線狀態，視每四個 bit 為一組，分別表達該位置在連線中的順序，共 8 組則表達 8 條連線。

static const uint32_t move_masks[9] = {
    0x40040040, 0x20004000, 0x10000404, 0x04020000, 0x02002022,
    0x01000200, 0x00410001, 0x00201000, 0x00100110,
};

其中，32 bit :

$b_{31} b_{30} b_{29} b_{28}$ 代表左上到右上的連線
$b_{27} b_{26} b_{25} b_{24}$ 代表左中到右中的連線
$b_{23} b_{22} b_{21} b_{20}$ 代表左下到右下的連線
$b_{19} b_{18} b_{17} b_{16}$ 代表左上到左下的連線
$b_{15} b_{14} b_{13} b_{12}$ 代表中上到中下的連線
$b_{11} b_{10} b_{9} b_{8}$ 代表右上到右下的連線
$b_{7} b_{6} b_{5} b_{4}$ 代表左上到右下的連線
$b_{3} b_{2} b_{1} b_{0}$ 代表左下到右上的連線

以 0x40040040 為例，0x40040040 = 0100 0000 0000 0100 0000 0000 0100 0000 表示和棋盤中第一個位置有關的三種連線方式，包括第一條、第四條、第七條，其中為 0100 是因為 a 位於個個連線中的順序一:

第一條 :

	1	2	3
1	a	b	c
2	d	e	f
3	g	h	i

第四條 :

	1	2	3
1	a	b	c
2	d	e	f
3	g	h	i

第七條 :

	1	2	3
1	a	b	c
2	d	e	f
3	g	h	i

之後會以 board |= move_masks[move]; 取得了選定走法 move 對應的連線狀態，然後更新玩家的棋盤狀態，由此可見當任四個 bit 出現 0111 時，代表任一條連線的三個位置都有棋子，也就是玩家勝利，所以利用 player_board + 0x11111111 將任四個 bit 中的 0111 轉成 1000 判斷是否玩家勝利

static inline uint32_t is_win(uint32_t player_board)
{
    return (player_board + 0x11111111) & 0x88888888;
}

2024q1 Homework4 (quiz3+4)

第三週測驗題

測驗一

測驗二

解釋包裝成函式後

測驗三

ilog2

size_t ilog2

運用 GNU extension

測驗四

測驗五

第四週測驗題

測驗一

Total Hamming Distance 改進

測驗二

程式碼實現

方法一

方法二 - look up table

tictactoe 程式碼理解

Read more

2024q1 Homework5 (assessment)

linux2024-homework1

2024q1 Homework6 (integration)

2024q1 Homework2 (quiz1+2)

`ilog2`

`size_t ilog2`