数学研发论坛

 找回密码
 欢迎注册
查看: 3331|回复: 16

[擂台] 快速判断是否为10的整数次幂并计算幂次

[复制链接]
发表于 2009-2-18 21:00:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
Input:正整数 n,取值范围为 $[2, 2^32-1]$(或 $[2, 2^64-1]$),
Return:若为10的整数次幂,则返回幂指数;否则返回
  1. #ifdef WIN64
  2. typedef UINT64      OSUINT
  3. #else
  4. typedef UINT32      OSUINT
  5. #endif

  6. OSUINT __fastcall get10exp( OSUINT n /* 2 <= n <= (OSUINT)(-1) */ );
复制代码
一贯地,追求效率,无论什么语言、汇编指令均可上场。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-18 21:05:33 | 显示全部楼层
看无心人闲得发慌(来点复杂的吧),特抛一个小题目。

这个问题在大数的基数转换(进制转换)中,将决定是否可用快速算法。

类似地,也可一并考虑为2的多少次整数幂(这个相对简单得多):
  1. OSUINT __fastcall get2exp( OSUINT n /* 2 <= n <= (OSUINT)(-1) */ );
复制代码
或5的多少次幂:
  1. OSUINT __fastcall get5exp( OSUINT n /* 2 <= n <= (OSUINT)(-1) */ );
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-18 21:23:22 | 显示全部楼层
这个类似我那个帖子:/thread-1195-1-1.html

算法
对于数n,若bc=log2(n), (对于UINT32,bc=0..31,则可根据bc造表,见下)
Bit 数(bc)数的范围参照数是10的几次方
0110
12-30--
24-70--
38-15101
416-310--
532-630--
664-1271002
7128-2550--


则有如下算法:
将表格第3列表示为数组a, 表格第4列表是为数组b,则有如下算法

bc=log2(n);
if ( n==a[bc] )
  return b[bc]
else
  return 0;
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-18 21:39:30 | 显示全部楼层
确实与求“某进制下的位数”问题有点渊源。
但又略有不同,其绝大多数情况下将返回0
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-18 22:32:01 | 显示全部楼层
int a[]={1,10,100,1000,10000,100000,...};

int get_times_of_2(int x){
    asm{ bsr x, eax}
}
int get10exp(int x)
{
     int b=get_times_of_2(x);
    return (-(a[ b ]==x))&b;
}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-19 08:08:06 | 显示全部楼层
get_times_of_2() 函数应该象这么定义比较好:
  1. __declspec(naked)
  2. UINT32 __fast get_times_of_2( UINT32 x /* x>0 */ )
  3. {
  4.     __asm   bsf     eax, ecx;
  5.     __asm   ret;
  6. }
复制代码
mathe 的算法我也曾想到过,但不知是否还有更奇妙的算法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-19 08:16:12 | 显示全部楼层
mathe程序翻译为
  int a[]={1,10,100,1000,10000,100000,...};

  __declspec(naked)
   __fastcall int get10exp(int x)
  {
        __asm
        {
            bsr eax, ecx
            movd edx, dword ptr [a + eax * 4]
            and edx, ecx
            xchg eax, ecx
            shr edx, cl
            xchg eax, ecx
            neg edx
            and eax, edx
            ret            
        }
  }
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-19 08:19:22 | 显示全部楼层
我怎么觉得应该是用 bsf 而不是 bsr 指令啊?
(我特意在 6# 修改过来的)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-19 09:10:48 | 显示全部楼层
是bsr
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-19 09:26:18 | 显示全部楼层
我揣摩 mathe 的 get_times_of_2(x) 的本意是得到 x 的二进制数后面连续有多少个bit为0,
所以应该用 bsf 而不是 bsr.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-8-19 22:40 , Processed in 0.058753 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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