原帖由 litaoye 于 2009-3-6 15:38 发表 http://bbs.emath.ac.cn/images/common/back.gif
如果也可以考虑的话,就给了我很大的鼓舞呀!呵呵!再想想!
说个思路,不一定实用!可以先算一下Mod 9,这个好算,数位加和就行了!
这样可以相对在查找2^N的时候可以更明确1些,2^m % 9 是个循环!
不好意思,想错了,想成了单纯的2^m了,再乘上一个数的话,就没规律了!
如果经常需要做这种判断，我想到另外一种方法。
比如需要判断这个整数n被5的最多几次方整除。
我们可以事先保存一个整数$2^h$的10进制表示，其中h足够大,但是(2^h应该同整数n差不多大)
我们可以计算$n*2^h$,然后判断乘积后面有几个0就可以了。
这倒是一个不错的算法。:b:
10^3约等于2^10，大概就可以判定了吧
突然想到，几千年前
欧几里德
就把你这个问题想好了：
UINT32 getMax2Exp( const UINT32 * a, SIZE_T n ){
int l=n*9
l*=log(10)/log(2) ；//a的2进表示的最大位数
UINT32 M=1<<l；//2^l次幂的1000000000进制表示
return gcd(a,M)；//答案
}
最大公约数算法，收敛超快，这比以上各位的速度快吧！
用最大公约数的算法，应该更慢。
如果求一个10进制大数与2的整数次幂（指数足够大）的公约数，
我宁愿将其转化为本话题的快速算法，而不是反其道而行之。
特翻书，找GCD的复杂度
假设a的10进制位数是n
只需进行对数级次数的除法运算
则绝不会超过4.8*n-0.32次除法运算
而 平均是
1.9405*n次除法运算。
不过除法操作的两个数越来越小
这个问题是个特定问题，应该用更简洁更高效的算法。
你可以看看 5# 里提出的问题，若用GCD，肯定非常不划算。
25# ssikkiss
这里，你可能还忽略了一个问题，n 通常会比较大，比如 n=10000，
那么 l=33219（也许还得+1），此时 M 是无法用 UINT32 表达的，
而在十进制中，2^l 计算并不是如2进制移位那么快就可完成的。
除了移位判断，我实在没其他的招数了。
不过，对于此题，用大一统的GCD算法的确是没有充分利用2的幂这个特殊条件