请教一下关于VC处理对2的幂取模的问题

backer

对2的幂取模，按理说利用余数 = 被除数 - 商*2^k就可以了，而有符号数对2的k次方求商应该也很高效： mov eax, 被除数 cdq and edx,1F add eax,edx sar eax,5 ;这时eax已经得到了商 shl eax, k sub 被除数, eax ;此时可以得到余数 以上可以实现无分支取模 在VC6里面，其实现为如下代码： 00401000 mov eax,dword ptr ss:[esp+4] ;[esp+4]保存了被除数 00401004 mov ecx,eax 00401006 and ecx,8000001F 0040100C jns short TestDiv.00401013 0040100E dec ecx 0040100F or ecx,FFFFFFE0 00401012 inc ecx 00401013 push ecx 00401014 push 20 00401016 push eax 00401017 push TestDiv.004130D8 ; ASCII "%d %% %d = %d" 0040101C call TestDiv.004010B0 00401021 add esp,10 其实现产生了分支语句，明显效率不高，请教一下这样的处理是否有其他考虑呢？

backer

我就纳闷，无论是周期总和还是流水线问题，VC的写法都不高效啊，我还开了O2的，可能他们考虑到某些我没想到的方面吧。 写了个程序测试一下，看看在有符号数值范围内有没有某个特殊的数值存在问题。

1. int MyModBy32(int n)
2. {
3. __asm
4. {
5. mov eax, n
6. cdq
7. and edx,0x1F
8. add eax,edx
9. sar eax,5 ;
11. shl eax, 5
12. sub n, eax ;
13. }
15. return n;
16. }
18. int func1(int n)
19. {
20. return n % 32;
21. }
23. int _tmain(int argc, _TCHAR* argv[])
24. {
25. int r1, r2;
26. for (int i = 1; i; i++)
27. {
28. r1 = func1(i);
29. r2 = MyModBy32(i);
30. printf("%d %% %d = %d\r\n", i, 32, r1);
31. printf("%d %% %d = %d\r\n", i, 32, r2);
32. if (r1 != r2)
33. {
34. puts("error");
35. break;
36. }
37. }
39. system("pause");
40. return 0;
41. }

复制代码

backer

VC产生的代码中，其原理貌似也简单，在对有符号数求余的时候，VC规定余数的符号由被除数决定，使得满足公式“余数 = 被除数 - 商*除数”，于是遇到一个问题，也就是负余数的处理。对于2的k次方取余来说，大多数余数的值只需取得被除数二进制数值中的最后k位的值即可，负数则还需k位之前补1，于是可以的到以下代码，设k为5： mov reg, 被除数 and reg,8000001F jns LAB1 or reg, FFFFFFE0 LAB1: 以上代码对余数非0是没有问题的，但是如果余数为0，则按以上代码计算结果为FFFFFFE0，是错误的，于是加以调整，调整办法为or运算前后减一加一。对于余数不为0的，此调整不影响计算结果；对于余数为0的，末尾k位全部为0值，此时减一得到末尾k位为1，or运算得到-1，最后加一得到余数值为0，调整后的代码如下： mov reg, 被除数 and reg,8000001F jns LAB1 dec reg or reg, FFFFFFE0 inc reg LAB1: 本人非数学专业，研究数学是工作之余的兴趣爱好，以上言论也不能算是严密的数学论证，最多只是猜测。论坛数学高手如云，故前来请教一二，若猜测有误，望不吝指点。

backer

不知道是怎么回事，写帖子内容的文本框很小，截图无法上传。

gxqcn

不知道是怎么回事，写帖子内容的文本框很小，截图无法上传。 backer 发表于 2010-7-28 01:59

你可点“高级回复”模式，如觉窗口不够大，右上角还有最大化、新开窗口等按钮。 在“高级回复”模式里下面有个“添加附件”链接，点一下即可上传附件（注意，单个附件不得超过500KB）。

backer

backer

点附件没有反映，惭愧，完全不懂网页方面

gxqcn

你的IE版本太老了，请升级一下；或安装Firefox吧。