2022q1 Homework3 (quiz3)

contributed by < YiChainLin >

測驗題目

實驗的 gcc 編譯器版本

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

測驗1

在 Linux 核心原始程式碼，include/linux/bitfield.h 提及一個巨集 GENMASK，其作用是依據給定的範圍，產生連續的 bitmask，例如:

GENMASK(6, 4) 產生 01110000₂
GENMASK(39, 21) 產生 0x000000ffffe00000 (64 位元)

已知我們使用的微處理器架構為 64 位元，且 unsigned long 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 GENMASK 巨集的定義:

#define GENMASK(h, l) \
    (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))

本題要根據示例要的結果是要產生在二進位元中，第 h + 1 (high) 位 ~ 第 l + 1 (low) 位的 1 遮罩
在無號整數下，使用邏輯移位(logical shift) shift 移位補 0 的效果，完成本題
以範例來說我們預期的 bitmask 為:

GENMASK(39, 21):
    0000...00111...111111000...000 (64位元)
             ^          ^
          (第40位)    (第22位)

在 ((~0UL) >> (LEFT)) 敘述中要能產生最高位前面的 0，所以透過邏輯移位補 0 的特性中，要向右 shift 64 - (h + 1)，64 位元是來自於題目的架構，如果是 32 位元的架構則為 31 - h

LEFT = 63 - h

所以對應這個敘述可以產生這樣的結果:

000..00001111111...11111 (64位元) 
         ^
      (第40位)

再來就是要將尾段清零，透過與 0 的 & 計算去除，所以透過向左移位補 0 的特性，可以補 l 個數的 0
所以在 ((~0UL) >> (l) << (RIGHT)) 的敘述中，透過右移補 0 的方式產生，先進行向右移位 l 次，再左移 l次

RIGHT = l

右移 l:                          再左移 l:  
0000....00111...11111 (64位元)   111...1100...00 (64位元)
              ^                         ^ 
        (第 63 - l 位)               (第 l 位)

最後再將 high 的位移結果加入進行 & 運算

    000..000011111111..11111   (64位元)
 &  111..1111111111100...000
 ...........................
    000..000011111110...0000  <-產生 (h + 1) ~ (l + 1)位的 1 bitmask

有一點比較不懂的是在 (~0UL) >> (l) 這段敘述中，為什麼要右移，如果只是想要在尾端補 0 的時候，那只要左移 l 次就可以了
也就是在右半部分只要 (~0UL) << (l) 能達到一樣的效果

測驗2

考慮以下程式碼

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 結構體，並確保第一個成員的地址，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 align_down)。

參考C 語言：記憶體管理、對齊及硬體特性

首先要先了解電腦的 CPU 如何抓取資料，CPU 抓取資料的單位是 4 byte 或是 8 byte (分別為 32 位元與 64 位元的電腦架構)，在處理上才會快速，不會想一個一個 1 byte 抓取
若資料的分布狀況不在 4 byte 的情況下，如下圖，分別抓取藍色的資料與黃色的資料，在透過移位(shift)的方式調整所需要的資料，最後再結合一起
但是這樣的做法比較沒有效率，所以編譯器在分配記憶體時就會做 data alignment 的動作
舉例在 int 的 alignment 方式，int 為 4 byte 、 char 為 1 byte ，理論上加起來要為 5 byte ，但是 char 為了 alignment int，所以會從 1 byte 多加 3 個 byte，變成 8 byte 的形式，所以 CPU 就能因為這樣的倍數關係不會降低抓取資料的速度

struct s1 {
    char c;
    int a;
}

對 4 個位元組向下對齊，因此要將 v 的值處理能被 4 整除的數字，所以在二進位元的表示中，在最後兩位的 bit 要等於 0
所以 3 的二進位元為 00..0011₂ ，在透過取反獲得 11..1100₂ ，再透過 & 運算子可將 v 的最後兩個 bits 變成 00₂
回傳的結構是 struct fd 所以在將型態強制轉型成結構內的型態 struct foo * ，始能將 v 記憶體位址取址

EXP1 = (struct foo *)(v & ~3)

測試:

    long long a = 5;
    struct fd test = to_fd(a);

    printf("alignment : %p %p\n", &test.foo, &test.flags);

結果:

alignment : 0x7fff11a83dd0 0x7fff11a83dd8

可以看到在記憶體的表現上以 8 byte 的空間分配

測驗3

考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 LeetCode 190. Reverse Bits 的描述。

#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;
}

觀察函式中 0xCC 與 0xAA 在 8 位元下的二進位表示分別為 11001100 與 10101010，利用 & 的運算子，可將對應位置的 bit 紀錄，也就是指定相對應的 bit 進行 shift
可得知在交換順序時候為
- 前 4 個與後 4 個 bit 交換
- 再來鄰近每兩個 bit 成對交換
- 最後將鄰近一組的 2 個 bit 互換
所以在左半部分都是對 x 數值向右 shift，可推測右半部分是對 x 數值向左 shift
因此將 0xCC 與 0xAA 的二進位取反:

 0xCC : 11001100
~0xCC : 00110011  /* 0x33 */
 0xAA : 10101010
~0xAA : 01010101  /* 0x55 */

EXP2 = (x & 0x33) << 2
EXP2 = (x & 0x55) << 1

以 x = 0x35 為例，8-bit 二進位為 00110101₂，預期結果為 10101100₂

x = (x >> 4) | (x << 4);

         00000011    (x >> 4)
      |  01010000    (x << 4)
      ...........
         01010011    (4 個 4 個交換)

x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);

        01010011 (x)            01010011 (x)
     &  11001100 (0xCC)      &  00110011 (0x33)
     ...........             ...........
        01000000                00010011
        
         00001000    ((x & 0xCC) >> 2)
      |  01001100    ((x & 0x33) << 2)
      ...........
         01011100    (2 個 2 個交換)

x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);

        01011100 (x)            01011100 (x)
     &  10101010 (0xAA)      &  01010101 (0x55)
     ...........             ...........
        00001000                01010100
        
         00000100    ((x & 0xAA) >> 1)
      |  10101000    ((x & 0x55) << 1)
      ...........
         10101100    (相鄰交換)

測驗4

延伸〈你所不知道的 C 語言：前置處理器應用篇〉，我們嘗試將 foreach 巨集予以擴充，使得支援以下寫法:

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

對應的巨集定義:

#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__})))

可發現巨集 __VA_ARGS__ 主要用於宣告任意的變數在 function 的引數中，方便在宣告時不使用太多不同型態的宣告(可變引數的宣告方式)，在 C99 以後的版本新增的功能

A macro can be declared to accept a variable number of arguments much as a function can. The syntax for defining the macro is similar to that of a function.
來源 : gcc 文件

程式的功能在於要能走訪 foreach_int 函式中的每一個 int 的引數，觀察到函式定義中的 i 即代表每一個引數的變數，所以變數 i 為範例中的 (0, -1, 100, 0, -99)
分析 for 迴圈的初始條件 unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0);
- 拆部分來看 ((i) =((int[]){__VA_ARGS__})[0]) ，前面的 int[] 表示整數的陣列宣告，放入的資料為 __VA_ARGS__ 也就是說將函式的引數值都存入了陣列當中 (0, -1, 100, 0, -99) ，而 [0] 表示陣列第一個位置的元素，以範例來說是 0
- 再來是給定 _foreach_i 變數值為括弧後的 0 ，就好像是宣告了某個變數的過程時，再宣告一個變數，_foreach_i 也不會拿到 i 的值
看到判斷條件 _foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int) 右半部分的內容，計算整個陣列的記憶體長度，除上 int 的長度，也就是計算整個陣列元素的數量，所以就可以觀察到 _foreach_i 的變數用於走訪的次數，會根據傳入引數值的個數
(i) = ((int[]){__VA_ARGS__, 0})[EXP4] 所以根據上述的分析，可以得知 [EXP4] 為整數陣列中元素的位置，需要走訪每一個元素，為持續遞增的變數，因此 EXP4 為 ++_foreach_i ，所以觀察 foreach_ptr 函式功能也相似，所以 EXP5 也為 ++_foreach_i

EXP4 = ++_foreach_i;
EXP5 = ++_foreach_i;
一開始想法比較簡單，會選擇 _foreach_i++，但是經時跑過程式後發現會是錯誤的，原因是在下一次的迴圈時，變數 i 比 _foreach_i++ 早賦值，因此再第一次迴圈的時候會重複 (i) = ((int[]){__VA_ARGS__, 0})[0] 的結果，將第一個引數重複走訪兩次

測試 _foreach_i++ 結果:

i is 0
i is 0
i is -1
i is 100
i is 0

利用 typeof() 取得引數的變數型態並宣告一個陣列存取

參考 gcc 文件解釋

Another way to refer to the type of an expression is with typeof. The syntax of using of this keyword looks like sizeof, but the construct acts semantically like a type name defined with typedef.

對於 const char * 處理方式透過 void * 可以彈性處理傳入的型態，可用於指向不同型態的變數，有暫存的效果，可以再還原
void * 參考文章
範例:

int a = 10;
void *void_ptr = &a;
printf("%d\n", *(int *)void_ptr); /* 結果為 10 */

使用 assert() 函式，用來檢驗敘述的正確性，在本範例中要檢驗每個資料的是否存在
assert() 參考文章

#define _foreach_no_nullval(i, p, arr) \
    assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))

若 p (元素)為 NULL 且 i 的數量少於陣列元素的個數，所以為了確保函式能順利走訪每一個資料
當 assert 情況產生，出現以下的訊息:

main: Assertion `(_foreach_i) >= sizeof(((const void *[]){"Hello", "world"})) / sizeof(((const void *[]){"Hello", "world"})[0])' failed.

測驗5

針對 LeetCode 29. Divide Two Integers，以下是可能的實作:
































#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;
}

在兩整數二進位的除法中也可以利用長除法的觀念下去執行，如圖
先看到 4 ~ 15 行中分別處理被除數與除數的正負號問題，在執行上將兩個未知的整數都先取正數，使用的方式是利用二補數的行為取正，先取反 ~ 再 +1
再來看到 17 ~ 19 行中根據長除法的方式，除數要先從被除數最前端的位元開始進行，所以利用迴圈的方式檢查被除數與除數相差的位元位數

應該不用使用到迴圈進行位元數的判斷，可以使用 ctz 類的相關函式進行修改

另外，若除數為零的情況下，在 17 ~ 19 行的敘述中會進入無窮迴圈，為本題的缺陷之處

EXP6 = dvs << shift

看到 22 ~ 27 行，首先看到第一層的迴圈，用於判斷被除數在大於除數時能持續進行，所以 EXP7 會與這個判斷式有關，對於被除數或是除數的增減有影響
再來看到第二層的迴圈，在每一輪的除法中判斷是否可以進行相減的情況(換言之就是商數可以填入 1 的時候)，若不行則退一位( shift-- )，確保每一輪的減法是大減小的情況
利用 res 儲存商的結果，觀察到 (unsigned int) 1 << shift 就是由第二層迴圈判斷的結果，將商數儲存，利用 | 運算子根據 shift 移位的結果將該輪可進行一次減法的 1 存下
也就是說在 EXP7 中為每一輪除法的減法敘述，因此 EXP7 為

EXP7 = dvd -= dvs << shift

最後看到 28 ~ 29 行的敘述，因為使用 unsigned int 儲存結果，因此要避免 overflow 的問題產生，所以把特例的情況將結果固定為 int 的最大數值結果

例外的情況為當除數為 -1 或 1 的情況就會有這種狀況的發生，能讓 res 的最左邊第一個位置(對於有號整數來說是正負號的判斷位元)的位元為除數 -1 或 1

測驗7

考慮 ilog32 函式可針對給定的 32 位元無號數，計算扣除開頭的 0，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:

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 bit 位元前扣除掉不必要的 0 位元，所需要能表現該數的有效位元數量
分為 4 個階段判斷:
- 判斷數字是否為 16 位元以上的數值 (0xFFFFU = 111..11₂)，大於則將判別的結果 1 儲存 16 的結果，也就是 1 << 4 = 10000₂ = 16₁₀
- 將 v 檢查完後 16 位元後就可以移除 v >>= m ，進行下一階段 8 個位元的檢查
- 以此類推在這 4 個階段的檢查，每一次都是對半檢查

前 3 個階段分別的 bitmask為
0xFFFF = 1111111111111111
0xFF = 11111111
0xF = 1111

所以 EXP10 為 11 的 bitmask ，轉為 16 進制 = 0x3U

EXP10 = (v > 0x3U) << 1

剩下還有最後一位 bit 的檢查，用要將 ret 結果的最後一個 bit 確認 1 的與否，與前面的檢查方式類似，只不過要濃縮成一句，要達成兩件事情:
1. 檢查最後 1 的 bitmask
2. 將結果填入 1 或 0
根據前面的檢查方式可以變成以下兩句:
1. m = (v > 0x1U) << 0;
2. ret += m;

流程上需要 v >> m; 用於下一階段的檢查，但已是最後一次的判斷所以不用再移位

將兩句結合，0x1U = 1₂ ,<< 0 沒有實質作用所以刪除，再將 ret 結果補上 1 或 0 剛好為判斷式的結果，因此

EXP11 = ret += v > 1

測驗9

考慮以下進行記憶體地址對齊 (alignment) 的巨集:

/* 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))

題目解析:巨集功能要能把傳入引數進行 alignment 的動作，將 1 ~ 16 的數值，都改為 16₁₀ 也就是 10000₂最後的 4 個 bit 要為 0，若傳入 0 則要回傳 0
而後 4 個位元的的數值為 1₁₀ ~ 15₁₀ (0001₂ ~ 1111₂)，但這不是我們要的，因此要把它清零，所以要產生 0000 的 0 bitmask，所以可以推測 ~(NNN) 為相關作法
NNN 產生 0000₂ 的方法為對 1111₂(15₁₀) 取反，如何找出 15 這個數字，就是由 16 - 1 得來

如果要產生 000 的 bitmask 也可以利用 8₁₀ -> 1000₂，再 - 1 為 0111，最後取反得到 1000

NNN = MAX_ALIGNMENT - 1

獲得 0 的 bitmask 後就可以用 & 計算子清零，理解後就可以觀察到前面的敘述: ((x) + MAX_ALIGNMENT - MMM) ， x + MAX_ALIGNMENT 將 x 加上不影響的最後 4 個位元的數值(保留第 5 位元 16 的值)再搭配清零的動作就可以得到 16 的數值
那假設傳入的是 0 代表要把加入的 16 清除，才能回傳 0，所以 MMM 就是在處理 0 的特例情況，要把 10000₂ 降一位透過 -1 的方式進行(可得到 01111₂)

MMM = 1

x 傳入 1 ~ 15 範圍的值

以 8 bits 表現
       x                     00000110   
       MAX_ALIGNMENT         00010000
       x + MAX_ALIGNMENT     00010110
                                ^
                        (保留 alignment 值)
       MAX_ALIGNMENT - 1     00001111  取反 `~` -> 11110000
       
       00010011    x + MAX_ALIGNMENT - 1 (-1不影響結果)
    &  11110000    ~(MAX_ALIGNMENT - 1)
    ...........
       00010000    <- 16 的結果

x 傳入 0

以 8 bits 表現
       x                     00000000   
       MAX_ALIGNMENT         00010000
       x + MAX_ALIGNMENT     00010000

       MAX_ALIGNMENT - 1     00001111  取反 `~` -> 11110000
       
       00001111    x + MAX_ALIGNMENT - 1 (-1 將最高位降一位)
    &  11110000    ~(MAX_ALIGNMENT - 1)
    ...........
       00000000    <- 0 的結果

測驗10

考慮以下巨集可得到二個表示式進行整數除法操作時，最接近的整數值:

#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

看到前三個敘述的判斷條件，分別為:

((typeof(x)) -1) > 0
((typeof(divisor)) -1) > 0
(((__x) > 0) == ((__d) > 0))
前兩項為:將傳入 x 、 divisor 的型態轉型到 -1 上，分兩種情況為有號數與無號數，這個判斷式就是要確保在計算的時候皆為無號數，所以透過 -1 的強制轉型判斷

    unsigned int a;
    int b;
    printf("result : %d\n", ((typeof(a)) -1) > 0);
    printf("result : %d\n", ((typeof(b)) -1) > 0);

結果為:

result : 1
result : 0

而第三項的判斷式，也是確保傳入的兩數皆為正數的情況下進行計算

再來看到除法的取最接近整數的運算方式， / 在運行的方式為無條件捨去小數的形式，所以要透過對結果有四捨五入的結果產生，所以要對 / 結果 + - 除數的一半數值，也就是說要將被除數捨棄掉的數值進行處理
- 若是捨棄掉除數的一半以上則需要加上除數的 0.5 進位
- 若是捨棄掉除數的一半以下則需要扣除除數的 0.5

RRR = (__x) + ((__d) >> 1)
SSS = (__x) - ((__d) >> 1)

測驗11

考慮以下計算整數開平方根的實作:

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))

首先看到 fls() (find the last bit set)函式的作用，目的是要找到一數在二進位中由最低位至到最高位的 1 的位置，檢查的方式為產生 1 的 bitmask 在不同位置檢查，檢查的順序為 32 位元、 48 位元、 56 位元、 60 位元、 62 位元、 63 位元，遞增的順序為 +16 +8 +4 +2 +1，以 4₁₀ (100₂) 為例

第一層:
        num = 63
        1111...1100...000  (~0ul << 32) 前 32 個位元為 1
     &                100 
     ....................
        00000000000000000   num = 63 - 32 = 31

第二層: (看前 32 個位元)
        num = 31
        1111...11000...000 (~0ul << 48) 
      &                100 ( 4 << 32)
      ....................
        0000...0000...000   num = 31 - 16 = 15
        
第三層: (看前 16 個位元)
        num = 15
        1111111100000000 (~0ul << 56) 
      &              100 ( 4 << 16)
      ..................
        0000000000000000   num = 15 - 8 = 7
        
第四層: (看前 16 個位元)
        num = 7
        1111000000000000 (~0ul << 60) 
      &      10000000000 ( 4 << 8)
      ..................
        0000000000000000   num = 7 - 4 = 3      
        
第五層: (看前 16 個位元)
        num = 3
        1100000000000000 (~0ul << 62) 
      &  100000000000000 ( 4 << 4)
      ..................
        0100000000000000  結果不為 0, num = 3   
第六層: (看前 16 個位元)
        num = 3
        1000000000000000 (~0ul << 62) 
      &  100000000000000 
      ..................
        0000000000000000  num = 3 - 1 = 2   

4 = 0100 
最高位 1 為第 2 個位元位置 (第一個位置是第 0 位)

m 透過 fls() ，找出數字的最高位元位置，目的為了找出小於該數值最大二進位中完全平方數，(例如: 1, 4, 16, 64)，用 & ~1UL 將 fls() 的最低位數去除
參考平方根的算法1、平方根的算法2

首先一個數可假設

N^{2} = (a_{n} + . . . a_{0})^{2}

而在二進位中可將每一項的

a

表示為

a_{m} = 2^{m}

或是

a_{n} = 0

可由二進位的數值進行逼近，對

2^{m}

進行迭代，假設為:

P_{m} = a_{n} + a_{n - 1} + . . . + a_{m}

m+1為迭代的下一位

決定

a_{m} = 2^{m}

或是

a_{n} = 0

，假設

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

若

N^{2} \geq P_{m}^{2}

，則表示

a_{m} = 2^{m}

(表示

a_{m}

存在於平方數中)，若無則

a_{m} = 0

根據上式則為

P_{m} = P_{m + 1}

，而為防止迭代停止的狀況，則為更新目標數字的數值為

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

，持續更新數值為:

X_{m} = X_{m + 1} - Y_{m}

，其中

Y_{m} = P_{m}^{2} - P_{m + 1}^{2} = 2 P_{m + 1} a_{m} + a_{m}^{2}

(由式 1 平方結果而來)

分別表示:

c_{m} = 2 P_{m + 1} a_{m}, d_{m} = a_{m}^{2}

又因

a_{m} = 2^{m}

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

可得在 m-1 時:

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

所以當

a_{m} = 2^{m}, c_{m} / 2 + d_{m}

,而

a_{m} = 0, c_{m} / 2

，

d_{m - 1} = d_{m} / 4

根據上述的計算方式就可以發現對應題目中的變數

$c_{m} = y$
$d_{m} = m$

對應程式為:

每次的迭代都需要
$c_{m} / 2$
$d_{m - 1} = d_{m} / 4$

XXX = y >>= 1
ZZZ = m >>= 2

所以當平方數在 x 存在則需要扣除，因此:

YYY = x -= b

2022q1 Homework3 (quiz3)

測驗1

測驗2

測驗3

測驗4

測驗5

測驗7

測驗9

測驗10

測驗11

Read more

2022q1 Homework6 (ktcp)

2022q1 Homework 5 (quiz8)

2022q1 Homework2 (quiz2)

2022q1 Homework1 (lab0)