gxqcn 发表于 2009-2-18 21:00:50

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

Input：正整数 n，取值范围为 $$（或 $$），
Return：若为10的整数次幂，则返回幂指数；否则返回零。#ifdef WIN64
typedef UINT64      OSUINT
#else
typedef UINT32      OSUINT
#endif

OSUINT __fastcall get10exp( OSUINT n /* 2 <= n <= (OSUINT)(-1) */ );一贯地，追求效率，无论什么语言、汇编指令均可上场。:)

gxqcn 发表于 2009-2-18 21:05:33

看无心人闲得发慌（来点复杂的吧），特抛一个小题目。

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

类似地，也可一并考虑为2的多少次整数幂（这个相对简单得多）：OSUINT __fastcall get2exp( OSUINT n /* 2 <= n <= (OSUINT)(-1) */ );或5的多少次幂：OSUINT __fastcall get5exp( OSUINT n /* 2 <= n <= (OSUINT)(-1) */ );

liangbch 发表于 2009-2-18 21:23:22

这个类似我那个帖子：http://bbs.emath.ac.cn/thread-1195-1-1.html

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

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

bc=log2(n);
if ( n==a )
return b
else
return 0;

gxqcn 发表于 2009-2-18 21:39:30

确实与求“某进制下的位数”问题有点渊源。
但又略有不同，其绝大多数情况下将返回0

mathe 发表于 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;
}

gxqcn 发表于 2009-2-19 08:08:06

get_times_of_2() 函数应该象这么定义比较好：__declspec(naked)
UINT32 __fast get_times_of_2( UINT32 x /* x>0 */ )
{
    __asm   bsf   eax, ecx;
    __asm   ret;
}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
            and edx, ecx
            xchg eax, ecx
            shr edx, cl
            xchg eax, ecx
            neg edx
            and eax, edx
            ret            
      }
}

gxqcn 发表于 2009-2-19 08:19:22

我怎么觉得应该是用 bsf 而不是 bsr 指令啊？
（我特意在 6# 修改过来的）

无心人 发表于 2009-2-19 09:10:48

是bsr

gxqcn 发表于 2009-2-19 09:26:18

我揣摩 mathe 的 get_times_of_2(x) 的本意是得到 x 的二进制数后面连续有多少个bit为0，
所以应该用 bsf 而不是 bsr.
页: [1] 2
查看完整版本: 快速判断是否为10的整数次幂并计算幂次