您可能不知道的 C/C++ 中的 switch 语句
4.86/5 (150投票s)
通过逆向工程 VC++ 讨论 switch/case 的执行方式
引言
许多编程语言，如 C/C++、C#、Java 和 Pascal 都提供了 switch 语句，以便我们实现选择逻辑。在某些情况下，它是 if-then-else 的一个很好的替代方案，使代码更清晰、更易读。在实践中使用 switch 时，您可能想知道
switch块在运行时是如何执行的？- 对于长列表的条件，它的运行速度是否比
if-then-else快？ - 对于 n 个条件，
switch的时间复杂度是多少？
C/C++ 标准定义了语言元素的规范，但并未说明如何实现 switch 语句。任何供应商都可以自由使用任何实现，只要它符合标准。本文讨论了在 Visual C++ 中运行 switch 语句时会发生什么，并提供了几个在不同条件下的示例。我们将使用 Microsoft Visual Studio IDE 分析这些示例，因为它可以在编译时生成相应的汇编列表。因此，假设您对 Intel (x86) 汇编语言有一般的了解。正如您很快会看到的，这里的所有结果都基于逆向工程，因此本文绝不是对编译器中 switch 实现的全面描述。如果您正在学习汇编语言编程，本文可能是一份学习材料。
我们的第一个示例是 switch1.cpp，一个常用的简单块，如下所示
#include "functions.h"
int main()
{
int i =3; // or i =20
switch (i)
{
case 1: f1(); break;
case 2: f2(); break;
case 5: f1(); break;
case 7: f2(); break;
case 10: f1(); break;
case 11: f2(); break;
case 12: f2(); break;
case 17: f1(); break;
case 18: f1(); break;
default: f3();
}
return 0;
}
其中三个函数定义在 functions.cpp 中
void f1() { cout "f1 called\n"; }
void f2() { cout "f2 called\n"; }
void f3() { cout "f3 called\n"; }
最坏情况是否可以认为是 i=3 或 i=20？它是如何执行的：它会耗尽所有九个 case 并最终到达 default 来调用 f3 吗？让我们从汇编翻译中找到答案。
要在 Visual Studio 中生成汇编列表，请打开 switch1.cpp 的属性对话框，然后在 C/C++ 下选择“输出文件”类别。在右侧窗格中，选择“带源代码的程序集”(/FAs) 选项，如下图所示
然后，当您编译 switch1.cpp 时，将生成一个名为 switch1.asm 的汇编文件。使用此选项，列表将包含 C++ 源代码，并以分号和行号作为注释，如下节所示。
两级跳转表
让我们从上到下分析汇编列表。switch 从这里开始
; 5 : int i =3; // or i =20
mov DWORD PTR _i$[ebp], 3
; 6 :
; 7 : switch (i)
mov eax, DWORD PTR _i$[ebp]
mov DWORD PTR tv64[ebp], eax
mov ecx, DWORD PTR tv64[ebp]
sub ecx, 1
mov DWORD PTR tv64[ebp], ecx
cmp DWORD PTR tv64[ebp], 17 ; 00000011H
ja SHORT $LN1@main
mov edx, DWORD PTR tv64[ebp]
movzx eax, BYTE PTR $LN15@main[edx]
jmp DWORD PTR $LN16@main[eax*4]
假设符号 _i$[ebp] 是 i 的别名，tv64[ebp] 是 i2 的另一个名称，$LN15@main 被重命名为 table1，$LN16@main 被重命名为 table2，而 $LN1@main 是一个名为 Default_Label 的标签。片段仅用伪代码表示
i2 = i;
i2 = i2-1;
if i2 > 17 goto Default_Label;
goto table2[4*table1[i2]];
在这里，17 表示最后一个 case 条件值，因为整数 1 到 18 被映射为 0 到 17。这就是为什么 i2 被减去，使其成为一个零基整数作为索引。现在，如果 i2 大于 17（例如，n=20），控制将转到 default。否则，它将转到 table2[4*table1[i2]] 所指向的位置。
当 i 为零时会怎样？那么 i2 将变成 -1。担心索引越界错误吗？不，它永远不会发生。回到汇编列表，您可以看到 -1 被保存为 DWORD，即双字（无符号 4 字节整数）。因此，它必须大于 17 并转到 default。
让我们看看两个表，看看它们是如何协同工作的。table1 非常简单，起始地址为 $LN15@main，您可以将其视为一个数组名。
$LN15@main:
DB 0
DB 1
DB 9
DB 9
DB 2
DB 9
DB 3
DB 9
DB 9
DB 4
DB 5
DB 6
DB 9
DB 9
DB 9
DB 9
DB 7
DB 8
使用这个数组，table1[0] 是 0，table1[1] 是 1，table1[2] 和 table1[3] 是 9，等等。这些值用于计算 table2 的索引，table2 以 $LN16@main 开始
$LN16@main:
DD $LN10@main
DD $LN9@main
DD $LN8@main
DD $LN7@main
DD $LN6@main
DD $LN5@main
DD $LN4@main
DD $LN3@main
DD $LN2@main
DD $LN1@main
上述标签，从 $LN10@main 到 $LN1@main，是 C++ 中的十个调用目标，对应九个 case 加上一个 default。请注意，DB 表示定义字节（8 位），而 DD 定义四字节（32 位）的双字类型。这就是为什么我们需要在 table2[4*table1[i2]] 中乘以 4。通过这个公式，我们通过 table1 和 table2 计算调用地址
- 如果
i等于 1，i2为 0 且table1[0]为 0，则通过table2[0]（第一个 case）跳转到$LN10@main。 - 如果
i等于 2，i2为 1 且table1[1]为 1，则通过table2[4*1]（第二个 case）跳转到$LN9@main。 - 如果
i等于 3，i2为 2 且table1[2]为 9，则通过table2[4*9]（默认 case）跳转到$LN1@main。 - ... ...
现在我们来看标记为 LN10@main 到 $LN1@main 的代码段，作为调用目标
$LN10@main:
; 8 : {
; 9 : case 1: f1(); break;
call ?f1@@YAXXZ ; f1
jmp SHORT $LN11@main
$LN9@main:
; 10 : case 2: f2(); break;
call ?f2@@YAXXZ ; f2
jmp SHORT $LN11@main
$LN8@main:
; 11 : case 5: f1(); break;
call ?f1@@YAXXZ ; f1
jmp SHORT $LN11@main
; ... ...
$LN2@main:
; 17 : case 18: f1(); break;
call ?f1@@YAXXZ ; f1
jmp SHORT $LN11@main
$LN1@main:
; 18 :
; 19 : default: f3();
call ?f3@@YAXXZ ; f3
$LN11@main:
; 20 : }
; 21 :
; 22 : return 0;
函数 f1、f2 和 f3 被转换为修饰的汇编过程，并带有问号前缀，例如 ?f1@@YAXXZ、?f2@@YAXXZ 和 ?f3@@YAXXZ。请注意，$LN10@main 是 case 1 的标签，用于调用 f1；$LN9@main 是 case 2 的标签，用于调用 f2；$LN1@main 是 default 的标签，用于调用 f3。
还有一个额外的标签 $LN11@main，指向最后一个 default 子句之后的位置。每个 case 操作完成后，控制将跳转到 $LN11@main。这实现了 break 语句。没有它，控制将转到下一个 case。这就是为什么 break 语句在 C/C++ switch 块中是必需的。
显然，基于这种两级表机制，我们进行了一次比较、一次乘法和两次地址跳转。此 switch 模式的时间复杂度应为 O(1)。把这一切放在一起，我们有一个大局如下
回想一下，我们在 table1 中使用 DB 定义索引值，在 table2 中使用 DD。在此示例中，table1 只有 18 个 case 值。但是 DB 定义 byte 意味着范围仅为零到 255。如果 switch 中有更多 case，并且值超过 255 怎么办？
一级跳转表
现在来看第二个示例，switch2.cpp，包含 1000 个 case。为简单起见，我们从条件值为零开始
int main2()
{
int i =1000;
switch (i)
{
case 0: f1(); break;
case 1: f1(); break;
case 2: f2(); break;
case 3: f1(); break;
// ... ...
case 995: f1(); break;
case 996: f1(); break;
case 997: f1(); break;
case 998: f2(); break;
case 999: f1(); break;
default: f3();
}
return 0;
}
不要认为这会使事情变得复杂。恰恰相反，它变得更简单了。这是 Visual Studio 为我们生成的 switch2.asm
; 5 : int i =1000;
mov DWORD PTR _i$[ebp], 1000 ; 000003e8H
; 6 :
; 7 : switch (i)
mov eax, DWORD PTR _i$[ebp]
mov DWORD PTR tv64[ebp], eax
cmp DWORD PTR tv64[ebp], 999 ; 000003e7H
ja $LN1@main2
mov ecx, DWORD PTR tv64[ebp]
jmp DWORD PTR $LN1006@main2[ecx*4]
同样，假设符号 _i$[ebp] 是 i 的别名。因为第一个 case 从零开始，所以不需要映射。因此 i2（来自 tv64[ebp]）等于 i。数组 $LN1006@main2 是一个唯一的跳转表，标签 $LN1@main2 是 Default_Label。这个片段只是这样做
i2 = i;
if i2 > 999 goto Default_Label;
goto table[4*i2];
通过在 switch2.asm 中搜索 $LN1006@main2，我们发现所有代码标签都由双字定义
$LN1006@main2:
DD $LN1001@main2
DD $LN1000@main2
DD $LN999@main2
DD $LN998@main2
DD $LN997@main2
DD $LN996@main2
; ... ...
DD $LN5@main2
DD $LN4@main2
DD $LN3@main2
DD $LN2@main2
总共有 1000 个调用目标，每个标签后面都有一个过程调用，从 $LN1001@main2 到 $LN2@main2 向下排列
$LN1001@main2:
; 8 : {
; 9 : case 0: f1(); break;
call ?f1@@YAXXZ ; f1
jmp $LN1002@main2
$LN1000@main2:
; 10 : case 1: f1(); break;
call ?f1@@YAXXZ ; f1
jmp $LN1002@main2
$LN999@main2:
; 11 : case 2: f2(); break;
call ?f2@@YAXXZ ; f2
jmp $LN1002@main2
; ... ...
$LN3@main2:
; 1106 : case 998: f2(); break;
call ?f2@@YAXXZ ; f2
jmp SHORT $LN1002@main2
$LN2@main2:
; 1107 : case 999: f1(); break;
call ?f1@@YAXXZ ; f1
jmp SHORT $LN1002@main2
$LN1@main2:
; 1108 :
; 1109 : default: f3();
call ?f3@@YAXXZ ; f3
$LN1002@main2:
; 1110 : }
; 1111 :
; 1112 : return 0;
在这里，$LN1@main2 指向 default，额外的标签 $LN1002@main 实现 break。虽然复杂度也为 O(1)，但这种机制应该会更有效一些，因为它只需要一次地址跳转。下面是这个示例的图示
到目前为止，我们看到了 switch 的出色执行示例。使用 switch 是否真的比 if-then-else 更好？对于 n 个条件不匹配的情况，if-then-else 必须检查每个条件直到最后一个，这是最坏情况 O(n)。但是对于 switch，我们是否总是期望它的复杂度为 O(1)？或者是否存在某种代码会导致其执行超出这个范围？
使用二分查找
我们将给出第三个示例，在 switch3.cpp 中展示 case 条件值之间的巨大差距，其中 switch 的执行行为类似于二分查找
int main3()
{
int i =1;
switch (i)
{
case 100: f1(); break;
case 200: f2(); break;
case 250: f2(); break;
case 500: f1(); break;
case 700: f2(); break;
case 750: f2(); break;
case 800: f2(); break;
case 900: f1(); break;
default: f3();
}
return 0;
}
通过生成汇编列表 switch3.asm，这次我们从下往上查看，先检查 case 操作
$LN9@main3:
; 8 : {
; 9 : case 100: f1(); break;
call ?f1@@YAXXZ ; f1
jmp SHORT $LN10@main3
$LN8@main3:
; 10 : case 200: f2(); break;
call ?f2@@YAXXZ ; f2
jmp SHORT $LN10@main3
$LN7@main3:
; 11 : case 250: f2(); break;
call ?f2@@YAXXZ ; f2
jmp SHORT $LN10@main3
$LN6@main3:
; 12 : case 500: f1(); break;
call ?f1@@YAXXZ ; f1
jmp SHORT $LN10@main3
$LN5@main3:
; 13 : case 700: f2(); break;
call ?f2@@YAXXZ ; f2
jmp SHORT $LN10@main3
$LN4@main3:
; 14 : case 750: f2(); break;
call ?f2@@YAXXZ ; f2
jmp SHORT $LN10@main3
$LN3@main3:
; 15 : case 800: f2(); break;
call ?f2@@YAXXZ ; f2
jmp SHORT $LN10@main3
$LN2@main3:
; 16 : case 900: f1(); break;
call ?f1@@YAXXZ ; f1
jmp SHORT $LN10@main3
$LN1@main3:
; 17 :
; 18 : default: f3();
call ?f3@@YAXXZ ; f3
$LN10@main3:
; 19 : }
; 20 :
; 21 : return 0;
非常整洁，有八个 case 加上一个 default，我们可以轻松地将这部分写成一个九行列表，每行对应一个目标标签、一个 C++ case 和一个过程名
除了 $LN9@main3 到 $LN1@main3 之外，我们还有 $LN10@main3 来实现 break 语句。接下来，我们如何跳转到这些调用目标？看下面的代码
; 5 : int i =1;
mov DWORD PTR _i$[ebp], 1
; 6 :
; 7 : switch (i)
mov eax, DWORD PTR _i$[ebp]
mov DWORD PTR tv64[ebp], eax
cmp DWORD PTR tv64[ebp], 700 ; 000002bcH
jg SHORT $LN14@main3
cmp DWORD PTR tv64[ebp], 700 ; 000002bcH
je SHORT $LN5@main3
cmp DWORD PTR tv64[ebp], 250 ; 000000faH
jg SHORT $LN15@main3
cmp DWORD PTR tv64[ebp], 250 ; 000000faH
je SHORT $LN7@main3
cmp DWORD PTR tv64[ebp], 100 ; 00000064H
je SHORT $LN9@main3
cmp DWORD PTR tv64[ebp], 200 ; 000000c8H
je SHORT $LN8@main3
jmp SHORT $LN1@main3
$LN15@main3:
cmp DWORD PTR tv64[ebp], 500 ; 000001f4H
je SHORT $LN6@main3
jmp SHORT $LN1@main3
$LN14@main3:
cmp DWORD PTR tv64[ebp], 750 ; 000002eeH
je SHORT $LN4@main3
cmp DWORD PTR tv64[ebp], 800 ; 00000320H
je SHORT $LN3@main3
cmp DWORD PTR tv64[ebp], 900 ; 00000384H
je SHORT $LN2@main3
jmp SHORT $LN1@main3
逻辑不难理解。首先，条件值 i 被保存在 _i$[ebp] 和 tv64[ebp] 中。为了简化，我们只利用所有标签，移除开头的 "$" 和结尾的 "@main3"。重写片段如下
i2 = i;
if i2 > 700 goto LN14;
if i2 == 700 goto LN5;
if i2 > 250 goto LN15;
if i2 == 250 goto LN7;
if i2 == 100 goto LN9;
if i2 == 200 goto LN8;
goto LN1;
LN15:
if i2 == 500 goto LN6;
goto LN1;
LN14:
if i2 == 750 goto LN4;
if i2 == 800 goto LN3;
if i2 == 900 goto LN2;
goto LN1;
当然，编译器会优化代码，因为它首先选择 700 进行比较，而不是 switch 块中的起始 case 值 100。尽管这个 switch 是用十个 if-then 语句来实现九个条件的，但它实际上应用了二分查找机制。下图显示了上述代码的等效决策树，即您可能熟悉的二叉搜索树
对于所有用黄色圆圈着色的内部节点，我们进行比较，而所有椭圆形叶子节点表示成功结束。每次失败都默认转到 LN1。比较节点的中序遍历序列是 100、200、250、500、700、750、800 和 900；而所有叶子的中序遍历序列恰好是 LN9、LN8、LN7、LN6、LN5、LN4、LN3 和 LN2，如上表所示。本质上，这是一个复杂度为 O(log n) 的二分查找算法。当 i=1 时，它将经过前六次比较，然后到达 LN1 的 default。但是当 i=500 时，只需要四次比较。
我们知道，二分查找的前提是输入数据已排序。我想知道这是否仅仅因为我在 switch3.cpp 的 switch 中使用了升序的 case 值。这种好奇心引出了 switch4.cpp 中无序的条件。
int main4()
{
int i =1;
switch (i)
{
case 750: f2(); break;
case 700: f2(); break;
case 250: f2(); break;
case 500: f1(); break;
case 800: f2(); break;
case 900: f1(); break;
case 100: f1(); break;
case 200: f2(); break;
default: f3();
}
return 0;
}
令我惊讶的是，相同的二分查找策略出现在 switch4.asm 的代码中，具有与上面完全相同的决策树。唯一的区别是标签被重新编号了——这是非常合理的，因为我们刚刚重新排序了它们！您可以查看随附的 switch4.asm 以了解详细信息。
这个实验无疑给我们提供了一些线索，以找出编译器是如何神奇地对 case 条件值进行排序的。排序算法的复杂度高于 O(log n)，并且在运行时不值得这样做。注意，排序在生成的汇编中是不可见的。这意味着排序不包含在运行时执行的汇编指令中。还请注意，所有条件值都是常量，在编译器将 C++ 转换为机器码之前就可以获得。现在，考虑到预处理器是合理的；所有已知 case 值以及排序都可以简单地在编译时完成。这就是为什么翻译的汇编代码只反映二分查找而没有排序代码。静态排序行为（与运行时动态行为相对）可以通过宏过程、汇编指令和运算符来实现。可以在文章末尾的参考文献中找到这样的预处理示例。
混合实现
现在，我可以展示一个将跳转表和二分查找结合起来的示例，如 switch5.cpp 所示。
int main5()
{
int i =1;
switch (i)
{
case 3: f1(); break;
case 5: f2(); break;
case 6: f2(); break;
case 7: f2(); break;
case 100: f1(); break;
case 200: f2(); break;
case 250: f2(); break;
case 700: f2(); break;
case 750: f2(); break;
case 900: f2(); break;
default: f3();
}
return 0;
}
这是此 switch 块在相应的 switch5.asm 中的实现方式
; 5 : int i =1;
mov DWORD PTR _i$[ebp], 1
; 6 :
; 7 : switch (i)
mov eax, DWORD PTR _i$[ebp]
mov DWORD PTR tv64[ebp], eax
cmp DWORD PTR tv64[ebp], 100 ; 00000064H
jg SHORT $LN16@main5
cmp DWORD PTR tv64[ebp], 100 ; 00000064H
je $LN7@main5
mov ecx, DWORD PTR tv64[ebp]
sub ecx, 3
mov DWORD PTR tv64[ebp], ecx
cmp DWORD PTR tv64[ebp], 4
ja $LN1@main5
mov edx, DWORD PTR tv64[ebp]
jmp DWORD PTR $LN18@main5[edx*4]
$LN16@main5:
cmp DWORD PTR tv64[ebp], 700 ; 000002bcH
jg SHORT $LN17@main5
cmp DWORD PTR tv64[ebp], 700 ; 000002bcH
je SHORT $LN4@main5
cmp DWORD PTR tv64[ebp], 200 ; 000000c8H
je SHORT $LN6@main5
cmp DWORD PTR tv64[ebp], 250 ; 000000faH
je SHORT $LN5@main5
jmp SHORT $LN1@main5
$LN17@main5:
cmp DWORD PTR tv64[ebp], 750 ; 000002eeH
je SHORT $LN3@main5
cmp DWORD PTR tv64[ebp], 900 ; 00000384H
je SHORT $LN2@main5
jmp SHORT $LN1@main5
它由两部分组成，首先是一个一级跳转表，然后是二分查找代码。使用前面提到的 i、i2 和标签命名，令 $LN18@main5 为表，$LN1@main5 为 default。此片段执行以下操作
i2 = i;
if i2 > 100 goto LN16;
if i2 == 100 goto LN7; // go case 100
// now i2 < 100
i2 = i2-3; // map to zero-based index
if i2 > 4 goto LN1; // go default over 7
goto table[4*i2]; // go jump table
LN16: // binary search
if i2 > 700 goto LN17;
if i2 == 700 goto LN4; // go case 700
if i2 == 200 goto LN6; // go case 200
if i2 == 250 goto LN5; // go case 250
goto LN1; // go default
LN17:
if i2 == 750 goto LN3; // go case 750
if i2 == 900 goto LN2; // go default
goto LN1;
其中表定义为
$LN18@main5:
DD LN11 ; index 0, go case 3
DD LN1 ; index 1 for value 4, go default
DD LN10 ; index 2, go case 5
DD LN9 ; index 3, go case 6
DD LN8 ; index 4, go case 7
一个有趣的改变是在 switch5.cpp 中删除了 case 6。仅仅因为这个原因，混合实现就变成了两级跳转表和二分查找的组合。详情请参阅可下载示例中的 switch6.cpp 和 switch6.asm。如果您尝试以某种顺序添加额外的 case，您会发现两个独立的跳转表与二分查找结合起来。
更多问题和扩展
现在您已经通过一些典型示例了解了 switch 的一些知识。您现在应该理解为什么 C/C++ switch 只支持整数数据类型作为条件表达式，例如 char 和枚举类型，而不是 float 点数或 string 类型。除此之外，可能还会出现更多直观的问题
- 是否需要按条件值顺序维护
jump表中的 case？ - 如果我们使用负整数作为 case 值怎么办？
- 如果
default标签缺失，或者出现在块中的任何位置而不是最后怎么办？
我相信您可以通过分析包含这些问题的 C++ 代码的汇编列表来回答这些问题。为了方便起见，我在示例中附上了 switch7.cpp 及其 switch7.asm。
int main7()
{
int i =15;
switch (i)
{
case 2: f2(); break;
case 1: f1(); break;
case 5: f1(); break;
case 10: f1(); break;
case 7: f2(); break;
default: f3(); break;
case -3: f2(); break;
case 12: f1(); break;
case 17: f2(); break;
case 18: f1(); break;
}
return 0;
}
尽管在这些示例中 switch 的性能看起来比 if-than-else 更好，但我们仍然有一些未解决的问题。显然，在实践中不可能枚举所有 switch 的执行方式。对 switch 实现的全面分析应该由编译器开发人员编写，而不是由盲目的黑盒测试人员编写。因此，我们无法确定 switch 执行中的最坏情况，它是否会达到 O(n)。我们也不知道在什么条件下，编译器会选择一种实现而不是另一种，或者甚至是我们未提及的其他方法。
作为读者在讨论中的一个例子，一个担忧是上述跳转表在实现稀疏填充的 switch case 时会造成内存浪费。对于只有两个 case 条目 1 和 0x7fffffff 的极端示例，如下所示？编译器会消耗大部分无用的条目在跳转表中吗？
int main8()
{
int i =3;
switch (i)
{
case 1: f1(); break;
case 0x7fffffff: f2(); break;
default: f3(); break;
}
return 0;
} 这对我们聪明的编译器来说并非如此。如前所述，我们不知道编译器如何选择一种实现而不是另一种。请参阅这里，这个双 case 示例没有选择跳转表。它只是简单地将 switch 转换为 if-then，而没有消耗任何额外的内存：
; 5 : int i =3;
mov DWORD PTR _i$[ebp], 3
; 6 :
; 7 : switch (i)
mov eax, DWORD PTR _i$[ebp]
mov DWORD PTR tv64[ebp], eax
cmp DWORD PTR tv64[ebp], 1
je SHORT $LN3@main8
cmp DWORD PTR tv64[ebp], 2147483647 ; 7fffffffH
je SHORT $LN2@main8
jmp SHORT $LN1@main8
$LN3@main8:
; 8 : {
; 9 : case 1: f1(); break;
call ?f1@@YAXXZ ; f1
jmp SHORT $LN4@main8
$LN2@main8:
; 10 : case 0x7fffffff: f2(); break;
call ?f2@@YAXXZ ; f2
jmp SHORT $LN4@main8
$LN1@main8:
; 11 : default: f3(); break;
call ?f3@@YAXXZ ; f3
$LN4@main8:
; 12 : }
; 13 :
; 14 : return 0; 同样，通过这种黑盒测试，无法影响或预测编译器的选择。 根据问题的不同，无论是稀疏还是密集填充的 switch case， 编译器显然都能很好地适应它们。
总结
通过仔细审查上述示例，我们揭示了一些您可能不知道的关于运行时 switch 的知识。要在 Visual Studio 中分析 C/C++ 程序，我们可以进行静态和动态分析。对于本文，我们利用编译器生成的汇编列表。另一方面，我们也可以在调试时使用 VS 反汇编窗口监控二进制执行，其中列表中的标签和过程被转换为内存地址。这样，您可以跟踪寄存器和内存分配，以理解数据端序、堆栈帧等。在这里，对我们来说，汇编列表似乎足以且易于指示从此处到那里的跳转。可下载的 zip 文件包含七个示例，其中包含 .cpp 源代码和 VS 2010 中的 .asm 列表。较早版本的 VS 也可以生成相同的列表。
本文不涉及 .NET 或 C# 等热门技术。汇编语言相对传统，如今已经不那么引人注目了。然而，在应用程序中，不同类型的汇编语言在新设备开发中起着重要作用。在学术上，汇编语言编程被认为是计算机科学中的一门要求很高的课程。我在富勒顿学院教授汇编语言编程，CSCI 241，其中高级语言与底层执行交互的概念是教学的重要组成部分。特别是，学生们感兴趣的主要主题之一是如何 C/C++ 或 Java 在机器上运行，由低级数据结构和算法表示。因此，我希望本文也能作为学生解决问题的基本示例之一。欢迎任何评论和建议。
致谢
我谨此感谢 wtwhite、Charvak Karpe 和 Harold Aptroot 就二分查找进行的宝贵讨论。没有他们，“使用二分查找”一节就不会像今天这样。
参考文献
- 来自 MSDN：Microsoft Macro Assembler Reference
- 反神论战争：x86 指令集
- 教材：Assembly Language for Intel-Based Computers
历史
- 2010年8月9日 -- 发布原始版本
- 2010年9月8日 -- 修改并重写了一些章节
- 将“switch 语句的最坏情况”一节替换为“使用二分查找”。添加了二叉搜索树图像。
- 添加了“混合实现”一节
- 重写了“更多问题和扩展”一节
- 调整了前两个章节之间的段落
- 在“两级
Jump表”一节中添加了对负索引的解释
- 2010年9月28日 -- 文章更新
- 澄清了关于二分查找排序先决条件未解答的问题。
- 添加了致谢和参考文献
- 2012年12月19日 -- 纳入了 Christian Scholze 的内存讨论示例