2024q1 Homework4 (quiz3+4)

contributed by < weihsinyeh >

第三週測驗

測驗 1

改成版本二的原因是為了不使用 libm 的 log2，因為log 2 會導致錯誤。

Domain error: x is negative errno is set to EDOM. An invalid floating-point exception (FE_INVALID) is raised.
Pole error: x is zero errno is set to ERANGE. A divide-by-zero floating-point exception (FE_DIVBYZERO) is raised.

但這裡個錯誤如果設定好 N 不會發生。接下來是精度問題。

參考 Find the log base 2 of an integer with a lookup table
作業使用 flp2( x ) = 1 << ( 31 - nlz( x ))，用這個方式的缺點如下

However, for these relations to hold for and the computer must have its shift instructions defined to produce 0 for shift amounts of –1, 32, and 63. Many machines (e.g.,PowerPC) have “mod 64” shifts, which do this. In the case of –1, it is adequate if the machine shifts in the opposite direction (that is, a shift left of –1 becomes a shift right of 1).

Rounding Down to a Multiple of a Known Power of 2

根據　POWER-OF-2 BOUNDARIES
求 unsigned x 的rounding up 的八倍數。
( x + 7 ) & –8 先+ 7round up再 & -8。-8 的2's : 1...11000 可以把多餘的餘數去掉。
求 signed x 的rounding up 的八倍數，改變求 unsigned x 的 t。
t ← ( x >> 31 ) & 7; ( x + t ) & –8 所以是正數 t 會變成 0 ，負數會 t 會為 7。

x = -31 2's: 11100001
（一） arithmetic right shift ( x >> 7 ) 後為 11111111 。
（二） & 7 2's: 00000111 得到 t : 00000111。
（三） x + t ：11100001 + 00000111 = 11101000
（四） & 11111000 = 11101000 = -24

x = 31 2's: 00011111
（一） arithmetic right shift ( x >> 7 ) 後為 00000000 。
（二） & 7 2's: 00000111 得到 t : 00000000。
（三） x + t ：00011111 + 00000000 = 00011111
（四） & 11111000 = 00011000 = 24

但第二步每次只要是負數都會是 t : 00000111 ，是正數 t : 00000000？

x & ((-1) << k )
(x >> k )<< k

Rounding Up/Down to the Next Power of 2

測驗題

接下來是逼近的概念。我在這裡想最久的是
一開始

$N^2=(a_n+a_{n-1}+a_{n-2}+...+a_1{)}^2$ 去表示。但卻從來沒有算過

$N^2$ 的值。反而每次逼近的時候是找 N 的二進位要如何被表示，哪個位元要被 set 為 1。

那就舉個例子來看：
一開始是

${10}^2=100$ 接下來從flp(10)也就是 8 開始找。發現

$8^2<{10}^2$ ，也就是找到哪些二進位表示為 1010 。

$X_m=N^2-P_m^2$ 確認這個是否要加這個位元為 1。

想了一天終於想通了，原先我一直很困惑題目解說是用

$N^2=(a_n+a_{n-1}+a_{n-2}+...+a_1{)}^2$。之所以困惑在於舉例給予程式 36，要得到的數值為 6 。而演算法卻是一直在找 6 的二進位為何?當最後逼近得到110 就回傳 6。但我一直無法聯想到到底一開始為何會有 6 ? 要如何逼近它？因為這很像一個程式碼輸入整數要求回傳二進位。並不是要求平方根的程式碼。

測驗題這句話

$P_0=a_n+a_{n-1}+a_{n-2}+...+a_0$ 即為所求平方根

$N$，就花了很多時間去想。因為沒連結到上面這句話 原理是將欲求平方根的 N^2拆成。我後來看懂程式碼才知道

$P_0=a_n+a_{n-1}+a_{n-2}+...+a_0$ 是即為所求

$N^2$的平方根

$N$。

再來是當

$a_m=0$ 則

$c_{m-1}=P_m{2}^m=(P_{m+1}+a_m)2^m=P_{m+1}{2}^m+a_m{2}^m=c_m/2$，
是改成

$c_{m-1}=P_m{2}^m=(P_{m+1}+a_m)2^m=P_{m+1}{2}^m+a_m{2}^m=0$。
依據

$c_m=2P_{m+1}{a}_m+a_m^2$ ，當

$a_m=0$ 則

$c_m=0$ 。看到一直想不明白有哪些情況它還是

$c_m/2$。

$X_{n+1}=N$。
依據

$X_m=N^2-P_m^2$ ，則

$X_{n+1}=N^2-P_{n+1}^2$ 因為已知

$a_n$ 為最大的，所以

$P_{n+1}=0$，那代回去算式我認為是

$X_{n+1}=N^2$ 才對。但有可能是我現在還沒想不出來寫

$X_{n+1}=N$ 的原因。

雖然如此，還是不妨礙解釋程式碼，回到上面 36 的例子，要求他的平方根，那就是

$N^2=36$ 要回傳答案

$N$ 也就是 6 。

知道目標後，先寫一個將十進位　X　轉換為二進位的方式，寫 i=32 是因為整數用四個位元組，一個位元組八個位元。然後這個程式就是把如果從最高位元

$2^{32}$ 到低位元

$2^0$ 是該

$X>=2^i$ 那bits pattern 一定會將第 i 位元設為 1 。

ret = 0;
for(i = 32; ;i-=1){
    ret << 1
    if( >= 2^i){
        ret = (ret+1);
        X -= 2^i
    }
}

由於看到 i 都會被拿來用作 2 的冪次，所以我們可以簡化為，然而這依然有從 i = 2^32 很耗時的問題。

for(i = 2^32; ;i>>1){
    ret << 1
    if(X >= i){
        ret = (ret+1);
        X -= i
    }
}

解決耗時問題，修正成 i = fls(N) 。對應測驗程式碼i = 1UL << ((31 - __builtin_clz(X))

for(i = fls(X);;i>>1){
    ret << 1
    if(X >= i){
        ret = (ret+1);
        X -= i
    }
}

思考完後這還是給定 X 轉換二進位的程式碼。但要如何從這個改成平方根，首先就是要改變 if 判斷式的條件，而判斷式內要做的是為將位元設定為 1 則不用修改，因為輸出平方根也需要將位元設為 1 。因此設為 1 的時機點要調整，要將原先用於輸出二進位的改為輸出平方根。而這裡要用二進位做平方根的原因，我認為是因為想要用這個遞迴作逼近的功能。同時當如果高位元已經滿足以剛好求得平方根，則不用考慮低位元。同時如果先考慮低位元，缺點是後續高位元如果符合平方根的話，低位元要調整。

接下來就是

$X=N^2$ 要求

$N$，如果套用上述的程式碼，我們最後需要得到

$N$ 的二進位表示。其二進位表示為

$b_n{b}_{n-1}{b}_{n-2}...b_1{b}_0$ ， 如果寫成

$N=a_n+a_{n-1}+a_{n-2}+...+a_1+a_0$ 則對應到二進位

$a_x$ 為

$2^x$ 或

$0$。所以現在修改上面的程式碼：

for(i = fls(X);;i>>1){
    ret << 1
    if(X >= i^2){
        ret = (ret+1);
        X -= i^2
    }
}

然而這是個錯誤範例因為 X 跟 平方根 i^2，絕對不是將每個位元所表示的 2 的冪取平方。因為這樣會變成錯誤

$N^2=a_n^2+a_{n-1}^2+a_{n-2}^2+...+a_1^2+a_0^2$
正確

$N^2=(a_n+a_{n-1}+a_{n-2}+...+a_1+a_0{)}^2$
此為

$(a+b{)}^2=a^2+2ab+b^2\ne a^2+b^2$ 的概念，所以目標判斷式變成能夠考慮到其他位元。

也因此有了下面

$N^2=(a_n+a_{n-1}+a_{n-2}+...+a_1+a_0{)}^2$ =

$a_n^2+[2a_n+a_{n-1}]a_{n-1}+[2(a_n+a_{n-1})+a_{n-2}]a_{n-2}+\cdots +[2(a_n+a_{n-1}+\cdots +a_1)+a_0]a_0$
因為每次看到上面的迴圈每次都只經過一個位元（第x個位元），確認

$b_x$ 是否要被設為 1。所以現在做的是把

$a_n$

$a_{n-1}$

$\dots a_1$

$a_0$ 分開考慮。因為剛好由高位元到低位元去做逼近，所以每一輪其實知道之前幾輪的結果。

$P$ 表示 previous 是在前幾輪有用過得位元。因此改為

$P$ 表示。

$a_n^2+[2a_n+a_{n-1}]a_{n-1}+[2(a_n+a_{n-1})+a_{n-2}]a_{n-2}+\cdots +[2(a_n+a_{n-1}+\cdots +a_1)+a_0]a_0$

$a_n^2+[2P_n+a_{n-1}]a_{n-1}+[2P_{n-1}+a_{n-2}]a_{n-2}+\cdots +[2P_1+a_0]a_0$
因此

$P_m=a_n+a_{n-1}+\cdots +a_m$ 。接下來超級有趣。首先第一輪考慮

$a_n$ 開始，平方

$a_n^2$ 是否小於 X ？下一輪

$a_{n-1}$ 考慮進來，赫然發現前兩項相加為

$a_n^2+[2a_n+a_{n-1}]a_{n-1}=(a_n+a_{n-1}{)}^2$
而這個剛好右等於

$(a_n+a_{n-1}{)}^2=P_{n-1}^2$。因為不考慮低位元，符合逼近的概念，修正判斷式：

for(i = fls(X);;i>>1){
    ret << 1
    if(X >= P^2){
        ret = (ret+1);
        ...
    }
}

接下來的問題是如何每一輪都不要重複計算

$P^2$，而是可以用上一輪得到的結果，所以觀察此回合

$P_m^2$ 與上一回合

$P_{m+1}^2$ 的關係得出：

$P_m^2-P_{m+1}^2=2P_{m+1}{a}_m+a_m^2$ (而m+1是在m右邊的位元，為了對應到測驗解說更方便)。然而這件事沒有解決問題因為要計算平方

$a_m^2$ 的問題還是存在，雖然可以重複利用上輪的

$P_{m+1}$ 。而此作法需要不斷的計算

$P_m=a_n+a_{n-1}+\cdots +a_m$ 。但在二進制裡面

$a_m=a_{m+1}/2$ ，因此可以利用上一輪得到的

$a_{m+1}^2$ 來得到這一輪的

$a_m^2$。關係式：

$a_m^2=a_{m+1}^2/4$。而這個東西只要在遞迴的時候一開始用 Count Leading Zeros (clz) 找到第一個

$b_m=1$ 即可。

然而這樣又有一個問題，記住了

$a_{m+1}^2$ ，卻沒記住

$a_{m+1}$，因此現在要來思考前面那一項要如何從上一輪得到。回憶之前的想法記住前一輪的

$P_{m+1}^2$ 只要下一輪就再加上

$2P_{m+1}{a}_m+a_m^2$ 得

$P_m^2$。

接下來看前一輪

$P_{m+1}^2-P_{m+2}^2=2P_{m+2}{a}_{m+1}+a_{m+1}^2$ ，因為前面考慮第二項現在關注第一項。

$2P_{m+1}{a}_m=2(P_{m+2}+a_{m+1})(a_{m+1}/2)=P_{m+2}{a}_{m+1}+a_{m+1}^2$　展開後發現

$a_{m+1}^2$，這是剛剛算第二項已經記住的值，達到重複利用。再來看第一項與前一輪第一項的差別，剛好差兩倍。

終於得到通式了：
這一輪第一項寫為　

$c_m$ ，第二項寫為

$d_m$ 。
前一輪第一項寫為　

$c_{m+1}$ ，第二項寫為

$d_{m+1}$ 。

$c_m=c_{m+1}/2+d_{m+1}$

$d_m=d_{m+1}/4$

$P_{m+1}^2-P_{m+2}^2=c_m+d_m$
第一輪先知道

$a_n$ 也就是最大的位元是第幾個再將 1 左移多少。d = 1UL << (31 - __builtin_clz(x)) 知道從哪裡開始後。

接下來迴圈的第一輪找到找

$a_n^2=d$

因爲

$a_n^2=d<=N^2$
已知

$2^k$ 為

$N^2$ 的 Rounding Down to the Next Power of 2 ，得到關係

$2^k<=N^2$
因此初始化

$d$ 的時候，因為

$d=a_n^2=(2^n{)}^2$可以把他變成

$2^k$

而d = 1UL << ((31 - __builtin_clz(x)) & ~1UL)用& ~1UL的用途是把最後一個位元清掉。
先舉例如下：
（一）ｘ = 64 左移量為 6 (偶) ，最後一個位元清掉無效果， d=64
（二）ｘ = 32 原先左移量為 5 (奇) ，最後一個位元清掉左移量為 4 (偶) ，d=16

上面別寫奇數偶數表達。因為迴圈每回合

$d$ 都除4。
用 （二）ｘ = 32 作反例

$d_m=32$

$\to$

$d_m=8$

$\to$

$d_m=2$

$\to$

$d_m=0$ 結束。因為

$d_m=a_m^2$ 很明顯在

$a_m$ 無論在迴圈的哪個回合都無法定義，如果

$a_m$不能被定義，就

$a_m$就不能被

$2^m$。而不能被

$2^m$ 表示的意義相當於 這樣就失去前面演算法二進位 digit by digit 的效果。因為當檢察平方根的值是否大於

$2^m$ ，是在檢查第

$m$ 個位元是否需要被設為 1
也因此我們要先確保左移量為偶數。那為甚麼為了確保的方式，是讓奇數的最後一個位元也就是

$1$被清除（相當於減一）?那為什麼不是加一呢，減一不會讓他少考慮高位元嗎?

這件事情我花了一個晚上寫數學式子想去證明，然而現在卻發現他就是那麼的直覺。雖然沒用，但經過一個晚上使用 Letax 的能力有提升。

上面的問題在於

$2^k$ 的

$k$ 為奇數。那將

$k-1$ 不會少考慮高位元?
先用2a+1當成這個

$k$ 所以改寫成

$2^{2a+1}$ 。
再來繼續把鄰居寫出來

$2^{2a}<2^{2a+1}<2^{2a+2}$ ，接著因為

$2^{2a+1}$ 為

$N^2$ 的 Rounding Down to the Next Power of 2，所以把

$N^2$ 塞入

$2^{2a}<2^{2a+1}<=N^2<2^{2a+2}$ 。接著一起開根號

$2^a<2^{\frac{2a+1}{2}}<=N<2^{a+1}$。完美，平方根的最高位元一定為

$2^a$，不會有沒考慮到

$2^{a+1}$ 也就是第a+1個位元的問題。因此證明減一是對的。接下來就可以到到程式碼的第 2 行的初始化。

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

初始化完代表開始考慮

$a_n^2$ ，而

$c_m=P_{m+1}{2}^{m+1}$ 因為

$P_{n+1}=0$ 因此

$c_n=0$
由於

$x=N^2$每一輪都把當前位元

$a_m^2$ 減掉。剩下只要考慮更低位元。因為

$c+d=P_m^2-P_{m+1}^2$ 。然而在當前位元要考慮的是

$x=N^2$ 是否大於

$P_m^2$ ?然而卻看到是判斷式比較是否大於

$c+d$ 。
那是因為在上一輪

$x$ 已經將

$P_{m+1}^2$ 減掉了。

$x-P_{m+1}^2?P_m^2-P_{m+1}^2$。所以這樣的寫法是對的。 而

$c$ 與

$d$ 在每一輪的變化都寫進去了。

然而因為我重新思考後修正之前的想法，原本以為當

$a_m=0$ 則

$c_{m-1}=P_m{2}^m=(P_{m+1}+a_m)2^m=P_{m+1}{2}^m+a_m{2}^m=c_m/2$，應該修正為

$c_{m-1}=P_m{2}^m=(P_{m+1}+a_m)2^m=P_{m+1}{2}^m+a_m{2}^m=c_m/2=0$。然而看

$c_m$ 與

$d_m$的作用，因為

$d_m$做的是考慮是否

$N$ 包含

$a_m$，如果不包含代表就代表判斷式裡面不執行(第六行)。那下一輪的

$c$ 確實不用

$c+=d$，而(第四行)是因為，在一回合要比較的都會少一個最高位元。

看下一輪的

$c_{m-1}=P_{m+1}{2}^m+a_m{2}^m$ 但這個其實是

$c_{m-1}=2P_{m+1}{2}^{m-1}+a_m{2}^m=2P_{m+1}{a}_{m-1}+a_m{2}^m$
所以當

$a_m=0$

$c_{m-1}=P_m{2}^m=(P_{m+1}+a_m)2^m=2P_{m+1}{2}^{m-1}+a_m{2}^m=2P_{m+1}{a}_{m-1}+a_m{2}^m=c_m/2\ne 0$ 。 其實是在作

$a_{m-1}$ 是在先預先處理下一個位元。

由於只要計算

$P_0=a_n+a_{n-1}+a_{n-2}+...+a_1+a_0$，

$P_0$是最後的答案，所以只要求到

$P_0＝c_{-1}=P_{-1+1}{2}^{-1+1}$。

ffs / fls 取代 __builtin_clz

使程式不依賴 GNU extension，且提供分支和無分支 (branchless) 的實作。

測驗 2

INTEGER DIVISION BY CONSTANTS

測驗 3

測驗 4

測驗 5

---

第四週測驗

測驗 1

v    : b3 b2 b1 b0
v>>1 : b4 b3 b2 b1 
&    :  0  1  1  1
n    :  0 b3 b2 b1
n>>1 : b5  0 b3 b2
&    :  0  0  1  1
n    :  0  0 b3 b2 
n>>1 : b6  0  0 b3
&    :  0  0  0  1
n    :  0  0  0 b3 

因此下面這些數字也有相同效果。但由於運算元的位元都在前面步驟變為 0 。所以寫成 & 0x77777777 不影響結果，此外 & 的常數都為 0x77777777 的優點是較容易記憶其他 population count 的核心概念(右移)。

n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x33333333; 
v -= n;
n = (n >> 1) & 0x11111111;
v -= n;

用範例 input(

$I$) : 4 說明，會計算 hamming distance

$I\times I$ 次，其中有I次是跟自己比較，變為

$I\times I-I=I\times (I-1)$，但是其實要比較的為

$C_2^I=\frac{I\times (I-1)}{2}$，因此再右移一個位元用作除以二。

《Hacker's Delight》和 《CS:APP》第二章

上面的作法用 divide and conquer 先將以每 4 個位元 (nibble) 去計算 1 的數量。
第一個思路:將一串位元，二個位元一組去計算 1 的數量，接著四個位元一組去儲存相加上步驟的兩組的結果，八個位元一組…。

1's turn  1 0 1 1 1 1 0 0 
2's turn  0 1|1 0|1 0|0 0
3's turn  0 0 1 1|0 0 1 0
4's turn  0 0 0 0 0 1 0 1

將第一個思路轉化成程式:

x       1 0 1 1 1 1 0 0  (1's turn)  
& 0x55  0 1 0 1 0 1 0 1
= A     0 0 0 1 0 1 0 0                      
x >> 1  0 1 0 1 1 1 1 0                x      1 0 1 1 1 1 0 0
& 0x55  0 1 0 1 0 1 0 1                & 0xAA 1 0 1 0 1 0 1 0
= B     0 1 0 1 0 1 0 1                       1 0 1 0 1 0 0 0
A + B   0 1|1 0|1 0|1 0  (2's turn)    >> 1   0 1 0 1 0 1 0 0 (B)
& 0x33  0 0 1 1 0 0 1 1
...
% 0x0F  0 0 0 0 1 1 1 1 

右邊使用 (x & 0xAA) >> 1 增加可讀性，書上的說明: 看不懂

《Hacker's Delight》P85
The code avoids generating two large constants in a register. This would cost an instruction if the machine lacks the and not instruction.

x = x - ((x >> 1) & 0x55555555);

x       1 0 1 1 1 1 0 0
x >> 1  0 1 0 1 1 1 1 0
& 0x55  0 1 0 1 0 1 0 1
        0 1 0 1 0 1 0 0
        0 1 1 0 1 0 0 0

因為上面有點難說明操作背後的意義，所以以兩個位元分成4個情況討論

x                    1 1      1 0     0 1
x >> 1               0 1      0 1     0 0
01                   0 1      0 1     0 1 
(( x>>1 ) & 01)      0 1      0 1     0 0
x - (( x>>1 ) & 01)  1 0      0 1

兩個位元能夠出現 1 的數量可能性的結果有 2(10) 與 1(01) 與 0(00)，因此當 x 是 (11) 時，則結果會是 2(10)， x 是 (10)或(01) 時，則結果會是 1(01)， x 是 0(00) 時，則結果會是 0(00)。
(( x>>1 ) & 01) 提取第二個位元的值 (0 或 1)。觀察 x 與結果的值，發現差第二個位元

$b_{2k+1}$ 的值。因此 x - (( x>>1 ) & 01) 得到結果:每二個位元有多少個位元被設為 1 。接著一路將計算出的數量相加。相加的方式則是用平行相加二組。把原先(下方註解內容)修改:

x = x - ((x >> 1) & 0x55555555); // x = (x & 0x55555555) + ((x>>1) & 0x55555555)
x = (x & 0x33333333) + ((x >> 2) & 0x33333333); 
x = (x + (x >> 4)) & 0x0F0F0F0F; // x = (x & 0x0F0F0F0F) + ((x>>4) & 0x0F0F0F0F)
x = x + (x >> 8);
x = x + (x >> 16);
res =  x & 0x0000003F;

4 5 6 行原先的操作是寫作這樣，下面用例子說明:

    x = (x & 0x00FF00FF) + ((x>>8) & 0x00FF00FF);
    x = (x & 0x0000FFFF) + ((x>>16) & 0x0000FFFF);

            0 0 0 0 0 1 0 1|0 0 0 0 0 1 0 0|0 0 0 0 0 1 1 0|0 0 0 0 1 0 0 0
          
原先的操作 : 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1|0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0
修正的操作 : 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1|0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0

原先的操作 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1
修正的操作 : 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1|0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1
&         :       0       0       0       0       0       0       3       F

最後之所以是 0x3F 是因為總共只有 32 個位元。所以用6個位元就可以表示其數量

$[0,32]$ 。到此覺得《Hacker's Delight》真的很好看，我原本只看第二章，而第五章又展現這麼簡單的想法。呼應影片Hamming codes part 2: The one-line implementation 。其中 Hamming 在想出漢明碼的過程中常常想到名言: "Luck favors a prepared mind."。影片作者也說:"Clever ideas often look deceptively simple in hindsight, which makes them easy to underappreciate." 就像上面的程式碼看起來簡單，但不代表不值得花時間去欣賞。讀 《Hacker's Delight》 時看到很多從未有的想法竟是可以被這麼直覺地呈現，然而誕生這個想法的過程卻可能是非常困難曲折的。因此原理只會在頭腦準備好去接受時才會被發現，當還找不到原理時，並不代表原理不存在。

接下來這個要看第 i 個位元

$b_i$的值為 1 還是 0。透過公式 :

$b_i=\lfloor \frac{x}{2^i}\rfloor -2\lfloor \frac{x}{2^{i+1}}\rfloor$，第一項是把

$b_j,j<i$ 的位元都清掉 (作法 : 把

$b_k,k>=i$ 放在

$b_{k-i}$的位置) 。第二項是清掉

$b_i$前面的位元 (作法 : 把

$b_k,k>=i$ 放在

$b_{k-i}$ 的位置後，再把

$b_0$ 變為 0 ) 。所以第一項減第二項是

$b_i$ 的值 (0 或 1)。

$b_3+b_2+b_1+b_0$

$=(\lfloor \frac{x}{2^3}\rfloor -2\lfloor \frac{x}{2^{3+1}}\rfloor )+(\lfloor \frac{x}{2^2}\rfloor -2\lfloor \frac{x}{2^{2+1}}\rfloor )+(\lfloor \frac{x}{2^1}\rfloor -2\lfloor \frac{x}{2^{1+1}}\rfloor )+(\lfloor \frac{x}{2^0}\rfloor -2\lfloor \frac{x}{2^{1+0}}\rfloor )$

$=(\lfloor \frac{x}{2^3}\rfloor -2\lfloor \frac{x}{2^4}\rfloor )+(\lfloor \frac{x}{2^2}\rfloor -2\lfloor \frac{x}{2^3}\rfloor )+(\lfloor \frac{x}{2^1}\rfloor -2\lfloor \frac{x}{2^2}\rfloor )+(\lfloor \frac{x}{2^0}\rfloor -2\lfloor \frac{x}{2^1}\rfloor )$

$=\lfloor \frac{x}{2^0}\rfloor -\lfloor \frac{x}{2^1}\rfloor -\lfloor \frac{x}{2^2}\rfloor -\lfloor \frac{x}{2^3}\rfloor -\lfloor \frac{x}{2^4}\rfloor$
只有 4 個位元時

$\lfloor \frac{x}{16}\rfloor =0$，就等於測驗題的說明 :

$X-\lfloor \frac{x}{2}\rfloor -\lfloor \frac{x}{4}\rfloor -\lfloor \frac{x}{8}\rfloor =b_3+b_2+b_1+b_0$，將其擴展到以十為底 :

$X-9\lfloor \frac{x}{10}\rfloor -9\lfloor \frac{x}{100}\rfloor -\cdots =d_0+d_1+d_2+d_3+\dots$。

將這個公式連接到二個位元的事情。也就是第一輪到第二輪的數學表示。

1's turn  1 0 1 1 1 1 0 0 
2's turn  0 1|1 0|1 0|0 0

二個位元可以想成四進位。

$X-3\lfloor \frac{x}{4}\rfloor -3\lfloor \frac{x}{4^2}\rfloor -\cdots =f_0+f_1+f_2+f_3+\dots$
因此把上面數學式子轉換成

$x=x-3\times (x>>2)=x-3\lfloor \frac{x}{4}\rfloor$ 等同於得到

$f_0$的值。

x    b3  b2 |b1  b0  -> (b3*2+b2)*4 + (b1*2+b0)*1
-)    0  b3  b2   0
-)    0   0  b3  b2

先右移二再乘 3(0x11)，相當於做了(右移一後再減)兩次，因此 sum_digits(x) =

$(b_3\ast 2+b_2)+(b_1\ast 2+b_0)=b_3(2^3-2^2-2^1)+b_2(2^2-2^1-2^0)+b_1(2)+b_0=2b_3+b_2+2b_1+b_0$
擴展成

$x=x-3\times ((x>>2)\mathrm{\&}$ 0x3333333

$)=x-3\lfloor \frac{x}{4}\rfloor$ 是為了平行計算每4個bit。

用上面的概念就可以解釋測驗題的程式碼，sum_digits(x) =

$(b_3+b_2+b_1+b_0)$，也就是二進位

x    b3  b2  b1  b0 |-> (b3)*2^3+(b2)*2^2+(b1)*2+(b0)*1
-)    0  b3  b2  b1
-)    0   0  b3  b2
-)    0   0   0  b3

因此改成做了(右移一後再減)三次。原先覺得 & 0x77777777 與 & 0x33333333 與 & 0x11111111 也可以，但是讀上說明才發現都寫成 & 0x77777777 的優點如下說明:

《Hacker's Delight》 P89
The repeated use of the mask & 0x77777777 permits loading it into a register and referencing it with register-to-register instructions.

讀這本書的時候，原先有很多想法都會在後面被提到並且說明優缺點。像是他說明逐一將最右邊(right-most)的 1 位元清掉(《Hacker's Delight》P23 )，接著寫在迴圈 while(x != 0){ x = x & (x-1);} 計算總共做了幾輪，這樣的操作在 1 比較少的時候會較快，如果 1 很多就用 while(x != -1){x = x | (x+1);} 來將最右邊的 0 設為 1。這樣就因應不同的情況，而不用每次都先平行計算次數再用 divide and conquer 相加結果。

針對 LeetCode 477. Total Hamming Distance 撰寫出更高效的程式碼。

因為 divide and conquer 是將要處理的單元先分成 niddle 為單位在兩兩一組相加原先在單位中計算的整數，因此這已經是平行運算，所以要血更高效的，我首先不會改這裡。我改的地方是:

    v = (v + (v >> 4)) & 0x0F0F0F0F;
    v *= 0x01010101;
    v = v>>24
    return v

因為乘的數字太大了。我把第 2、3 行改成下面這一行。

    v -= 255*((v>>8)+(v>>16)+(v>>24));                    

原理來自公式 :

$X-(N-1)\lfloor \frac{x}{N^1}\rfloor -(N-1)\lfloor \frac{x}{N^2}\rfloor -\cdots =n_0+n_1+n_2+n_3+\dots$，以 N 為底要求 X 每個位數的值。而因為在第 1 行已將將 v 轉換成如下:

v            b7    b6 b5    b4 b3    b2 b1    b0
v>>1          0    b7 b6    b5 b4    b3 b2    b1
&0x0F0F0F0F_________________________
              0 b6+b7  0 b4+b5  0 b2+b3  0 b0+b1

由上面得知是以

$2^8=256$ 進位，每位數用 8 個位元儲存該位數的值，等同拿出

$(b_6+b_7)$

$(b_4+b_5)$

$(b_2+b_3)$

$(b_0+b_1)$。代換公式

$X-255\lfloor \frac{x}{(2^8{)}^1}\rfloor -255\lfloor \frac{x}{(2^8{)}^2}\rfloor -255\lfloor \frac{x}{(2^8{)}^3}\rfloor =n_0+n_1+n_2+n_3$

但這件事情讓我很好奇，為什麼不一開不直接用 2 進位。這樣公式會變成

$X-(2-1)\lfloor \frac{x}{(2{)}^1}\rfloor -(2-1)\lfloor \frac{x}{(2{)}^2}\rfloor -(2-1)\lfloor \frac{x}{(2{)}^3}\rfloor -\cdots -(2-1)\lfloor \frac{x}{(2{)}^{31}}\rfloor =b_0+b_1+b_2+\cdots +b_{32}$。
也就是測驗題的公式這樣程式碼會變成。

    unsigned n = v;
    while(n){
        n >>= 1;
        v -= n;
    }

但這樣效率會變低，代表平行是加快程式效能的關鍵。那接下來做的事情是將程式盡量改成平行的版本。

測驗 2

測驗 3

課程回顧

Linux 核心模組運作原理

xorshift 亂數產生器，

如何測試

ldexpl
fusion operation
x * ( 2^exp )
x & 0x7fff sign 算有號
x = (x >> CCCC)
靜態區域變數 static 其實就是 全域變數。

population count

ECC
BCH

crt
trusted computing base

• Monolithic kernel 與
• Microkernel : kernel 責任沒有很大，第一代的實作效能低。

• sudo insmod hello.ko 變成 linux kernel 不可分割的一部分。
• linux kernel 不是 micro kernel 。
• schedule 兩萬行，密碼學有八萬行。
• super user 會用壞
• initcall
• 以前用陣列存 64 個任務，後來用鏈結串列與紅黑樹
• oobrain

Linux 核心設計: 不只挑選任務的排程器

EEVDF
EAS
Mach microkernel
LTE : long-term evolution (2G -> 3G CDMA 3.999999)
現代作業系統 long-term 。
dynamic frecuency scaling
L4 microkernel
何時會發生 context switch.
process 在 user mode 交換 kernel mode 可能不會 depend implementation
context switch

x86-64 指令集是 AMD 發明。　
IA32 是 intel
IA64 是 intel
x86-64 AMD
x86s 去掉 32

Linux 核心設計: 不僅是個執行單元的 Process

cpumask_t : migration_disabled
多數處理器都是多核。
cpu hotplug: 滑動頁面，最耗　cpu 資源。播放影片 decoder 可以用最少的 cpu 資源。　
NUMA : 傳輸需要時間。 cpu migrate 到其他 cpu 。

ls -lh /sys/devices/system/cpu

孟母是自願 migrate
cpu　頻率會變動， cpu 會 idle。
RCU 同步 lock free 與 semphore 與 mutex 不一樣。
mm 記憶體管理，稀疏問題，要考慮並行，同時效率要高，因為存取頻率太高。
schedule 裡面有一堆 lock 。
ttwu
rt_mutex
C_groupts
brk 系統呼叫 為了相容 Kconfig 可以找到描述用的規範。用git log 只能看2005年之後的東西
mallco calloc 提供給 user space 的競爭。
snmalloc 讓兩個以上的行程去做通訊。
CTSS
jitter 最大延遲 - 最小延遲
work queue

不能被 dereference

#define UNALIGNED(X) ((long) X & (sizeof(long) - 1))
const void * str = (const void char *) str
unsigned char d = c; 

轉型要讓它算術，參數可以接受任意存取，但之後需要轉型。使用者看自己的應用場景去強制轉型，才能去存取最後的物件。
64 bits。
BBBB = mask << i;
long 的寬度跟 word 的寬度是一樣的。
XOR 跟比較字元相通相消。
只要一個byte 是 0 就成立，detect_char 就會成立。
probabiltiy 擴充。
很多架構不能隨意存取地址。沒有對齊過的，不能存取。
RUNNING ready 與 running。