---
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)
:::
* 單精度浮點數
* 程式碼解析：
```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)
* 考慮 $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/):
* 多交幾次有機會到 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/)：
#### 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/):
## 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/)：
## 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/)：
#### 數學推導 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/)：
Sign in with Wallet
Connect another wallet