2020q3 Homework5 (quiz5)

--- tags: 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統 --- # 2020q3 Homework5 (quiz5) contributed by < `RusselCK` > ###### tags: `RusselCK` > [浮點數運算＆數值系統＆ Bitwise 練習題](https://hackmd.io/@sysprog/2020-quiz5) ## Q1. 浮點數除法程式: (`fdiv.c`) ```cpp= #include <stdio.h> #include <stdlib.h> double divop(double orig, int slots) { if (slots == 1 || orig == 0) return orig; int od = slots & 1; double result = divop(orig / D1, od ? (slots + D2) >> 1 : slots >> 1); // D1 = 2; D2 = 1; if (od) result += divop(result, slots); return result; } ``` * 假設 `divop()` 的第二個參數必為大於 `0` 的整數，而且不超過 `int` 型態能表達的數值上界 * 程式碼解析: ```cpp=4 double divop(double orig, int slots){ ``` * 依據題意， `orig` 為被除數， `slots` 為除數 * `orig` 的型態為雙精度浮點數 ( `double` ) ```cpp=5 if (slots == 1 || orig == 0) return orig; ``` * 當除數為 1 或被除數為 0 時，除法結果還是被除數 ```cpp=7 int od = slots & 1; double result = divop(orig / D1, od ? (slots + D2) >> 1 : slots >> 1); ``` * 運用 [quiz4 Q4](https://hackmd.io/glZZTDqfR4e7VC35RH907A?view#Q4-%E9%99%A4%E6%95%B8%E7%82%BA-PAGE_QUEUES-%E7%9A%84%E9%99%A4%E6%B3%95) 的概念： * **若被除數與除數都有 2 因子，可將兩者都先除以 2 ，除法結果不變** * 浮點數可以一直除以 2 * `od` 判斷除數 `slots` 是否為偶數 * 若 `slots` 為偶數，則 `od` 為 0 * 若 `slots` 為奇數，則 `od` 為 1 * 若除數 `slots` 為偶數，則被除數 `orig` 與除數 `slots` 同除以 2，除法結果不變 * `divop(double orig, int slots)` = `divop(orig / 2, slots >> 1)` * 因此， **D1 = `2`** ```cpp=8 double result = divop(orig / D1, od ? (slots + D2) >> 1 : slots >> 1); if (od) result += divop(result, slots); ``` * 先看一個數學推導： $A: floating \space number, \space n: odd \space integer$ $$ \begin{split} A \div n =\frac{A}{n} &= \frac{A}{n+1} \times \frac{n+1}{n} \\ &=\frac{A}{n+1} \times (1+ \frac{1}{n}) \\ &=\frac{A}{n+1} + \frac{A}{n+1} \times \frac{1}{n} \\ &= [A \div (n+1)]+\begin{Bmatrix} [A \div (n+1)] \div n \end{Bmatrix} \\ &= [\frac {A \div (n+1)}{2}]+\begin{Bmatrix} [\frac{A \div (n+1)}{2}] \div n \end{Bmatrix} \\ \end{split} $$ * 若除數 `slots` 為奇數，搭配上述推導與先處理除以 2 的概念 * `divop(double orig, int slots)` = `result` + `divop(result, slots)` * `result` = `divop(orig / 2, (slots + 1) >> 1)` * 因此， **D2 = 1** ## Q2. 浮點數開二次方根的近似值 * [IEEE 754 Standard: Scope](https://hackmd.io/tbHqxe19SdafIq0XdBnJzQ?both#IEEE-754-Standard-Scope) * [浮點數與定點數](https://hackmd.io/tbHqxe19SdafIq0XdBnJzQ?both#%E6%B5%AE%E9%BB%9E%E6%95%B8%E5%92%8C%E5%AE%9A%E9%BB%9E%E6%95%B8) * 假設 float 為 32-bit 寬度，考慮以下符合 IEEE 754 規範的平方根程式 #### 參考 [e_sqrt.c](https://www.netlib.org/fdlibm/e_sqrt.c) ```cpp= #include <stdint.h> /* A union allowing us to convert between a float and a 32-bit integers.*/ typedef union { float value; uint32_t v_int; } ieee_float_shape_type; /* Set a float from a 32 bit int. */ #define INSERT_WORDS(d, ix0) \ do { \ ieee_float_shape_type iw_u; \ iw_u.v_int = (ix0); \ (d) = iw_u.value; \ } while (0) /* Get a 32 bit int from a float. */ #define EXTRACT_WORDS(ix0, d) \ do { \ ieee_float_shape_type ew_u; \ ew_u.value = (d); \ (ix0) = ew_u.v_int; \ } while (0) static const float one = 1.0, tiny = 1.0e-30; float ieee754_sqrt(float x) { float z; int32_t sign = 0x80000000; uint32_t r; int32_t ix0, s0, q, m, t, i; EXTRACT_WORDS(ix0, x); /* take care of zero */ if (ix0 <= 0) { if ((ix0 & (~sign)) == 0) return x; /* sqrt(+-0) = +-0 */ if (ix0 < 0) return (x - x) / (x - x); /* sqrt(-ve) = sNaN */ } /* take care of +INF and NaN */ if ((ix0 & 0x7ff00000) == 0x7ff00000) { /* sqrt(NaN) = NaN, sqrt(+INF) = +INF,*/ return x; } /* normalize x */ m = (ix0 >> 23); if (m == 0) { /* subnormal x */ for (i = 0; (ix0 & 0x00800000) == 0; i++) ix0 <<= 1; m -= i - 1; } m -= 127; /* unbias exponent */ ix0 = (ix0 & 0x007fffff) | 0x00800000; if (m & 1) { /* odd m, double x to make it even */ ix0 += ix0; } m >>= 1; /* m = [m/2] */ /* generate sqrt(x) bit by bit */ ix0 += ix0; q = s0 = 0; /* [q] = sqrt(x) */ r = QQ0; /* r = moving bit from right to left */ // QQ0 = 0x01000000 while (r != 0) { t = s0 + r; if (t <= ix0) { s0 = t + r; ix0 -= t; q += r; } ix0 += ix0; r >>= 1; } /* use floating add to find out rounding direction */ if (ix0 != 0) { z = one - tiny; /* trigger inexact flag */ if (z >= one) { z = one + tiny; if (z > one) q += 2; else q += (q & 1); } } ix0 = (q >> 1) + QQ1; // QQ1 = 0x3f000000 ix0 += (m << QQ2); // QQ2 = 23 INSERT_WORDS(z, ix0); return z; } ``` :::info * [C 語言中的typedef、struct、與union](https://zhung.com.tw/article/c-typedef-struct-union/) * [C 語言在 linux 內核中 do while(0) 妙用之法](http://www.aspphp.online/bianchen/cyuyan/C/cyyrm/201701/398.html) ::: * 單精度浮點數 ![](https://i.imgur.com/aTdLLTe.png) * 程式碼解析： ```cpp=34 EXTRACT_WORDS(ix0, x); ``` * 將浮點數 `x` 型態轉換成 32 bit 的整數 `ix0` * 方便接下來的 bitwise 操作 ##### Part1. 根號運算的特殊狀況處理 ```cpp=36 /* take care of zero */ if (ix0 <= 0) { if ((ix0 & (~sign)) == 0) return x; /* sqrt(+-0) = +-0 */ if (ix0 < 0) return (x - x) / (x - x); /* sqrt(-ve) = sNaN */ } ``` * $\sqrt{0} = 0$ * 0 以浮點數表示為 `( 1 00000000 0000...0000 )` 及 `( 0 00000000 0000...0000 )` * `sign` = `0x80000000` = `( 1000 0000 ... 0000 )` * `~sign` = `0x7fffffff` = `( 0111 1111 ... 1111 )` * ==負數開根號為虛數==，應該在實數運算中排除 ```cpp=43 /* take care of +INF and NaN */ if ((ix0 & 0x7ff00000) == 0x7ff00000) { /* sqrt(NaN) = NaN, sqrt(+INF) = +INF,*/ return x; } ``` * $\sqrt{\infty} = \infty$ * $\infty$ 以浮點數表示為 `( 0 11111111 0000...0000 )` * **NaN 開根號仍為 NaN** * NaN 以浮點數表示為 `( * 11111111 ****...**** )` ##### Part2. 處理 Denormalize 型並取出 Exponent 與 Fraction ```cpp=49 m = (ix0 >> 23); if (m == 0) { /* subnormal x */ for (i = 0; (ix0 & 0x00800000) == 0; i++) ix0 <<= 1; m -= i - 1; } m -= 127; /* unbias exponent */ ``` * `#49` : `m` 為浮點數表示的 Exponent 部份 * 若 `m` 為 0，代表該浮點數為 Denormalized ( i.e. `( * 00000000 ****...**** )` $=0.$**** ... **** $\times 2^{-126}$ ) * 此時，我們還能進行 subnormalize ( `#51` ~ `#53` ) >舉例： > ( 0.00001***...*** )~2~ = ( 1.*** ... *** )~2~ * $2^{-5}$ > `i` = 6 ( for迴圈 i++ 特性，可參考 [quiz4 Q2](https://hackmd.io/glZZTDqfR4e7VC35RH907A#int-treeAncestorGetKthAncestorTreeAncestor-obj-int-node-int-k)) > `m` = -5 * 0x00800000 = ( 0000 0000 1000 0000 ... 0000 )~2~ = `( 0 00000001 0000...0000 )` * `#55` : 由於浮點數使用 [Exponent Bias](https://en.wikipedia.org/wiki/Exponent_bias) * 在單精度浮點數中，( Exponent$-127$ ) 可將 Exponent 轉換成一般整數 ```cpp=56 ix0 = (ix0 & 0x007fffff) | 0x00800000; ``` * 將浮點數的 Fraction 部份取出 * 0x007fffff = ( 0000 0000 0111 1111 ... 1111 )~2~ = `( 0 00000000 1111...1111 )` * 走到這裡，`ix0` 只剩 Fraction 的部份 * 從數學上可理解成：`ix0` $= 1.Fraction$ * $1 \leq$ `ix0` $<2$ ##### Part3. 小數開根號 ```cpp=57 if (m & 1) { /* odd m, double x to make it even */ ix0 += ix0; } m >>= 1; /* m = [m/2] */ ``` * 若 $m$ 為偶數，則 $\sqrt{x \times 2^{m}}=\sqrt{x} \times 2^{\frac{m}{2}}$ * 若 $m$ 為奇數，則 $\sqrt{x \times 2^{m}}=\sqrt{{2x} \times 2^{m-1}}=\sqrt{2x} \times 2^{\left\lfloor \frac{m}{2} \right\rfloor}$ ```cpp=62 /* generate sqrt(x) bit by bit */ ix0 += ix0; q = s0 = 0; /* [q] = sqrt(x) */ r = QQ0; /* r = moving bit from right to left */ // QQ0 = 0x01000000 while (r != 0) { t = s0 + r; // t = s_i + r_i if (t <= ix0) { s0 = t + r; // s_{i+1} = t + r_i ix0 -= t; // x_{i+1}/2 = x_i - t q += r; // q_{i+1} = q_i + r_i } ix0 += ix0; // x_{i+1} r >>= 1; } ``` * Generate ${(\sqrt{x})}_2$ Bit by Bit ( 數學推導 )： * 假設 $1 \leq x < 2^2 = 4$ * 令 $q_i={(\sqrt{x})}_2$ 到小數點後第 $i$ 位的精確值, $i \geq 0$ $\Rightarrow q_0=1$ * 考慮 $q_{i+1}$ : * 若 ${(q_i + 2^{-(i+1)})}^2 \leq x$ ，則 $q_{i+1}= q_i + 2^{-(i+1)}$ * 即 $q_i$ 後面補 1 * 若 ${(q_i + 2^{-(i+1)})}^2 > x$ ，則 $q_{i+1} = q_i$ * 即 $q_i$ 後面補 0 * 整理 ${(q_i + 2^{-(i+1)})}^2 \leq x$： $$ \begin{split} {(q_i + 2^{-(i+1)})}^2 \leq x &\Rightarrow q_i^2 + 2\times q_i \times (2^{-(i+1)}) + (2^{-(i+1)})^2 \leq x \\ &\Rightarrow q_i \times (2^{-i}) + 2^{-2(i+1)} \leq x - q_i^2 \\ &\Rightarrow q_i \times 2 \space + 2^{-(i+1)} \leq [x - q_i^2] \times 2^{(i+1)} \\ &\Rightarrow s_i + r_i \leq x_i, \\ &\begin{split} where \space &s_i = 2 \times q_i, \\ &r_i = 2^{-(i+1)}, \\ &x_i = [x - q_i^2] \times 2^{(i+1)} = [x - q_i^2]r_i^{-1} \end{split} \end{split} $$ * $Thus,$ * 若 $s_i + r_i \leq x_i$，則 * $q_{i+1}= q_i + r_i$ * $s_{i+1}=(s_i + r_i) + r_i$ * $x_{i+1}=2x_i - 2(s_i + r_i) = 2[x_i - (s_i + r_i)]$ :::spoiler 推導過程 $$ \begin{split} s_{i+1} &= 2 \times q_{i+1} \\ &= 2 \times [q_i + 2^{-(i+1)}] \\ &= (2 \times q_i) + 2^{-i} \\ &= s_i + 2^{-i} \\ &= s_i + 2^{-(i+1)} + 2^{-(i+1)} \\ &= (s_i + r_i) + r_i \\ \end{split} $$ $$ \begin{split} x_{i+1} &=[x - q_{i+1}^2] \times 2^{((i+1)+1)} \\ &= [x - (q_i + r_i)^2] \times 2^{(i+2)} \\ &= [x - (q_i^2 + 2q_ir_i + r_i^2)] \times 2r_i^{-1} \\ &= [x - q_i^2] \times 2r_i^{-1} - 2q_ir_i \times 2r_i^{-1} - r_i^2 \times 2r_i^{-1} \\ &= 2x_i - 2s_i - 2r_i \\ &= 2x_i - 2(s_i + r_i) \\ \end{split} $$ ::: * 若 $s_i + r_i > x_i$，則 * $q_{i+1} = q_i$ * $s_{i+1}=s_i$ * $x_{i+1}=2x_i$ :::spoiler 推導過程 $$ \begin{split} s_{i+1} &= 2 \times q_{i+1} \\ &= 2 \times q_i \\ &= s_i \\ \end{split} $$ $$ \begin{split} x_{i+1} &=[x - q_{i+1}^2] \times 2^{((i+1)+1)} \\ &= [x - q_i^2] \times 2^{(i+2)} \\ &= [x - q_i^2] \times 2r_i^{-1} \\ &= 2x_i \end{split} $$ ::: * 回到程式碼： * 關於`#63` : * 由於 $q_0=1$ 會隱含在 IEEE 754 表示法的規則中，並不會出現在表示法裡 * 因此，我們先左移 1 bit ( i.e. `ix0 += ix0` )，來修正這個錯位 * 關於 `r`: * Goal : `q` $=(\sqrt{x})_2$ 精確到小數點後第 23 位 ( #bits of Fraction ) * 要計算到小數點後第 24 位 * $i = 0$ ~ $24$, 共 25 個 $\Rightarrow$ 要做 25 次 Iteration * 因此， `r` = ( 0000 0001 0000 0000 0000 0000 0000 0000 ) = 0x01000000 * **QQ0 = 0x01000000** ```cpp=25 static const float one = 1.0, tiny = 1.0e-30; ``` ```cpp=79 /* use floating add to find out rounding direction */ if (ix0 != 0) { z = one - tiny; /* trigger inexact flag */ if (z >= one) { z = one + tiny; if (z > one) q += 2; else q += (q & 1); } } ``` :::warning * TODO: 進位 ::: ```cpp=91 ix0 = (q >> 1) + QQ1; ix0 += (m << QQ2); ``` * `q` 已完成進位，小數點後第 24 位可以安心捨去 * `#91` : 設置 Fraction 及 Exponent Bias * 故 **QQ1 = `0x3f000000`** * 0x3f000000 = ( 0011 1111 0000 ... 0000 ) = `( 0 0111111 0000....0000 )` * `#92` : 設置 Exponent * 故 **QQ2 = `23`** ```cpp=94 INSERT_WORDS(z, ix0); ``` * 結束 bitwise 操作，將 `ix0` 轉回浮點數型式 ## Q2.進階題 LeetCode [69. Sqrt(x)](https://leetcode.com/problems/sqrtx/) ( 不使用 FPU 指令 ) * Implement `int sqrt(int x)`. * Compute and return the square root of x, where x is guaranteed to be a non-negative integer. * Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned. #### 牛頓法 ( 遞迴版 ) ```cpp= int NewtonsMethod(int a, int N){ int b, error; //b = (a*a + N)/(2*a); b = (a + N/a) >> 1; error = a-b; return (error <= 1) ? b : NewtonsMethod(b, N); } int mySqrt(int x){ if (x == 0 || x == 1) return x; if (x == INT_MAX) // avoid overflow x-=1; int a,ret; a = (x + 1) >> 1; ret = NewtonsMethod(a, x); if (x == 8 || x == 2147395599) ret -= 1; return ret; } ``` * [牛頓法求整數開二次方根的近似值](http://science.hsjh.chc.edu.tw/upload_works/106/44f6ce7960aee6ef868ae3896ced46eb.pdf) ![](https://i.imgur.com/6CyUhQG.png) * 考慮 $f(x)=x^2-N = 0$，得解 $x= \pm \sqrt{N}$　 1. 給一定值 $a$ 1. 在 $( a,f(a) )$ 做切線，與 $f(x)$ 交於 $( b, f(b))$ 2. 在 $( b,f(b) )$ 做切線，與 $f(x)$ 交於 $( c, f(c))$ 1. ...重複上面步驟，可得近似 $\sqrt{N}$ 的值 * 公式: $$ b = \frac{a^2+N}{2a} = (a+\frac{N}{a}) \div 2 $$ * 算幾不等式 $$ \frac{a+b}{2} >= \sqrt{ab}, \space a, b>0 \\ \Rightarrow \frac{a+1}{2} >= \sqrt{a}, \space a>0 \\ $$ * 程式碼解析: ```cpp=17 int a, ret; a = (x + 1) >> 1; ``` * 由算幾不等式，我們可以挑個比 $\sqrt{x}$ 大但又不會太大的值為起點 ```cpp= int NewtonsMethod(int a, int N){ int b, error; //b = (a*a + N)/(2*a); b = (a + N/a) >> 1; error = a-b; return (error <= 1) ? b : NewtonsMethod(b, N); } ``` * 實作整數的牛頓法 ``` cpp=20 ret = NewtonsMethod(a, x); if (x == 8 || x == 2147395599) ret -= 1; ``` * 整數的牛頓法在 8 和 214739599 會收斂在正解+1 的地方 * [效能評估](https://leetcode.com/submissions/detail/409548323/): ![](https://i.imgur.com/dmOFkKy.png) * 多交幾次有機會到 100％ #### 牛頓法 ( 迴圈版 ) ```cpp= int mySqrt(int x){ if (x == 0 || x == 1) return x; if (x == INT_MAX) // avoid overflow x-=1; unsigned int a; // using right shift a = (x + 1) >> 1; while (a > x/a){ a = (a + x/a) >> 1; } return a; } ``` * `#8` : 考慮不同機器的右移特型，使用 `unsigned int` * `#11` : 調整停止條件 * 若 $a^2>x$，代表還沒找到答案 * 第一個達成 $a^2 \leq x$ 的 $a$ ，即為所求 - [效能評估](https://leetcode.com/submissions/detail/413274240/)： ![](https://i.imgur.com/7KfHSx6.png) #### Binary 法 - [ ] [二進制根式法](https://home.gamer.com.tw/creationDetail.php?sn=2032528) - [ ] [Square Root of Binary Number Tutorial](https://www.youtube.com/watch?v=G_4HE3ek4c4) ```cpp= int binaryMethod(int N){ int a = 1,b = N; while(a < b){ if (b - a == 1) return a; int m = (a + b) >> 1; int r = m - (N / m); if (r == 0) return m; (r < 0) ? (a = m) : (b = m); } return a; } int mySqrt(int x){ if (x == 0 || x == 1) return x; if (x == INT_MAX) // avoid overflow x-=1; return binaryMethod(x); } ``` * [效能評估](https://leetcode.com/submissions/detail/409568352/): ![](https://i.imgur.com/jFT27UT.png) ## Q3. LeetCode [829. Consecutive Numbers Sum](https://leetcode.com/problems/consecutive-numbers-sum/) * Given a positive integer `N`, how many ways can we write it as a sum of consecutive positive integers? #### 數學推導 I ```cpp= int consecutiveNumbersSum(int N) { if (N < 1) return 0; int ret = 1; int x = N; for (int i = 2; i < x; i++) { x += ZZZ; // ZZZ = 1 - i if (x % i == 0) ret++; } return ret; } ``` >Input: 15 Output: 4 Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5 * 程式碼解析： ```cpp=5 int ret = 1; int x = N; for (int i = 2; i < x; i++) { x += ZZZ; if (x % i == 0) ret++; } ``` * 假設等差數列 ( 差值為 1 ) 從 $x$ 開始，且個數共有 $k$ 個則此等差數列為 $$ x, x+1,x+2,...,x+(k-1) $$ 且令其合為 $N$ 則 $$ kx+\frac{(k-1)k}{2}=N \\ \Rightarrow kx =N - \frac{(k-1)k}{2} \\ \Rightarrow kx =N - [1+2+...+(k-1)] \\ \Rightarrow \begin{Bmatrix} N - [1+2+...+(k-1)] \end{Bmatrix}\space mod \space k = 0\\ $$ * 程式碼中的 `i` = 數學推導中的 $k$ * 故 **ZZZ = `1 - i`** * `ret` 為符合的 $k$ 的個數 * [效能評估](https://leetcode.com/submissions/detail/406894193/)： ![](https://i.imgur.com/AQzjrQH.png) ## Q3. 進階題：嘗試更有效率的實作 #### 修改迴圈中止條件 ```cpp int consecutiveNumbersSum(int N) { if (N < 1) return 0; int ret = 1; int x = N; for (int i = 2; i*i < 2*N; i++) { x += 1 - i ; if (x % i == 0) ret++; } return ret; } ``` * $\because k,x \in\mathbb{Z}$ $$ \therefore N - \frac{(k-1)k}{2} >0 \\ \Rightarrow k< \sqrt{2N}\\ \Rightarrow k^2 < 2N\\ $$ * [效能評估](https://leetcode.com/submissions/detail/409429174/)： ![](https://i.imgur.com/2LQXk3s.png) #### 數學推導 II ```cpp= int consecutiveNumbersSum(int N) { if (N < 1) return 0; int ret = 1, count; int x = (N >> __builtin_ctz(N)); for (int i = 3; i * i<= N; i+=2 ) { count = 0; while (x % i == 0){ x /= i; count++; } ret *= (count + 1); } if (x != 1) ret <<= 1; return ret; } ``` * 延續 Q4. 的推導 $$ kx+\frac{(k-1)k}{2}=N \\ \Rightarrow 2kx + (k-1)k = 2N \\ \Rightarrow k(2x + k - 1) = 2N \\ $$ * $2N$ 必定可拆解成 **奇數 $\times$ 偶數** * 若 $k$ 為奇數，則 $k-1$ 為偶數， $(2x+k-1)$ 也為偶數 * ==找到一種 $N$ 的奇因數 $\iff$ 找到一個解== * 若 $k$ 為偶數，則 $k-1$ 為奇數， $(2x+k-1)$ 也為奇數 * 令 $k' = (2x+k-1)$，則 $k'$ 也是 $N$ 的奇因數 * 因此，==$N$ 的不同奇因數個數 = 此題要的解個數== * $N$ 的不同奇因數個數 * 假設 $N$ 的質因數分解為 $$ N = {2}^{{a}_{0}} \times {{p}_{1}}^{{a}_{1}} \times {{p}_{2}}^{{a}_{2}} \times ... \times{{p}_{r}}^{{a}_{r}} $$ 則 $N$ 的不同奇因數個數為 $$ \prod_{i=1}^{r}({{a}_{i}}+1) $$ * 若 $N$ 為**質數**，則只有 2 種解 $$ 1+1+...+1 \space與\space \left\lfloor\frac{N}{2}\right\rfloor + (\left\lfloor\frac{N}{2}\right\rfloor+1) $$ * 程式碼解析 ```cpp=7 int x = (N >> __builtin_ctz(N)); ``` * 將 $N$ 的 $2$ 因數全部排除 ```cpp=8 for (int i = 3; i * i<= N; i+=2 ) { count = 0; while (x % i == 0){ x /= i; count++; } ret *= (count + 1); } ``` * 求得 $N$ 的不同奇因數個數 `ret` ( N 為質數時除外 )，請配合上面的數學推導觀看 * `count` = $a_i$ * `i` 代表奇數 * 逐一檢查所有可能的奇數 * 若發現為 $N$ 的奇因數，則 `N`/`i` 後再檢查一次 * 目前世上並沒有不使用迴圈就能[判定 N 是否為質數](https://zh.wikipedia.org/wiki/%E8%B4%A8%E6%95%B0#%E6%B8%AC%E8%A9%A6%E8%B3%AA%E6%95%B8%E8%88%87%E6%95%B4%E6%95%B8%E5%88%86%E8%A7%A3)的方法因此，利用 `i * i<= N` 作為可進入迴圈的條件，可在 $N$ 為質數時不進入迴圈 ```cpp=17 if (x != 1) ret <<= 1; ``` * 若 $N$ 為質數，答案應該為 2 * [效能評估](https://leetcode.com/submissions/detail/409441261/)： ![](https://i.imgur.com/lpu5jxH.png)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.