庫存管理

庫存管理

學習練習

簡介

整數

二進位表示法

整數是一種抽象概念,用來表示沒有小數部分的數,例如 4、-2、0 或 64532。

若要用一串位元組來表示整數,就得使用二進位表示法。 在這種表示法中,序列裡的每個位元各代表 2 的一個次方,而且位元的索引從右往左遞增時,所代表的值也跟著變大。

無號數

如果一個數只能是非負數,就稱為無號數。

無號數會直接表示成序列中所有設為 1 的位元所對應的 2 的次方總和。

在一個暫存器中,可表示的無號整數範圍從 0(沒有位元被設定)到 2⁶⁴ - 1(64 個位元全部設定的總和)。

要把無號數擴展到更大的長度,做法是把所有高位都填上 0,這樣新增的位元就不會影響到值。 這叫做零擴充。

指令movzx(z代表零)會把 8 位元或 16 位元的來源運算元零擴充到更大的目的運算元。 至於 32 位元的來源運算元,只要用單純的mov,就一定會零擴充到目的運算元的全部 64 位元。

有號數

如果一個整數可以是正數或負數,就稱為有號數。

為了表示負數,x86-64 使用二補數表示法。

在二補數中,有號數同樣表示成設定位元所對應的 2 的次方總和。 不過,如果最高位被設定,它就會被減掉,而不是加到其他位元上。

由於這個位元所對應的值比其餘所有位元的總和還大,實務上這表示只要這個位元被設定,這個數就一定是負數。 這個特別的位元叫做符號位元。

要把有號數擴展到更大的長度,就是把每個新增的高位都填上符號位元的複本,藉此保留原有的值。 這叫做符號擴充。

指令movsx(s代表符號)會把 8 位元或 16 位元的來源運算元符號擴充到更大的目的運算元。 movsx有個變體叫做movsxd,功能相同,只是把 32 位元的來源運算元擴充到 64 位元的目的運算元。

指令neg可以用來改變一個數的正負號。

Caution

在組合語言中,沒有辦法分辨一串位元組代表的是有號數還是無號數。 要為這些位元組賦予意義,是程式設計師的責任。

善用註解會對這項工作很有幫助。

立即值

在先前的概念中提過,像 4 或 -15 這樣的常數可以直接當成許多指令的來源運算元。 這類數字稱為立即值。

立即值並不存在暫存器或記憶體中,而是直接編碼在指令裡面。 在大多數指令中,無論目的運算元有多大,為它保留的空間都只有 32 位元寬。

當目的運算元是 64 位元寬時,這 32 位元會被_符號擴充_,以填滿整個運算元。 運算元的上半部會完全填滿立即值最高位的複本,因此只有落在_32 位元有號整數_範圍內的數才能這樣寫:

add rax, -1          ; the immediate is sign-extended, so all 64 bits of rax are affected
add rax, 2147483647  ; the largest immediate an instruction like this accepts

超出這個範圍的數就無法當成立即值使用。 這條規則的例外是mov:當目的運算元是暫存器時,它可以接受完整的 64 位元立即值。 如果需要 64 位元的立即值,可以先用mov把它載入暫存器,再使用該暫存器:

mov rax, 3435973837           ; this works, mov can take a 64-bit immediate
mov rdx, 18446744073709551615 ; the largest immediate mov accepts
sub rdx, rax

注意,負的立即值和位元表示相同的無號數是等價的,組譯出來的結果完全相同:

mov rax, -1                   ; rax = 18446744073709551615
mov rax, 18446744073709551615 ; rax = -1

加法

兩個數相加可以用add指令來計算。

另外還有一個單運算元的inc指令,會把運算元中的值加 1:

inc rax ; rax = rax + 1

兩個整數相加時,無論是有號數還是無號數,運作方式都相同。

減法

兩個整數相減使用sub指令。

另外還有一個單運算元的dec指令,會把運算元中的值減 1:

dec rax ; rax = rax - 1

兩個整數相減同樣不論有號或無號,運作方式都相同。

乘法

在 x86-64 中,有兩種不同的指令可以用來做兩個數的乘法。 一般來說,無號乘法使用mul指令,有號乘法則使用imul。

mul指令採用下列的單運算元形式,其中src是來源運算元:

mul src

imul指令可以採用單運算元、雙運算元或三運算元形式:

imul src
imul dest, src
imul dest, src1, src2
單運算元乘法

單運算元形式的乘法會隱含使用兩個暫存器:rax和rdx。 如果相乘的是兩個 64 位元的數,結果的低 64 位元會放在rax,高 64 位元會放在rdx。

這通常寫成rdx:rax,表示兩個暫存器是搭配使用的:

mul rcx ; rax = lower 64 bits of rax * rcx
        ; rdx = upper 64 bits of rax * rcx

其他運算元大小也是同樣的情形。 舉例來說,如果相乘的是兩個 32 位元的數,就會使用eax和edx。

例外是兩個位元組相乘的情況。

這種情況下不會用dl:al,而是使用ax。 ax的低半部(al)會取得乘積的低 8 位元,高半部(ah)則取得高 8 位元。

Caution

乘法中隱含使用的暫存器(例如rax和rdx)一定會被覆寫。 如果之後還會用到這些暫存器裡的值,應該在運算前先把它們存起來。

雙運算元乘法

imul的雙運算元形式有一個明確的目的運算元,並遵循一般的語法。 它不會用到rdx。 取而代之的是,結果會被截斷以配合目的運算元的大小。

imul r8, r9 ; r8 = lower 64 bits of r8 * r9
三運算元乘法

imul的三運算元形式有兩個來源運算元,其中第二個一定是立即值(常數)。 兩個來源運算元會相乘,結果經過截斷後放進目的運算元:

imul r8, r9, 100 ; r8 = lower 64 bits of r9 * 100

注意,目的運算元並不參與乘法。 它只是接收結果而已。

處理溢位

雙運算元和三運算元乘法都會截斷結果,以配合目的運算元的大小。 單運算元乘法會保留完整的範圍,但結果通常會拆成兩個暫存器rdx和rax。

因此,有時先在乘法前把運算元擴展,讓完整的乘積能放進單一暫存器,會很有用。 無號運算元會做零擴充,有號運算元則做符號擴充:

movzx eax, di ; di and si hold unsigned 16-bit numbers
movzx ecx, si
mul ecx       ; the 32-bit product fits in eax, and edx is cleared

除法

和乘法一樣,除法也有兩種指令可以對兩個數做除法。 無號除法使用div指令,有號除法則使用idiv。

這兩個指令都只接受一個運算元:

div src
idiv src

16 位元、32 位元和 64 位元的除法分別使用dx:ax、edx:eax和rdx:rax當作被除數。 在這些情況下,兩個暫存器會搭配產生一個 2N 位元的值,其中 N 是運算的大小(16 位元、32 位元或 64 位元)。 這個值再除以來源運算元。 商會寫入ax、eax或rax,餘數則寫入dx、edx或rdx,取決於運算的大小。

位元組之間的除法比較特別:它不使用dl:al,而是使用ax。 ax的低 8 位元(al)會取得運算的商,高 8 位元(ah)則取得餘數。

注意,除法之前應該先適當設定被除數中的所有位元。 rdx中任何被設定的位元(8 位元除法時則是ah)都會影響到被除的值。

在無號除法中,如果被除的值可以放進低半部,就應該把高半部清除。 任何能清除這些位元的指令都可以。 例如在 32 位元除法中,mov edx, 0會清除高位的位元。

在有號除法中,則應該把值做符號擴充。 有些指令可以自動完成這個過程:cbw、cwd、cdq和cqo。 第一個會根據al的正負號設定ah中的位元。 其餘的分別把ax符號擴充到dx、把eax擴充到edx、把rax擴充到rdx。

Caution

除法中隱含使用的暫存器(例如rax和rdx)一定會被覆寫。 如果之後還會用到這些暫存器裡的值,應該在除法前先把它們存起來。

說明

一間本地商店正要把庫存搬到更大的倉庫。 你受雇來打包並搬運所有東西。

你有四項任務,全都和搬運管理有關。

Note

以下是這個概念中提到的指令:

指令 說明
add a, b a = a + b
inc a a = a + 1
sub a, b a = a - b
dec a a = a - 1
imul a rdx:rax = a * rax(有號)
imul a, b a = a * b(有號,截斷)
imul a, b, c a = b * c(有號,截斷)
mul a rdx:rax = a * rax(無號)
div a rax = rdx:rax / a 的商,rdx = 餘數(無號)
idiv a rax = rdx:rax / a 的商,rdx = 餘數(有號)
movzx a, b a = b,並在多出來的位元補 0
movsx a, b a = b,若 b < 0 則在多出來的位元補 1,否則補 0
Note

請記得,只要改變運算元的名稱,就能用不同大小存取同一個暫存器。 例如:rax(64 位元)、eax(32 位元)、ax(16 位元)、al(8 位元)。

完整的表格可以參考上一個概念。

1. 取得每個箱子的重量

物品正被裝進箱子,而箱子必須標示重量。 附近沒有磅秤,但幸運的是,你知道每件物品的平均重量。

為了方便整理,一個箱子只裝兩種不同產品的物品。

定義一個函式get_box_weight,回傳一個箱子的總重量,單位為g。 這個函式的參數依序為:

  • 箱子中第一種產品的物品數量
  • 第一種產品每件物品的重量,單位為g
  • 箱子中第二種產品的物品數量
  • 第二種產品每件物品的重量,單位為g

假設空箱重500 g。 常數WEIGHT_OF_EMPTY_BOX定義在解答檔案的開頭。

範例:

get_box_weight(30, 40, 50, 20);
// => 2700

所有引數都是 16 位元非負整數,回傳值則是 32 位元非負整數。

2. 計算卡車能裝下多少個箱子

箱子被堆疊起來,用卡車搬到新倉庫。 不過,卡車裡的垂直空間有限。

定義一個函式max_number_of_boxes,回傳在卡車內可以垂直堆放(一個疊在另一個上面)多少個特定高度的箱子。

這個函式的參數是箱子的高度,單位為cm。 假設卡車內部高度為300 cm。 常數TRUCK_HEIGHT定義在解答檔案的開頭。

範例:

max_number_of_boxes(30);
// => 10

引數和回傳值都是 8 位元非負整數。 箱子高度至少為2,所以結果可以放進 8 位元。

3. 檢查是否所有產品都已清點

新倉庫裡有一份清單,記錄每種產品尚未清點的物品數量。 每搬一個新箱子過去,你就要為箱子裡的每種產品算出清單上的新數值。

定義一個函式items_to_be_moved,回傳某項產品還剩下多少物品要搬到新倉庫。 這個函式的參數依序為:

  • 某項產品尚未清點的物品數量
  • 箱子中該產品的物品數量

範例:

items_to_be_moved(76532, 120);
// => 76412

這些引數是 32 位元非負整數。 回傳值是 32 位元整數。 如果過程中發生錯誤,結果有可能是負數。

4. 領取報酬

你的報酬取決於搬了多少個箱子,以及總共跑了幾趟卡車。 每搬一個箱子可獲得5 美元,每跑一趟可獲得220 美元。 常數PAY_PER_BOX和PAY_PER_TRUCK_TRIP定義在解答檔案的開頭。

請注意,你可能已經先預領了一部分報酬來支付初期成本,而這筆預付款要從最終報酬中扣除。 此外,有些產品沒有保險,如果這些物品有損壞或遺失,你的報酬也會按這些物品的價值扣減。 如果不小心的話,你最後可能會倒欠一筆錢喔!

也就是說,你應得或積欠的淨額是:

net = boxes * PAY_PER_BOX + trips * PAY_PER_TRUCK_TRIP - up_front - broken_items * item_value

這筆報酬,或債務,會由你和幾位你雇用的工人平分。 剩下的錢,或剩下的債務,都歸你。 例如,如果淨額是100,由6個人(你和5位工人)平分,你會拿到20(100/(5 + 1) = 16,再加上剩下的4)。

定義一個函式calculate_payment,回傳你最後應該領取或支付的金額。 這個函式的參數依序為:

  • 你已經預領的金額,為 64 位元非負整數
  • 搬運的箱子總數,為 32 位元非負整數
  • 卡車跑的趟數,為 32 位元非負整數
  • 損壞或遺失的物品數量,為 32 位元非負整數
  • 每件遺失物品的價值,為 64 位元非負整數
  • 要和你平分報酬或債務的工人數量,為 8 位元正整數

範例:

calculate_payment(2000, 1000, 5, 21, 2, 1);
// => 2029

回傳值是 64 位元整數。

透過 GitHub 編輯 連結會在新視窗或分頁中開啟
x86-64 Assembly Exercism

準備好開始 庫存管理 了嗎?

註冊 Exercism,透過 22 個概念130 個練習 和真人引導來學習並精通 x86-64 Assembly,全部免費。