在搜索文本中的字符串的 Search Ultimate 程序失败后,Igor K. 开始思考:“到底为什么我的程序运行得这么慢?”当他仔细检查代码时,他说:“我的代码没有错误,但我知道我们将如何改进 Search Ultimate!”从书架上拿出一本大书。这本书是“Azembler. 主要是新方法”。
仔细翻阅这本书后,Igor K. 意识到,事实证明,你可以将数字相乘的速度提高数十倍。 “Search Ultimate 将比以往更快!” ——那家伙高兴地喊道,然后开始工作。
现在让我们澄清伊戈尔的想法是什么。问题是编译器生成的代码远非完美。标准乘法确实比书中提到的技巧慢。
Azembler 语言使用 26 个寄存器(eax、ebx、...、ezx)和两个命令进行操作:
- [x] — 返回位于地址 x 中的值。例如,[eax] 返回位于地址中的值,等于寄存器 eax 中的值。
- lea x, y — 分配给寄存器 x,表示为第一个操作数,第二个操作数的地址。因此,例如,“lea ebx,[eax]”命令将把 eax 寄存器的内容写入 ebx 寄存器:首先将完成 [eax] 操作,其结果将是位于 eax 中写入的地址中的某个值。但我们不需要这个值——下一个操作将是 lea,它将获取 [eax] 地址,即 eax 寄存器中的值,并将其写入 ebx。
乍一看,第二个操作似乎毫无意义,但事实证明,将操作写为是可以接受的
lea ecx, [eax + ebx],
lea ecx, [k*eax]
甚至
lea ecx, [ebx + k*eax],
其中 k = 1、2、4 或 8。
因此,寄存器 ecx 将相应地等于数字 eax + ebx、k*eax 和 ebx + k*eax。然而,这种运算的执行速度比通常的数字乘法要快几十倍。通过使用几个这样的运算,我们可以非常快速地将某个数字乘以另一个数字。当然,您可以使用任何寄存器来代替 eax、ebx 和 ecx。
例如,让 eax 寄存器包含一些我们应该乘以 41 的数字。这需要 2 行:
lea ebx, [eax + 4*eax] // 现在 ebx = 5*eax
lea eax, [eax + 8*ebx] // 现在 eax = eax + 8*ebx = 41*eax
Igor K. 对以下问题感兴趣:乘以给定数字 n 所需的最小 lea 运算次数是多少以及如何做到这一点?你的任务是帮助他。
考虑在初始时刻 eax 包含 Igor K. 即将乘以 n 的数字,并且从 ebx 到 ezx 的寄存器包含数字 0。在最后时刻,结果可以位于任何寄存器中。
输入
输入数据包含唯一的整数 n (1 ≤ n ≤ 255),Igor K. 即将乘以该整数。
输出
在第一行打印数字 p,它表示执行此操作所需的最小 lea 操作数。然后打印由 p 命令组成的程序,执行操作。保证对于 1 到 255 之间的任意 n 都存在这样的程序。
精确使用以下格式的命令(这里 k 等于 1、2、4 或 8,x、y 和 z 是任何寄存器,甚至是重合的寄存器):
lea x, [y]
lea x, [y + z]
lea x, [k*y]
lea x, [y + k*z]
请注意,命令末尾的多余空格是不可接受的。
示例
输入 #1
41
输出 #1
2 lea ebx, [eax + 4*eax] lea ecx, [eax + 8*ebx]
输入 #2
2
输出 #2
1 lea ebx, [eax + eax]
输入 #3
4
输出 #3
1 lea ebx, [4*eax]