為什麼天真的寫法會壞掉？ 最自然的想法：沿用無窮繪圖迴圈，加一個變數 pattern，「c 有被按著就翻轉 pattern」。問題出在速度的鴻溝： 繪圖迴圈每秒跑上百圈，而一次按鍵平均持續約 75 ms——大約 \(1/13\) 秒。一次按鍵期間迴圈跑了幾十圈， pattern 就被翻轉了幾十次， 最後停在哪個值形同擲硬幣。

對症下藥：位準觸發 vs. 邊緣觸發。 這正是課程第一部分（第三、四週）講過的對比： 輪詢按鍵時，我們常常不想在「鍵正被按著」 （位準）時觸發，而想在「自上次檢查以來鍵 被按下了」（邊緣）時觸發—— 一圈輪詢迴圈就類比一個時脈週期。 解法是第四週升緣偵測器的軟體版： 用變數 prev 記住「上一圈 c 是否按著」， 只有 \(\textit{現在按著} \land \lnot\textit{剛才按著}\) （升緣！）才翻轉：

// checker3.asm -- 每「按一次」c 就切換棋盤
// pattern = 目前圖樣的起始字組（0x5555 或 0xAAAA）
// prev    = 上一圈 c 是否按著（軟體版升緣偵測）
    @21845
    D=A
    @pattern
    M=D            // pattern = 0x5555（左上黑）
    @prev
    M=0
(MAIN)
// 升緣偵測：只有「現在按著且剛才沒按」才翻轉
    @KBD
    D=M
    @99
    D=D-A
    @NOTC
    D;JNE          // 現在沒按 c
    @prev
    D=M
    @DRAW
    D;JNE          // 按著但上一圈也按著 → 不翻轉
    @prev
    M=1            // 記住「已按下」
    @pattern
    M=!M           // 翻轉圖樣（升緣！）
    @DRAW
    0;JMP
(NOTC)
    @prev
    M=0            // 放開了 → 重新武裝
(DRAW)
// 以下與 checker2 相同：畫整幅棋盤
    @pattern
    D=M
    @val
    M=D
    @SCREEN
    D=A
    @addr
    M=D
    @row
    M=0
(ROWLOOP)
    @k
    M=0
(WORDLOOP)
    @val
    D=M
    @addr
    A=M
    M=D
    @addr
    M=M+1
    @k
    MD=M+1
    @32
    D=D-A
    @WORDLOOP
    D;JLT
    @val
    M=!M
    @row
    MD=M+1
    @256
    D=D-A
    @ROWLOOP
    D;JLT
    @MAIN
    0;JMP

對照第四週：prev 就是 Mealy 版 one-shot 的那顆 D 正反器（\(S_{new}=in\)）， 翻轉條件 \(in \land \lnot S\) 就是 \(rise\)。 硬體裡用正反器擋住位準，軟體裡用一個變數—— 同一個思想，兩層抽象。

核心：左移一次 \(=\) 自加一次，重複 RAM[1] 次。 優化：移 16 位以上時每一位都被推出字組外， 結果必為 0——直接寫 0，免跑迴圈 （\(\texttt{RAM[1]}\) 可能大到 32767，不優化會空轉三萬圈）。

// leftshift.asm -- RAM[2] = RAM[0] << RAM[1]
    @R0
    D=M
    @R2
    M=D            // 結果從 RAM[0] 出發
    @R1
    D=M
    @n
    M=D
// 優化：n >= 16 → 全部位都移出 → 結果 0
    @16
    D=D-A
    @ZERO
    D;JGE
(LOOP)
    @n
    D=M
    @END
    D;JLE          // 移完了
    @R2
    D=M
    M=D+M          // R2 = 2 * R2（左移一位！）
    @n
    M=M-1
    @LOOP
    0;JMP
(ZERO)
    @R2
    M=0
(END)
    @END
    0;JMP

注意 M=M+M 不是合法的 comp—— 必須先 D=M 再 M=D+M。 測試：0x0001\(\ll\)4 \(= 16\)； 0xFFFF\(\ll\)1 \(=\) 0xFFFE ✓ （負數照樣正確：自加對位圖案一視同仁）。

左旋一位 \(=\) 左移一位，再把掉出去的舊最高位 從最低位補回來。判斷舊最高位：MSB 是符號位—— \(x < 0 \Leftrightarrow\) MSB \(= 1\)！ 而左移後的 LSB 必為 0，所以「補 1」用 \(+1\) 就行： \[\mathrm{rotl}(x) = \begin{cases} x + x, & x \ge 0 \\ x + x + 1, & x < 0 \end{cases}\]

// leftrotate.asm -- RAM[2] = RAM[0] 左旋 RAM[1] 位
    @R0
    D=M
    @R2
    M=D
    @R1
    D=M
    @n
    M=D
(LOOP)
    @n
    D=M
    @END
    D;JLE
    @R2
    D=M            // D = 舊值（符號位 = 舊 MSB）
    @NEG
    D;JLT
    @R2
    M=D+M          // MSB=0：純加倍
    @DEC
    0;JMP
(NEG)
    @R2
    M=D+M          // MSB=1：加倍……
    @R2
    M=M+1          // ……再把舊 MSB 補進 LSB
(DEC)
    @n
    M=M-1
    @LOOP
    0;JMP
(END)
    @END
    0;JMP

驗證題目範例：1010111000011011 左旋一位 \(\to\) 舊 MSB \(=1\)，加倍得 0101110000110110， \(+1\) 得 0101110000110111 ✓。

手環比喻看穿一切：旋轉 16 次回到原點，所以 \[\text{右旋 } k \text{ 位} \;=\; \text{左旋 } (16-k) \text{ 位}.\] 對左旋程式的「小改動」就一行：迴圈計數器從 \(\texttt{RAM[1]}\) 改成 \(16 - \texttt{RAM[1]}\)。

// rightrotate.asm -- 右旋 k 位 = 左旋 16-k 位
    @R0
    D=M
    @R2
    M=D
    @16
    D=A
    @R1
    D=D-M          // D = 16 - k
    @n
    M=D
// 以下與 leftrotate 的迴圈一字不差
(LOOP)
    @n
    D=M
    @END
    D;JLE
    @R2
    D=M
    @NEG
    D;JLT
    @R2
    M=D+M
    @DEC
    0;JMP
(NEG)
    @R2
    M=D+M
    @R2
    M=M+1
(DEC)
    @n
    M=M-1
    @LOOP
    0;JMP
(END)
    @END
    0;JMP

邊界檢查：\(k=0 \to\) 左旋 16 位 \(=\) 原值 ✓ （多跑 16 圈但結果正確）；\(k=15 \to\) 左旋 1 位 ✓。 驗證範例：1111111001111111 右旋一位： 舊 LSB \(=1\) 補到 MSB \(\to\) 1111111100111111 ✓。

右旋之後，把「繞回來」的位擦掉就是右移。 右旋 \(k\) 位後，原本的低 \(k\) 位繞到了字組頂端—— 邏輯右移要求那裡是 0，所以拿遮罩把高 \(k\) 位清零： \[x \gg k \;=\; \mathrm{rotr}(x, k) \,\land\, \bigl(2^{\,16-k} - 1\bigr)\] （\(2^{16-k}-1\) = 低 \(16-k\) 位全 1。） 妙處：旋轉圈數與遮罩的冪次都是 \(16-k\)—— 在同一個迴圈裡順便把 \(p = 2^{16-k}\) 累乘出來， 最後 \(mask = p - 1\)。\(k=0\) 時 \(p\) 自加 16 次溢位成 0， \(mask = -1 = \texttt{0xFFFF}\)，恰好是「不遮」✓。

// rightshift.asm -- 邏輯右移 = 右旋 + 清高位
    @R0
    D=M
    @R2
    M=D
    @16
    D=A
    @R1
    D=D-M          // D = 16 - k
    @n
    M=D
    @p
    M=1            // p 將累積成 2^(16-k)
(LOOP)
    @n
    D=M
    @DONE
    D;JLE
    @p
    D=M
    M=D+M          // p 翻倍（與旋轉同步）
    @R2
    D=M
    @NEG
    D;JLT
    @R2
    M=D+M
    @DEC
    0;JMP
(NEG)
    @R2
    M=D+M
    @R2
    M=M+1
(DEC)
    @n
    M=M-1
    @LOOP
    0;JMP
(DONE)
    @p
    D=M-1          // mask = p - 1 = 低 16-k 位全 1
    @R2
    M=D&M          // 擦掉繞回來的高 k 位
(END)
    @END
    0;JMP

驗證範例：1111111001111111 右移 1： 右旋 1 得 1111111100111111， 遮罩 \(2^{15}-1\) 清掉 MSB \(\to\) 0111111100111111 ✓。

行業註腳（題目原話）：左右移是最常用的位元運算 之一，硬體實作又便宜，所以幾乎所有 CPU 都有移位指令—— Hack 沒有，純粹是為了讓 ALU 保持簡單。

把數學規則翻成 Hack 的三塊拼圖：

• 奇偶判斷：\(x \mathbin{\&} 1\) （第一部分的遮罩！）；

• \(3x+1\)：沒有乘法指令，但 \(3x + 1 = x + x + x + 1\)——A 停在 @x 上 連做三次記憶體運算即可；

• \(x/2\)：\(x\) 是正偶數， 右移一位 \(=\) 右旋一位 \(=\) 左旋 15 位 （LSB 是 0，不會有位繞進 MSB，結果保持正數 ✓）。 這就是提示說的「右移比天真做法快」： 天真除法（迴圈減 2 計數）是 \(O(x)\)—— \(x=30000\) 時要一萬五千圈； 左旋 15 位固定 15 圈，快上千倍。

// collatz.asm -- 從 RAM[0] 迭代到 1，
//                軌跡寫入 RAM[32], RAM[33], ...
    @R0
    D=M
    @x
    M=D
    @32
    D=A
    @ptr
    M=D            // 輸出指標
(STORE)
// RAM[ptr++] = x（間接定址）
    @x
    D=M
    @ptr
    A=M
    M=D
    @ptr
    M=M+1
// x == 1 → 結束
    @x
    D=M-1
    @END
    D;JEQ
// 奇偶：x & 1
    @x
    D=M
    @1
    D=D&A
    @EVEN
    D;JEQ
// 奇數：x = 3x + 1（A 停在 x 上連續運算）
    @x
    D=M
    M=D+M          // 2x
    M=D+M          // 3x
    M=M+1          // 3x + 1
    @STORE
    0;JMP
(EVEN)
// 偶數：x >>= 1，用左旋 15 位實作
    @15
    D=A
    @r
    M=D
(ROT)
    @x
    D=M
    @RNEG
    D;JLT
    @x
    M=D+M          // MSB=0：加倍
    @RNEXT
    0;JMP
(RNEG)
    @x
    M=D+M          // MSB=1：加倍後補 LSB
    @x
    M=M+1
(RNEXT)
    @r
    MD=M-1
    @ROT
    D;JGT
    @STORE
    0;JMP
(END)
    @END
    0;JMP

追蹤 RAM[0]\(=5\)： \(5\)（奇）\(\to 16 \to 8 \to 4 \to 2 \to 1\)， 依序寫入 RAM[32..37] \(= 5,16,8,4,2,1\) ✓。

溢位提醒：Hack 只有 16 位元有號數 （最大 32767）。\(3x+1\) 一步就可能把 \(x > 10922\) 的奇數推出範圍——測試時挑軌跡峰值不超過 32767 的輸入 （例如 5、6、7、27 的峰值 9232 安全）。 題目說「這類數值驗證是早期電腦最常見的應用之一」—— 你正在重演 1950 年代數學家用真空管電腦做的事， 只是他們的字組更寬一點。

二進位直式乘法（shift-and-add）。 十進位直式乘法：把被乘數依序乘上每一位數字、 錯位相加。二進位更簡單——每位數字只有 0 或 1， 「乘上一位」變成「要或不要把（錯位後的） 被乘數加進結果」：

\[a \times b \;=\; \sum_{i=0}^{15} b_i \cdot (a \ll i)\]

掃描 \(b\) 的每一位（遮罩自加，第一部分 popcount 的老朋友）， 同步把 \(a\) 的「錯位副本」翻倍；該位是 1 就把副本加進結果：

// fastmult.asm -- R2 = R0 * R1，固定 16 圈
    @R2
    M=0
    @R1
    D=M
    @sh
    M=D            // sh = R1 的錯位副本（每圈翻倍）
    @mask
    M=1            // 掃描 R0 的位
(LOOP)
// if (R0 & mask) R2 += sh
    @mask
    D=M
    @R0
    D=D&M
    @SKIP
    D;JEQ
    @sh
    D=M
    @R2
    M=D+M
(SKIP)
// sh 翻倍（錯一位）
    @sh
    D=M
    M=D+M
// mask 翻倍；溢位成 0 = 16 位掃完
    @mask
    D=M
    MD=D+M
    @LOOP
    D;JNE
(END)
    @END
    0;JMP

複雜度對比：

附贈的正確性：這個演算法對負數也對—— 2’s complement 乘法 mod \(2^{16}\) 的位圖案與無號乘法相同 （第二週的「加法器不分正負」在乘法的延伸）。 硬體乘法器（例如 Hack 沒有的那顆）本質上就是把這 16 圈 展開成 16 層加法器陣列——你剛寫的程式就是 硬體乘法器的軟體轉世。

第一步：把幾何算清楚。

• 橫向：\(64 \text{ 欄} \times 8 \text{ px} = 512\) ✓ 整好一個螢幕寬。一個字組 16 px \(=\) 兩格： 偶數欄住低位元組（bit 0–7）、奇數欄住高位元組 （bit 8–15）——LSB 在左的規則決定了這個分配；

• 縱向：\(23 \text{ 列} \times 11 \text{ px} = 253\)， 剩 \(256-253 = 3\) 條像素列（253–255）塗黑；

• 格 \((r, c)\) 的第 0 條像素列住在 \[addr = 16384 + 32 \times (11r) + \lfloor c/2 \rfloor,\] 之後每條像素列 \(+32\)，共寫 11 次。

第二步：@ 的點陣圖。 8 寬 \(\times\) 11 高，最左像素對應 bit 0 （每列的值 \(=\sum_{\text{黑像素 } c} 2^c\)）：

（若想完全複製講義圖 2 的字形，照同樣方法逐列轉換即可 ——方法不變，只是 11 個常數不同。）

第三步：架構與 bookmark「函式」。 畫格子的程式碼要用兩次（擦舊、畫新）， 抄兩份太蠢——用題目教的技巧把它包成「函式」 PUTCELL：呼叫前把返回點的 ROM 位址 （標籤當值用！）存進 bookmark， 函式結尾 @bookmark / A=M / 0;JMP 跳回去。

方向鍵的掃描碼（Hack 字元集）： 左 \(=130\)、上 \(=131\)、右 \(=132\)、下 \(=133\)。 「每按一次動一格」用等待放開實現 （比 checker3 的 prev 更簡單的邊緣觸發法）。

完整程式：

// rogue.asm -- 23x64 格 Rogue 遊戲場，方向鍵移動 @
// ============ 初始化：字形表 RAM[40..50] ============
    @60
    D=A
    @40
    M=D        // ..####..
    @66
    D=A
    @41
    M=D        // .#....#.
    @153
    D=A
    @42
    M=D        // #..##..#
    @165
    D=A
    @43
    M=D        // #.#..#.#
    @165
    D=A
    @44
    M=D
    @165
    D=A
    @45
    M=D
    @121
    D=A
    @46
    M=D        // #..####.
    @1
    D=A
    @47
    M=D        // #.......
    @66
    D=A
    @48
    M=D        // .#....#.
    @60
    D=A
    @49
    M=D        // ..####..
    @50
    M=0        // ........
// ============ 清空螢幕；底部 3 條像素列塗黑 ============
    @SCREEN
    D=A
    @addr
    M=D
(CLR)                  // RAM[16384..24479] = 0（253 列）
    @addr
    D=M
    @24480
    D=D-A
    @BLK
    D;JGE
    @addr
    A=M
    M=0
    @addr
    M=M+1
    @CLR
    0;JMP
(BLK)                  // RAM[24480..24575] = -1（3 條黑列）
    @addr
    D=M
    @24576
    D=D-A
    @CINIT
    D;JGE
    @addr
    A=M
    M=-1
    @addr
    M=M+1
    @BLK
    0;JMP
(CINIT)
// ============ @ 放到左上格 (0,0) 並畫出 ============
    @crow
    M=0
    @ccol
    M=0
    @erase
    M=0
    @R0INIT
    D=A            // 標籤當值：返回位址存 bookmark
    @bookmark
    M=D
    @PUTCELL
    0;JMP
(R0INIT)
// ============ 主迴圈：輪詢方向鍵 ============
(MAIN)
    @KBD
    D=M
    @MAIN
    D;JEQ          // 沒按鍵
    @key
    M=D
    @130
    D=D-A
    @LEFT
    D;JEQ
    @key
    D=M
    @131
    D=D-A
    @UPK
    D;JEQ
    @key
    D=M
    @132
    D=D-A
    @RIGHT
    D;JEQ
    @key
    D=M
    @133
    D=D-A
    @DOWN
    D;JEQ
(WAITR)                // 非方向鍵（或移動完）：等放開
    @KBD
    D=M
    @WAITR
    D;JNE
    @MAIN
    0;JMP
(LEFT)
    @drow
    M=0
    @dcol
    M=-1
    @TRYMOVE
    0;JMP
(UPK)
    @drow
    M=-1
    @dcol
    M=0
    @TRYMOVE
    0;JMP
(RIGHT)
    @drow
    M=0
    @dcol
    M=1
    @TRYMOVE
    0;JMP
(DOWN)
    @drow
    M=1
    @dcol
    M=0
(TRYMOVE)
// 邊界檢查：0 <= nrow <= 22, 0 <= ncol <= 63
    @crow
    D=M
    @drow
    D=D+M
    @nrow
    M=D
    @WAITR
    D;JLT
    @22
    D=D-A
    @WAITR
    D;JGT
    @ccol
    D=M
    @dcol
    D=D+M
    @ncol
    M=D
    @WAITR
    D;JLT
    @63
    D=D-A
    @WAITR
    D;JGT
// 擦掉舊格（呼叫 PUTCELL，erase=1）
    @erase
    M=1
    @RETE
    D=A
    @bookmark
    M=D
    @PUTCELL
    0;JMP
(RETE)
// 座標更新、畫新格（erase=0）
    @nrow
    D=M
    @crow
    M=D
    @ncol
    D=M
    @ccol
    M=D
    @erase
    M=0
    @RETD
    D=A
    @bookmark
    M=D
    @PUTCELL
    0;JMP
(RETD)
    @WAITR
    0;JMP          // 等放開，一次按鍵只動一格
// ============ 「函式」PUTCELL ============
// 在 (crow,ccol) 畫 @（erase=0）或擦成白（erase=1）
// 結束跳回 bookmark
(PUTCELL)
// addr = SCREEN + 352*crow + ccol/2
    @SCREEN
    D=A
    @addr
    M=D
    @crow
    D=M
    @i
    M=D
(MUL352)               // 加法代替乘法：至多 22 圈
    @i
    D=M
    @MULDONE
    D;JLE
    @352
    D=A
    @addr
    M=D+M
    @i
    M=M-1
    @MUL352
    0;JMP
(MULDONE)
    @ccol
    D=M
    @c
    M=D
(HALVE)                // addr += ccol/2；odd = ccol%2
    @c
    D=M
    @2
    D=D-A
    @HDONE
    D;JLT
    @c
    M=D
    @addr
    M=M+1
    @HALVE
    0;JMP
(HDONE)
    @c
    D=M
    @odd
    M=D            // 0 = 低位元組，1 = 高位元組
// 逐列寫 11 列
    @40
    D=A
    @gp
    M=D            // 字形指標
    @11
    D=A
    @i
    M=D
(PROW)
// v = erase ? 0 : glyph[gp]
    @gp
    A=M
    D=M
    @v
    M=D
    @erase
    D=M
    @VOK
    D;JEQ
    @v
    M=0
(VOK)
// 奇數欄：v <<= 8；遮罩留低位元組（255）
// 偶數欄：v 不動；遮罩留高位元組（!255）
    @odd
    D=M
    @ODDCOL
    D;JNE
    @255
    D=!A           // D = 0xFF00：保留高 8 位
    @WMERGE
    0;JMP
(ODDCOL)
    @8
    D=A
    @j
    M=D
(SH8)                  // v <<= 8（8 次自加）
    @v
    D=M
    M=D+M
    @j
    MD=M-1
    @SH8
    D;JGT
    @255
    D=A            // D = 0x00FF：保留低 8 位
(WMERGE)
// RAM[addr] = (RAM[addr] & 遮罩) | v
    @addr
    A=M
    D=D&M          // D = 要保留的另半格
    @v
    D=D|M
    @addr
    A=M
    M=D
// 下一條像素列
    @32
    D=A
    @addr
    M=D+M
    @gp
    M=M+1
    @i
    MD=M-1
    @PROW
    D;JGT
// 返回呼叫點
    @bookmark
    A=M
    0;JMP

設計重點回顧：

• 讀—改—寫（read-modify-write）： 一個字組住兩格，寫自己那半格前必須先讀出整字組、 用遮罩保住鄰居的半格再 OR 回去—— 不然每次移動都會把隔壁格擦掉；

• 乘法都用加法迴圈：\(352 \times crow\) 至多 22 圈、\(ccol/2\) 至多 32 圈——輸入域小， 簡單勝過聰明（想快可用第 4 節的移位乘法）；

• bookmark 的極限（題目的伏筆）： 這種「函式呼叫」只有一層—— 若 PUTCELL 裡再「呼叫」別的函式， 第二次寫 bookmark 就把第一個返回位址 蓋掉了。解法是把返回位址疊起來—— 這正是第九、十週堆疊（stack）與呼叫框架的開場白。

測試流程：No animation 模式執行 \(\to\) 左上角出現 @、底部 3 條黑線 \(\to\) 點鍵盤按方向鍵：每按一次動一格、到邊界停住、 移動時不留殘影 ✓。