数学研发论坛

 找回密码
 欢迎注册
楼主: gxqcn

[擂台] 求bit位为1数目不超出2的正整数

[复制链接]
发表于 2009-2-3 17:11:50 | 显示全部楼层
说明一下,表中对8个位中有两个1的数据,预先存好返回值,这样先检测前8位,只有9/256的数据需要继续检测后面
如果有一个1,也存好相应值
由于预先算好,于是程序执行主要是寻址
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 17:13:31 | 显示全部楼层
原帖由 无心人 于 2009-2-3 17:08 发表


   你认为这么复杂的代码比我的汇编要高效么?
   况且,最终的代码的适用范围要比GxQ题目要求的大
   只要是1-2^32-2就可以

效率和代码复杂性的关系是这样的么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 17:18:21 | 显示全部楼层
可能是比不过你们的,毕竟用内存和寄存器是有较大差别的,不好说,我觉得这个得试试
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 19:27:20 | 显示全部楼层
从翻译后的汇编语句的行数就肯定要比我的多很多了啊
而且这么多比较和分支
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 20:44:18 | 显示全部楼层
试了一下,比你们的慢10倍
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 20:53:17 | 显示全部楼层


   那个,你比较了时间, 哪组汇编快???
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-3 21:11:19 | 显示全部楼层

GxQ 的版本

  1. typedef unsigned int UINT32;

  2. const UINT32 POW2[] = { 0, 1UL, 1UL<<1, 1UL<<2, 1UL<<3,
  3.                         1UL<<4,  1UL<<5,  1UL<<6,  1UL<<7,
  4.                         1UL<<8,  1UL<<9,  1UL<<10, 1UL<<11,
  5.                         1UL<<12, 1UL<<13, 1UL<<14, 1UL<<15,
  6.                         1UL<<16, 1UL<<17, 1UL<<18, 1UL<<19,
  7.                         1UL<<20, 1UL<<21, 1UL<<22, 1UL<<23,
  8.                         1UL<<24, 1UL<<25, 1UL<<26, 1UL<<27,
  9.                         1UL<<28, 1UL<<29, 1UL<<30, 1UL<<31 };

  10. __declspec(naked)
  11. UINT32 GreaterEqualBit2_57F( UINT32 n /* 1 <= n <= 2^31+2^30 */ )
  12. {
  13.     __asm
  14.     {
  15.         lea     edx, dword ptr[POW2+0x04];
  16.         mov     eax, dword ptr[esp+0x04];

  17.         bsr     ecx, eax;
  18.         mov     ecx, dword ptr[edx+ecx*0x04];
  19.         push    ecx;

  20.         xor     eax, ecx;
  21.         mov     ecx, -1;
  22.         bsr     ecx, eax;
  23.         mov     ecx, dword ptr[edx+ecx*0x04];

  24.         lea     edx, [ecx*0x02];
  25.         xor     eax, ecx;
  26.         cmovne  ecx, edx;

  27.         pop     eax;
  28.         add     eax, ecx;

  29.         ret;
  30.     }
  31. }
复制代码
15条指令,无移位运算(用查表法)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-3 21:11:25 | 显示全部楼层
  1. __declspec(naked)
  2. UINT32 GreaterEqualBit2_58F( UINT32 n /* 1 <= n <= 2^31+2^30 */ )
  3. {
  4.     __asm
  5.     {
  6.         mov     edx, dword ptr[esp+0x04];
  7.         mov     eax, 1;

  8.         bsr     ecx, edx;
  9.         shl     eax, cl;
  10.         push    eax;

  11.         xor     edx, eax;
  12.         bsr     ecx, edx;
  13.         mov     eax, 0;
  14.         setne   al;
  15.         shl     eax, cl;

  16.         lea     ecx, [eax*0x02];
  17.         xor     edx, eax;
  18.         cmovne  eax, ecx;

  19.         pop     edx;
  20.         add     eax, edx;

  21.         ret;
  22.     }
  23. }
复制代码
移位(不查表)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-3 21:11:30 | 显示全部楼层
  1. __declspec(naked)
  2. UINT32 GreaterEqualBit2_59F( UINT32 n /* 1 <= n <= 2^31+2^30 */ )
  3. {
  4.     __asm
  5.     {
  6.         push    ebx;
  7.         mov     ebx, dword ptr[esp+0x08];

  8.         bsr     ecx, ebx
  9.         mov     eax, 1
  10.         shl     eax, cl

  11.         xor     ebx, eax
  12.         xor     edx, edx
  13.         bsr     ecx, ebx
  14.         setne   dl
  15.         shl     edx, cl
  16.         add     eax, edx

  17.         xor     ecx, ecx
  18.         sub     ebx, edx
  19.         cmovne  ecx, edx

  20.         add     eax, ecx

  21.         pop     ebx;

  22.         ret;
  23.     }
  24. }
复制代码
(改编自无心人的 36#)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-3 21:17:55 | 显示全部楼层

测试结果

在 Intel P4 2.93GHz CPU 上,对 n 从 1 到 2147483648 进行测试,运行时间如下:
24#: 25 s
36#: 35 s
57#: 25 s
58#: 32 s
59#: 27 s

在 AMD Athlon 64 3200+ 上测试则为:
24#: 40 s
36#: 37 s
57#: 37 s
58#: 36 s
59#: 38 s

注:24# 为 liangbch 所写;36# 为 无心人 所写;后3个则为 GxQ 所写。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-8-25 23:36 , Processed in 0.050287 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表