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

gxqcn

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. 
   
7. OSUINT __fastcall get10exp( OSUINT n /* 2 <= n <= (OSUINT)(-1) */ );

复制代码

一贯地，追求效率，无论什么语言、汇编指令均可上场。

gxqcn

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

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

类似地，也可一并考虑为2的多少次整数幂（这个相对简单得多）：

1. OSUINT __fastcall get2exp( OSUINT n /* 2 <= n <= (OSUINT)(-1) */ );

复制代码

或5的多少次幂：

1. OSUINT __fastcall get5exp( OSUINT n /* 2 <= n <= (OSUINT)(-1) */ );

复制代码

liangbch

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

算法
对于数n，若bc=log2(n), (对于UINT32，bc=0..31，则可根据bc造表，见下)

Bit 数（bc)	数的范围	参照数	是10的几次方
0	1	1	0
1	2-3	0	--
2	4-7	0	--
3	8-15	10	1
4	16-31	0	--
5	32-63	0	--
6	64-127	100	2
7	128-255	0	--

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

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

gxqcn

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

mathe

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

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 的算法我也曾想到过，但不知是否还有更奇妙的算法？

无心人

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            
        }
  }

gxqcn

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

无心人

是bsr

gxqcn

我揣摩 mathe 的 get_times_of_2(x) 的本意是得到 x 的二进制数后面连续有多少个bit为0，
所以应该用 bsf 而不是 bsr.