# 2022q1 Homework3 (quiz3)
contributed by < `Tcc0403` >
[作業需求](https://hackmd.io/@sysprog/BJJMuNRlq)
[測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3)
## 測驗 1
### 題目
在 Linux 核心原始程式碼，[include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 提及一個巨集 GENMASK，其作用是依據給定的範圍，產生連續的 bitmask，例如:
* `GENMASK(6, 4)` 產生 011100002
* `GENMASK(39, 21)` 產生 0x000000ffffe00000 (64 位元)
已知我們使用的微處理器架構為 64 位元，且 `unsigned long` 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 `GENMASK` 巨集的定義:
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
請補完，使其行為符合預期。作答規範:
1. `LEFT` 和 `RIGHT` 應以最簡潔的形式撰寫，且符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範 (近似 Linux 核心程式碼排版風格)
2. `LEFT` 和 `RIGHT` 皆為表示式，可能包含常數
3. `LEFT` 和 `RIGHT` 皆不該包含小括號 (即 `(` 和 `)`)
### 作答
觀察 bitmask 的產生方式為將兩個 `~0UL` (即 64 位元皆為 1)進行相應的位移操作後，做 `AND` 操作，因此我們可以推斷位移操作的目的是將範圍外的位元變為 0 ，以下計算前後兩項所需清除的位元:
+ `(~0UL) >> (LEFT)`: 該項為右移，目的為清除範圍外的高位元，最高位元是第 `63` 位元，因此需要清除 `63-h` 個位元，故 `LEFT` = `63-h`
+ `(~0UL) >> (l) << (RIGHT)`: 該項為左移，目的為清除範圍外的低位元，最低位元是第 `0` 位元，因此需要清除 `l - 0` = `l` 個位元，故 `RIGHT` = `l`
\begin{align}
(\sim{0\text{UL}})>>(63-h) &= \overbrace{0\cdots0}^{63-h}\overbrace{1\cdots1}^{h+1}\\
(\sim{0\text{UL}})>>(l)<<(l) &= \overbrace{0\cdots0}^{l}\underbrace{1\cdots1}_{64-2l}\overbrace{0\cdots0}^{l}
\end{align}
\begin{array}{rrr}
&\overbrace{0\ \cdots\ 0}^{63-h}\overbrace{1\ \ \ \ \ \cdots\ \ \ 1}^{h+1} &\\
\cdot &\overbrace{0\cdots0}^{l}\overbrace{1\cdots1}^{64-2l}\overbrace{0\cdots0}^{l} &\\ \hline
\text{GENMASK(h, l)}\ = &\overbrace{0\cdots0}^{63-h}1\cdots1\overbrace{0\cdots0}^{l} &
\end{array}
:::warning
其中 `(~0UL) >> (l) << (RIGHT)` 的部分不太清楚為甚麼需要先右移再左移，範圍外的高位元應該在前一項就已經排除了，這邊的右移操作不知道有甚麼考量
:::
答案 :
+ `LEFT` = `63-h`
+ `RIGHT` = `l`
## 測驗 2
### 題目
考慮以下程式碼:
```c
struct foo;
struct fd {
struct foo *foo;
unsigned int flags;
};
enum {
FOO_DEFAULT = 0,
FOO_ACTION,
FOO_UNLOCK,
} FOO_FLAGS;
static inline struct fd to_fd(unsigned long v)
{
return (struct fd){EXP1, v & 3};
}
```
函式 fo_fd 接受指定的地址 v，填入一個 fd 結構體，並確保第一個成員的地址得以依據[〈你所不知道的 C 語言：記憶體管理、對齊及硬體特性〉](https://hackmd.io/@sysprog/c-memory)描述，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 [align_down](https://www.boost.org/doc/libs/1_78_0/doc/html/align/reference.html#align.reference.functions.align_down))。其中 struct foo; 運用[〈你所不知道的 C 語言：指標篇〉](https://hackmd.io/@sysprog/c-pointer)提及的 forward declaration 技巧，可在實作階段才提供具體 struct foo 的定義。
請補完，使其行為符合預期。作答規範:
1. `EXP1` 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
2. `EXP1` 不得使用 `%` (modulo) 運算子
3. 當變數和常數進行運算時，變數應該出現前於常數，例如 `v | 1`
### 作答
依題目所要求， `v` 向下對齊到能被 4 整除的地址上，將 `v` 的 bit 0 跟 bit 1 清除便是 4 的倍數，使用位元遮罩來保留 bit 0, 1 以外的位元，即 `v & ~3`。
接著透過 `(struct foo *)` 轉型成 `foo` 結構體的指標存取該地址
答案:
+ `EXP1` = `(struct foo *)(v & ~3)`
## 測驗 3
### 題目
考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 LeetCode [190. Reverse Bits](https://leetcode.com/problems/reverse-bits/) 的描述。
```c
#include <stdint.h>
uint8_t rev8(uint8_t x)
{
x = (x >> 4) | (x << 4);
x = ((x & 0xCC) >> 2) | (EXP2);
x = ((x & 0xAA) >> 1) | (EXP3);
return x;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP2` 和 `EXP3` 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
2. 當變數和常數進行運算時，變數應該出現前於常數，例如 `v | 1`
### 作答
觀察題目，得知該程式碼逐步交換位元，步驟如下:
+ 第一次交換: 將 4 位高位元與 4 位低位元交換，使用位移操作剛好可以將位元移至目標位置
```graphviz
digraph A{
subgraph iter{
original
[shape=none label=<
<table cellspacing="0" border="0">
<tr>
<td border="1" bgcolor="grey">7</td>
<td border="1" bgcolor="grey">6</td>
<td port="port0" border="1" bgcolor="grey">5</td>
<td border="1" bgcolor="grey">4</td>
<td border="1" bgcolor="white">3</td>
<td border="1" bgcolor="white">2</td>
<td port="port1" border="1" bgcolor="white">1</td>
<td border="1" bgcolor="white">0</td>
</tr>
</table>
>]
swap
[shape=none label=<
<table cellspacing="0" border="0">
<tr>
<td border="1" bgcolor="white">3</td>
<td border="1" bgcolor="white">2</td>
<td port="port2" border="1" bgcolor="white">1</td>
<td border="1" bgcolor="white">0</td>
<td border="1" bgcolor="grey">7</td>
<td border="1" bgcolor="grey">6</td>
<td port="port3" border="1" bgcolor="grey">5</td>
<td border="1" bgcolor="grey">4</td>
</tr>
</table>
>]
original:port0->swap:port3
original:port1->swap:port2
}
}
}
```
+ 第二次交換: 2 bits 為一組，相鄰組別兩兩交換，`(x & 0xCC)` 為圖中灰色的位元，剩餘的白色位元即為 `(x & ~0xCC)`=`(x & 0x33)`，對應的位移操作為左移 2 位。 `EXP2` = `(x & 0x33) << 2`
```graphviz
digraph A{
subgraph iter{
original
[shape=none label=<
<table cellspacing="0" border="0">
<tr>
<td border="1" bgcolor="grey">3</td>
<td port="port0" border="1" bgcolor="grey">2</td>
<td border="1" bgcolor="white">1</td>
<td port="port1" border="1" bgcolor="white">0</td>
<td border="1" bgcolor="grey">7</td>
<td port="port2" border="1" bgcolor="grey">6</td>
<td port="port1" border="1" bgcolor="white">5</td>
<td port="port3" border="1" bgcolor="white">4</td>
</tr>
</table>
>]
swap
[shape=none label=<
<table cellspacing="0" border="0">
<tr>
<td border="1" bgcolor="white">1</td>
<td port="port4" border="1" bgcolor="white">0</td>
<td border="1" bgcolor="grey">3</td>
<td port="port5" border="1" bgcolor="grey">2</td>
<td border="1" bgcolor="white">5</td>
<td port="port6" border="1" bgcolor="white">4</td>
<td border="1" bgcolor="grey">7</td>
<td port="port7" border="1" bgcolor="grey">6</td>
</tr>
</table>
>]
}
original:port0->swap:port5
original:port1->swap:port4
original:port2->swap:port7
original:port3->swap:port6
}
}
```
+ 第三次交換: 1 bit 為一組，相鄰組別兩兩交換，`(x & 0xAA)` 為圖中灰色的位元，剩餘的白色位元即為 `(x & ~0xAA)`=`(x & 0x55)`，對應的位移操作為左移 1 位。 `EXP3` = `(x & 0x55) << 1`
```graphviz
digraph A{
subgraph iter{
original
[shape=none label=<
<table cellspacing="0" border="0">
<tr>
<td port="port0" border="1" bgcolor="grey">1</td>
<td port="port1" border="1" bgcolor="white">0</td>
<td port="port2" border="1" bgcolor="grey">3</td>
<td port="port3" border="1" bgcolor="white">2</td>
<td port="port4" border="1" bgcolor="grey">5</td>
<td port="port5" border="1" bgcolor="white">4</td>
<td port="port6" border="1" bgcolor="grey">7</td>
<td port="port7" border="1" bgcolor="white">6</td>
</tr>
</table>
>]
swap
[shape=none label=<
<table cellspacing="0" border="0">
<tr>
<td port="port8" border="1" bgcolor="white">0</td>
<td port="port9" border="1" bgcolor="grey">1</td>
<td port="port10" border="1" bgcolor="white">2</td>
<td port="port11" border="1" bgcolor="grey">3</td>
<td port="port12" border="1" bgcolor="white">4</td>
<td port="port13" border="1" bgcolor="grey">5</td>
<td port="port14" border="1" bgcolor="white">6</td>
<td port="port15" border="1" bgcolor="grey">7</td>
</tr>
</table>
>]
}
original:port0->swap:port9
original:port1->swap:port8
original:port2->swap:port11
original:port3->swap:port10
original:port4->swap:port13
original:port5->swap:port12
original:port6->swap:port15
original:port7->swap:port14
}
}
```
答案 :
+ `EXP2` = `(x & 0x33) << 2`
+ `EXP3` = `(x & 0x55) << 1`
## 測驗 4
### 題目
延伸 [〈你所不知道的 C 語言：前置處理器應用篇〉](https://hackmd.io/@sysprog/c-preprocessor)，我們嘗試將 foreach 巨集 予以擴充，使得支援以下寫法:
```c
int i;
foreach_int(i, 0, -1, 100, 0, -99) {
printf("i is %i\n", i);
}
const char *p;
foreach_ptr(p, "Hello", "world") {
printf("p is %s\n", p);
}
```
預期輸出如下:
```
i is 0
i is -1
i is 100
i is 0
i is -99
p is Hello
p is world
```
對應的巨集定義:
```c
#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))
#define foreach_int(i, ...) \
for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int); \
(i) = ((int[]){__VA_ARGS__, 0})[EXP4])
#define foreach_ptr(i, ...) \
for (unsigned _foreach_i = \
(((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
(i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__, \
NULL})[EXP5], \
_foreach_no_nullval(_foreach_i, i, \
((const void *[]){__VA_ARGS__})))
```
請補完，使其行為符合預期。作答規範:
1. `EXP4` 和 `EXP5` 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
2. 不該出現小括號 (即 ( 和 ))
### 作答
題目中 `foreach` 的功能為走訪第一個除外的所有參數，並將其值指派給第一個參數
在 `foreach_int` 巨集中，分析 `for (clause-1; exp-2; exp-3)` 陳述句中的三個部分:
+ `clause-1` : 初始化 `i` 和 `_foreach_i`
+ `exp-2` : 判斷 `_foreach_i` 是否超過可走訪大小
+ `exp-3` : 更新 `i` 和 `_foreach_i`
我們需要補上更新的部分， `i` 需要更新為下一個參數， `(int[]){__VA_ARGS__, 0}` 是將欲走訪之參數視作陣列，透過 array subscript 存取下一個元素，利用 `++_foreach_i` ，同時更新 `_for_each_i`。故 `EXP4` = `++_foreach_i`，`__VA_ARGS__` 後面補上 `0` 可以避免因前置遞增運算子而存取到錯誤的記憶體空間
`foreach_iptr` 巨集中與 `foreach_int` 類似，走訪各個字串，其中 `_foreach_no_nullval` 巨集的功能為檢查空字串。 `EXP5` 的功能與 `EXP4` 相同，皆是在走訪下一個元素的同時更新作為索引值的變數
答案 :
+ `EXP4` = `++_foreach_i`
+ `EXP5` = `++_foreach_i`
## 測驗 5
### 題目
針對 LeetCode [29. Divide Two Integers](https://leetcode.com/problems/divide-two-integers/)，以下是可能的實作:
```c
#include <limits.h>
int divide(int dividend, int divisor)
{
int signal = 1;
unsigned int dvd = dividend;
if (dividend < 0) {
signal *= -1;
dvd = ~dvd + 1;
}
unsigned int dvs = divisor;
if (divisor < 0) {
signal *= -1;
dvs = ~dvs + 1;
}
int shift = 0;
while (dvd > (EXP6))
shift++;
unsigned int res = 0;
while (dvd >= dvs) {
while (dvd < (dvs << shift))
shift--;
res |= (unsigned int) 1 << shift;
EXP7;
}
if (signal == 1 && res >= INT_MAX)
return INT_MAX;
return res * signal;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP6` 和 `EXP7` 應以最簡潔的 C99 形式撰寫，符合[作業一](https://hackmd.io/@sysprog/linux2022-lab0)排版規範，且不該觸發編譯器警告訊息
2. 不該出現小括號 (即 ( 和 ))
### 作答
先觀察 `EXP6` 所在迴圈的功用，推測為計算除數對齊被除數所需要的最大位移量，當位移後的除數大於被除數便跳出迴圈，故 `EXP6` = `dvs << shift`
再來觀察 `EXP7` 所在迴圈的功用，推測為計算商數
```c=
while (dvd >= dvs) {
while (dvd < (dvs << shift))
shift--;
res |= (unsigned int) 1 << shift;
EXP7;
}
```
+ 第 2 ~ 3 行 : 調整除數的位移量，找出能使被除數減去位移後的除數的對應位移量
+ 第 4 行 : 將 `1` 填入商數中相對應的位元
+ 第 5 行 : 這邊需要更新被除數，為被除數與位移後的除數兩者之差，故 `EXP7` = `dvd -= dvs << shift`
`EXP6` = `dvs << shift`
`EXP7` = `dvd -= dvs << shift`
## 測驗 6
### 題目
針對 LeetCode [149. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)，以下是可能的實作:
```c
#include <stdbool.h>
#include "list.h"
struct Point {
int x, y;
};
struct point_node {
int p1, p2;
struct list_head link;
};
static bool can_insert(struct list_head *head, int p1, int p2)
{
struct point_node *pn;
list_for_each_entry (pn, head, link)
return EXP8;
return true;
}
static int gcd(int x, int y)
{
while (y) {
int tmp = y;
y = x % y;
x = tmp;
}
return x;
}
static int maxPoints(struct Point *points, int pointsSize)
{
if (pointsSize <= 2)
return pointsSize;
int i, j, slope_size = pointsSize * pointsSize / 2 + 133;
int *dup_cnts = malloc(pointsSize * sizeof(int));
int *hori_cnts = malloc(pointsSize * sizeof(int));
int *vert_cnts = malloc(pointsSize * sizeof(int));
int *slope_cnts = malloc(slope_size * sizeof(int));
memset(hori_cnts, 0, pointsSize * sizeof(int));
memset(vert_cnts, 0, pointsSize * sizeof(int));
memset(slope_cnts, 0, slope_size * sizeof(int));
for (i = 0; i < pointsSize; i++)
dup_cnts[i] = 1;
struct list_head *heads = malloc(slope_size * sizeof(*heads));
for (i = 0; i < slope_size; i++)
INIT_LIST_HEAD(&heads[i]);
for (i = 0; i < pointsSize; i++) {
for (j = i + 1; j < pointsSize; j++) {
if (points[i].x == points[j].x)
hori_cnts[i]++, hori_cnts[j]++;
if (points[i].y == points[j].y)
vert_cnts[i]++, vert_cnts[j]++;
if (points[i].x == points[j].x && points[i].y == points[j].y)
dup_cnts[i]++, dup_cnts[j]++;
if (points[i].x != points[j].x && points[i].y != points[j].y) {
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
int tmp = gcd(dx, dy);
dx /= tmp;
dy /= tmp;
int hash = dx * dy - 1333 * (dx + dy);
if (hash < 0)
hash = -hash;
hash %= slope_size;
if (can_insert(&heads[hash], i, j)) {
struct point_node *pn = malloc(sizeof(*pn));
pn->p1 = i;
pn->p2 = j;
EXP9;
}
}
}
}
for (i = 0; i < slope_size; i++) {
int index = -1;
struct point_node *pn;
list_for_each_entry (pn, &heads[i], link) {
index = pn->p1;
slope_cnts[i]++;
}
if (index >= 0)
slope_cnts[i] += dup_cnts[index];
}
int max_num = 0;
for (i = 0; i < pointsSize; i++) {
if (hori_cnts[i] + 1 > max_num)
max_num = hori_cnts[i] + 1;
if (vert_cnts[i] + 1 > max_num)
max_num = vert_cnts[i] + 1;
}
for (i = 0; i < slope_size; i++) {
if (slope_cnts[i] > max_num)
max_num = slope_cnts[i];
}
return max_num;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP8` 和 `EXP9` 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
2. `EXP8` 不該出現小括號 (即 `(` 和 `)`)
3. `EXP9` 為包含 `list_` 開頭巨集的單一敘述
### 作答
根據 `EXP8` 所在的函式名稱，猜測該函式的功能為判斷座標 (p1, p2) 是否符合某種條件，可以插入該位置的鏈結串列，觀察尋找呼叫該函式的程式碼段落，判斷此條件為
## 測驗 7
### 題目
考慮 `ilog32` 函式可針對給定的 32 位元無號數，計算扣除開頭的 0，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:
```c
int ilog32(uint32_t v)
{
int ret = v > 0;
int m = (v > 0xFFFFU) << 4;
v >>= m;
ret |= m;
m = (v > 0xFFU) << 3;
v >>= m;
ret |= m;
m = (v > 0xFU) << 2;
v >>= m;
ret |= m;
m = EXP10;
v >>= m;
ret |= m;
EXP11;
return ret;
}
```
請補完，使其行為符合預期。作答規範:
1. `EXP10` 和 `EXP11` 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息
2. `EXP11` 不該出現小括號 (即 ( 和 ))
3. `EXP10` 和 `EXP11` 皆包含 > 運算子
## 測驗 8
### 題目
考慮以下 C++ 二元搜尋樹的程式:
:::spoiler 原本程式碼
```c
typedef struct tnode *tree;
struct tnode {
int data;
tnode *left;
tnode *right;
tnode(int d)
{
data = d;
left = right = 0;
}
};
void remove_data(tree &t, int d)
{
tnode *p = t;
tnode *q;
while (p != 0 && p->data != d) {
if (d < p->data) {
q = p;
p = p->left;
} else {
q = p;
p = p->right;
}
}
if (p != 0) {
if (p->left == 0)
if (p == t)
t = p->right;
else if (p == q->left)
q->left = p->right;
else
q->right = p->right;
else if (p->right == 0)
if (p == t)
t = p->left;
else if (p == q->left)
q->left = p->left;
else
q->right = p->left;
else {
tnode *r = p->right;
while (r->left) {
q = r;
r = r->left;
}
p->data = r->data;
if (r == p->right)
p->right = r->right;
else
q->left = r->right;
p = r;
}
delete p;
}
}
```
:::
函式 `remove_data` 嘗試將指定的資料，自給定的二元搜尋樹移除，但原本的 `remove_data` 過於冗長，於是我們可善用 indirect pointer 改寫為以下:
```c
void remove_data(tree &t, int d)
{
tnode **p = &t;
while (*p != 0 && (*p)->data != d) {
if (d < (*p)->data)
EXP12;
else
EXP13;
}
tnode *q = *p;
if (!q)
return;
if (!q->left)
*p = q->right;
else if (!q->right)
*p = q->left;
else {
tnode **r = &q->right;
while ((*r)->left)
r = EXP14;
q->data = (*r)->data;
q = *r;
*r = q->right;
}
delete q;
}
```
請補完，使其行為符合預期。作答規範:
`EXP12`, `EXP13` 和 `EXP14` 應以最簡潔的 C99 形式撰寫，符合作業一排版規範，且不該觸發編譯器警告訊息，並善用 indirect pointer 的技巧來撰寫
`EXP12`, `EXP13` 和 `EXP14` 皆不該出現 ;
## 測驗 9
### 題目
考慮以下進行記憶體地址對齊 (alignment) 的巨集:
```c
/* maximum alignment needed for any type on this platform, rounded up to a
power of two */
#define MAX_ALIGNMENT 16
/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
(((x) + MAX_ALIGNMENT - MMM) & ~(NNN))
```
作用是向上對齊 (roundup)，請補完程式碼，使其行為符合預期。作答規範:
* `MMM` 是常數
* `NNN` 是表示式
* `MMM` 和 `NNN` 皆不得出現小括號 (即 ( 和 ))
* 符合作業一的排版和程式碼風格規範
* 以符合 C99 的最精簡形式撰寫
## 測驗 10
### 題目
考慮以下巨集可得到二個表示式進行整數除法操作時，最接近的整數值:
```c
#define DIVIDE_ROUND_CLOSEST(x, divisor) \
({ \
typeof(x) __x = x; \
typeof(divisor) __d = divisor; \
(((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
(((__x) > 0) == ((__d) > 0))) \
? ((RRR) / (__d)) \
: ((SSS) / (__d)); \
})
```
注意: 當除數 (即 divisor) 為負值時，行為沒有定義。
參考執行結果:
* `DIVIDE_ROUND_CLOSEST(7, 3) = 2`
* `DIVIDE_ROUND_CLOSEST(6, 3) = 2`
* `DIVIDE_ROUND_CLOSEST(5, 3) = 2`
作答規範:
* 符合作[業一](https://hackmd.io/@sysprog/linux2022-lab0)的排版和程式碼風格規範
* `RRR` 和 `SSS` 為表示式，且都包含 `(__x)` 和 `(__d)` (注意小括號)
* `RRR` 和 `SSS` 限用 `+`, `-`, `>>`, `<<` 這幾個運算子，可搭配小括號，並以符合 C99 的最精簡形式撰寫
* 變數在 `RRR` 和 `SSS` 出現的順序 (從左到右)，必定是 `__x` 先於 `__d`
* 請補完程式碼，使其行為符合預期。
## 測驗 11
### 題目
考慮以下計算整數開平方根的實作:
```c
static inline unsigned long fls(unsigned long word)
{
int num = 64 - 1;
if (!(word & (~0ul << 32))) {
num -= 32;
word <<= 32;
}
if (!(word & (~0ul << (64 - 16)))) {
num -= 16;
word <<= 16;
}
if (!(word & (~0ul << (64 - 8)))) {
num -= 8;
word <<= 8;
}
if (!(word & (~0ul << (64 - 4)))) {
num -= 4;
word <<= 4;
}
if (!(word & (~0ul << (64 - 2)))) {
num -= 2;
word <<= 2;
}
if (!(word & (~0ul << (64 - 1))))
num -= 1;
return num;
}
unsigned long i_sqrt(unsigned long x)
{
unsigned long b, m, y = 0;
if (x <= 1)
return x;
m = 1UL << (fls(x) & ~1UL);
while (m) {
b = y + m;
XXX;
if (x >= b) {
YYY;
y += m;
}
ZZZ;
}
return y;
}
```
`i_sqrt` 函式的作用等同於 `floor(sqrt(x))`
作答規範:
* 符合作業一的排版和程式碼風格規範
* `XXX`, `YYY` 和 `ZZZ` 都是敘述，不得呼叫任何函式，且不包含 ; 字元
* 只能使用 `=`, `+=`, `-=`, `>>=`, `<<=` 等運算子，且不得出現小括號 (即 ( 和 ))
* 以符合 C99 的最精簡形式撰寫
Sign in with Wallet
Connect another wallet