请教一下关于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 ;
   
10.    
    
11.     shl eax, 5
    
12.     sub n, eax ;
    
13.   }
    
14.   
    
15.   return n;
    
16. }
    
17. 
    
18. int func1(int n)
    
19. {
    
20.   return n % 32;
    
21. }
    
22. 
    
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.   }
    
38.   
    
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吧。