能力值：
(RANK：330 )
2 楼
学习123456
能力值：
( LV4，RANK：50 )
3 楼
先附上参考资料：
1. Concrete Mathematics - Ronald L. Graham
2. The Art of Computer Programming - Donald E. Knuth
3. divcnst-pldi94.pdf (感谢forgot提供)
4. The Solver Web Online Help - ? (
http://www.thesolver.it/Manuali/Factotum/source/001.htm 感谢bughoho提供)
由于本人没学会如何将word中的数学公式转换为论坛格式，故以下讨论用抓图表达。
上传的附件：
能力值：
( LV4，RANK：50 )
4 楼
能力值：
( LV4，RANK：50 )
5 楼
3. VC++6.0对整数除法的优化和论证 A. VC++6.0 对除以整型常量的各类处理
整数除法运算对应汇编指令分有符号idiv、无符号div。除法是指令中执行周期较长的，因此其效率也是较低的，所以编译器会尽量将除法指令用其它运算指令代替。C++中的除法和数学中的除法不同。在C++中除法运算不保留余数，有专门提求取余数的运算“%”也称之为取模运算。而且对于整数除法，C++的规则是仅仅保留整数部分，小数部分完全舍弃。
如果除数是变量，则只能使用除法指令。但是如果除数为常量，便有了优化的余地，根据除数值的相关特性，编译器有对应的处理方式。
在本节我们讨论编译其对除数为2的次方、非2次方、负数等各类情景的处理方式，我们假定整型为4字节补码形式。
见代码中实例演示。
各类型除法转换——Debug调试版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// C++源码说明：除法运算
// 变量定义
int nVarOne = argc;
int nVarTwo = argc;
// 两变量做除法
printf("nVarOne / nVarTwo = %d", nVarOne / nVarTwo);
// 变量除以常量，常量2的1次方
printf("nVarOne / 2 = %d", nVarOne / 2);
// 变量除以非二次方数
printf("nVarTwo / 7 = %d", nVarTwo / 7);
// 变量对非二次方数取模
printf("nVarTwo % 7 = %d", nVarTwo % 7);
// 变量除以常量，常量为2的3次方
printf("nVarOne / 8 = %d", nVarOne / 8);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// C++源码于对应汇编代码讲解
// C++源码对比，变量定义
int nVarOne = argc;
0040B7E8 mov eax,dword ptr [ebp+8]
0040B7EB mov dword ptr [ebp-4],eax
// C++源码对比，变量定义
37: int nVarTwo = argc;
0040B7EE mov ecx,dword ptr [ebp+8]
0040B7F1 mov dword ptr [ebp-8],ecx
// 除法运算转换特性
// C++源码对比，变量 / 变量
printf("nVarOne / nVarTwo = %d", nVarOne / nVarTwo);
; 取出被除数放入eax中
0040B7F4 mov eax,dword ptr [ebp-4]
; 扩展高位
0040B7F7 cdq
; 两变量相除，直接使用有符号除法指令idiv
0040B7F8 idiv eax,dword ptr [ebp-8]
; eax保存商值，作为参数压栈，调用函数printf，此函数讲解略
0040B7FB push eax
0040B7FC push offset string "nVarOne / nVarTwo = %d" (00420034)
0040B801 call printf (0040b750)
0040B806 add esp,8
1
2
3
4
5
6
7
8
9
// C++源码对比，变量 / 常量（常量值为2）
printf("nVarOne / 2 = %d", nVarOne / 2);
0040B809 mov eax,dword ptr [ebp-4]
0040B80C cdq
; 自身减去扩展高位
0040B80D sub eax,edx
; 和乘法运算类似，乘法是左移，对应的除法为右移
0040B80F sar eax,1
; printf 函数说明略……
1
2
3
4
5
6
7
8
9
10
11
12
13
// C++源码对比，变量 / 常量（常量值为2的3次方）
printf("nVarOne / 8 = %d", nVarOne / 8);
; 取出被除数放入eax
0040B851 mov eax,dword ptr [ebp-4]
; 扩展eax高位到edx，eax中为负数则edx为0xFFFFFFFF
0040B854 cdq
; 如果eax为负数，则0xFFFFFFFF & 0x00000007 <==> 0x00000007 反之为0
0040B855 and edx,7
; 使用eax加edx，如eax为负数则加7，反之加0
0040B858 add eax,edx
; 将eax右移3位
0040B85A sar eax,3
; printf 函数说明略……
没有打开O2的时候下，以上代码中只有除数为2 的次方值的前提下，才进行了优化处理。我们先从最为较简单的除以常量2的优化开始分析。
上传的附件：
能力值：
( LV4，RANK：50 )
6 楼
上传的附件：
能力值：
( LV4，RANK：50 )
7 楼
上传的附件：
能力值：
( LV4，RANK：50 )
8 楼
回顾代码清单中的关键部分：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
……
; 92492493h疑似
.text:004010AA mov eax, 92492493h
; 这里是流水线优化，esp和上次调用的call指令相关，和除法计算无关，可暂不理会。
.text:004010AF add esp, 8
; 有符号乘法，用esi乘以eax，esi中保存被除数
.text:004010B2 imul esi
; 这里又多出一个诡异的加法
.text:004010B4 add edx, esi
; 右移2位，也可看作除4
.text:004010B6 sar edx, 2
; 结果给eax
.text:004010B9 mov eax, edx
; 负数调整加1
.text:004010BB shr eax, 1Fh
.text:004010BE add edx, eax
.text:004010C0 push edx
.text:004010C1 push offset aNvartwo7D ; "nVarTwo / 7 = %d"
.text:004010C6 call _printf
……
上传的附件：
能力值：
( LV4，RANK：50 )
9 楼
123456
上传的附件：
能力值：
( LV4，RANK：50 )
10 楼
4. 除数为负的非二次方（上） 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
.text:00401000 _main proc near ; CODE XREF: start+AFp
.text:00401000 arg_0= dword ptr 4
.text:00401000 mov ecx, [esp+arg_0]
[B].text:00401004 mov eax, 99999999h[/B]
.text:00401009 imul ecx
.text:0040100B sar edx, 1
.text:0040100D mov eax, edx
.text:0040100F shr eax, 1Fh
.text:00401012 add edx, eax
.text:00401014 push edx
.text:00401015 push offset Format ; "%d\n"
.text:0040101A call _printf
.text:0040101F add esp, 8
.text:00401022 xor eax, eax
.text:00401024 retn
.text:00401024 _main endp
对于负除数求值过程中，有什么需要注意的呢？我们先看看除法转乘法的过程：
上传的附件：
能力值：
( LV4，RANK：50 )
11 楼
5. 除数为负的非二次方（下）
上例中我们讨论了对于Magic Number大于0x7fffffff的处理，那么在什么情况下 Magic Number会小于等于0x7fffffff，而且这个时候应该怎么处理呢？请先阅读以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
.text:00401000 _main proc near ; CODE XREF: start+AFp
.text:00401000 arg_0= dword ptr 4
.text:00401000 mov ecx, [esp+arg_0]
.text:00401004 mov eax, 6DB6DB6Dh
.text:00401009 imul ecx
.text:0040100B sub edx, ecx
.text:0040100D sar edx, 2
.text:00401010 mov eax, edx
.text:00401012 shr eax, 1Fh
.text:00401015 add edx, eax
.text:00401017 push edx
.text:00401018 push offset Format ; "%d"
.text:0040101D call _printf
.text:00401022 add esp, 8
.text:00401025 retn
.text:00401025 _main endp
回忆前面除数等于+7的讨论，对于正除数，Magic Number大于0x7fffffff的处理：
上传的附件：
能力值：
( LV4，RANK：50 )
12 楼
B. 除法优化的原则(上)
看到这里，大家应该注意到以上讨论并还原除数的结果是近似值，说明了我们的公式给出还不够严格，那么我们可以好好思考一下其值近似但不等的原因，先看看余数是多少。
回忆一下除法和余数的关系，根据（性质3），有：
b =(a - r) / q
上传的附件：
能力值：
( LV4，RANK：50 )
13 楼
上传的附件：
能力值：
( LV4，RANK：50 )
14 楼
现在分析一下VC++6.0中计算除法MagicNumber的过程，大家找到VC++6.0 bin目录下c2.dll(版本12.0.9782.0)，先在LoadLibrary下断，等c2加载，其有符号整数除法MagicNumber的计算过程在c2的文件偏移5FACE处，加载后的虚拟地址请读者自行计算，断在此处可以看到有符号整数除法MagicNumber的推算过程，其汇编代码过长，我就不贴了，自己给出F5后修改的C代码，如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 对于除数在3到13之间，直接查表，表结构如下
struct SignedMagicNumber
{
int nMagic;
int nExpInc;
};
// 对于除数为2的幂，有其他处理，故表内无对应值
struct SignedMagicNumber MagicTable[] = {
{1, 1}, // 0
{1, 1}, // 1
{1, 1}, // 2
{0x55555556, 0},
{0, 0}, // 4
{0x66666667, 1},
{0x2AAAAAAB, 0},
{0x92492493, 2},
{0, 0}, // 8
{0x38E38E39, 1},
{0x66666667, 2},
{0x2E8BA2E9, 1},
{0x2AAAAAAB, 1}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 以下代码还原修改自VC++6.0 bin目录下c2.dll(版本12.0.9782.0)，文件偏移5FACE，
// 原程序的返回值定义为结构体，这里修改为参数返回
int GetMagic(unsigned int nDivC, int *nOutExpInc)
{
// if ((int)nDivC >= 3 && nDivC < 13)
// {
// *nOutExpInc = MagicTable[nDivC].nExpInc;
// return MagicTable[nDivC].nMagic;
// }
unsigned int nAbsDivC = abs(nDivC);
int nExcBase = 31;
// t = 2^31 if nDivC > 0
// or t = 2^31 + 1 if nDivC < 0
unsigned int t = (nDivC >> 31) + EXP31;
// |nc| = t - 1 - rem(t, |nDivC|)
unsigned int nLargestMultiple = t - t % nAbsDivC - 1;
unsigned int q1 = EXP31 / nLargestMultiple;
unsigned int r1 = EXP31 - nLargestMultiple * q1;
unsigned int nMagicNumber = EXP31 / nAbsDivC;
unsigned int r2 = EXP31 - nAbsDivC * nMagicNumber;
do
{
r1 *= 2;
q1 *= 2;
++nExcBase;
if ( r1 >= nLargestMultiple )
{
++q1;
r1 -= nLargestMultiple;
}
r2 *= 2;
nMagicNumber *= 2;
if ( r2 >= nAbsDivC )
{
++nMagicNumber;
r2 -= nAbsDivC;
}
}
while ( q1 < nAbsDivC - r2 || q1 == nAbsDivC - r2 && !r1 );
nMagicNumber++;
if ( (int)nDivC < 0 )
nMagicNumber = -(int)nMagicNumber;
*nOutExpInc = nExcBase - 32;
return nMagicNumber;
}
然后写个程序验证一下看看：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
int main(int argc)
{
int nExpInc;
int nMagicNumber;
int nDividend = argc-201; // 这是被除数
int nDivisor = -100; // 这是除数
int nQuotient; // 这里存放商
// GetMagic用来计算magic number，
// 第一个参数指定除数，第二个参数OUT指数相对32的增量
// 这个例子用来模拟计算70 / -7的结果
do
{
nMagicNumber = GetMagic(nDivisor, &nExpInc);
printf("nMagicNumber = 0x%08x, ExpInc = %d\r\n", nMagicNumber, nExpInc);
if (nDivisor >= 0)
{
__asm
{
mov eax, nMagicNumber // 编译器会做成imm寻址，nMagicNumber早已在编译期间算出
mov esi, nDividend
imul esi
// 编译器不会产生这里的跳转，
// 因为编译阶段就计算出nMagicNumber的取值了，
// 所以编译期间就可以决定是否产生其后的add指令,
// nMagicNumber小于0x80000000(负数)则不需增加add
test nMagicNumber, 80000000h
jz NEXT1
add edx, esi
NEXT1:
mov ecx, nExpInc
sar edx, cl
shr esi, 31
add edx, esi
mov nQuotient, edx
}
}
else
{
__asm
{
mov eax, nMagicNumber
mov esi, nDividend
imul esi
test nMagicNumber, 80000000h
jnz NEXT2
sub edx, esi
NEXT2:
mov ecx, nExpInc
sar edx, cl
mov ecx, edx
shr ecx, 31
add edx, ecx
mov nQuotient, edx
}
}
printf("%d / %d = %d\r\n", nDividend, nDivisor, nQuotient);
printf("%d / %d = %d\r\n", nDividend, nDivisor, nDividend / nDivisor);
if (nQuotient != nDividend / nDivisor)
{
puts("Error");
break;
}
nDivisor++;
if (nDivisor == 0 || nDivisor == -1 || nDivisor == 1)
{
nDivisor = 2;
}
nDividend += 10;
}
while(nDivisor <= 100);
return 0;
}
见附件
下次讨论此代码的数学推导
上传的附件：
能力值：
( LV2，RANK：10 )
在线值：
15 楼
前两天上课讲的这么快就放上来了啊？
不知道ImageBase是哪位童鞋啊？
能力值：
( LV2，RANK：10 )
16 楼
占了这么多楼，应该有不少期，我也占楼等学习。
能力值：
( LV2，RANK：10 )
在线值：
17 楼
座等学习
能力值：
( LV4，RANK：50 )
18 楼
7月19日更新章节
能力值：
( LV2，RANK：10 )
19 楼
不错,学习了
能力值：
( LV4，RANK：50 )
20 楼
7月20日更新
能力值：
( LV2，RANK：10 )
在线值：
21 楼
貌似跟vc++没啥关联，标题应该为“浅析C语言对整数除以常量的处理”
能力值：
( LV4，RANK：50 )
22 楼
C语言是规则，具体实现每个厂商的编译器都不同
能力值：
( LV4，RANK：50 )
23 楼
7月21日更新
能力值：
( LV2，RANK：10 )
在线值：
24 楼
说明环境，方便读者测试
占楼学习
能力值：
( LV2，RANK：10 )
25 楼
学习了
前两天上课讲的这么快就放上来了啊？
