快速判断是否为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
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.