快速计算一个10进制整数最多可被2的多少次方整除？

gxqcn

比方说：
419430400 最多可被 2^24 整除；
450971566080 最多可被 2^32 整除；
2163588753756626385312110347721554337464320 最多可被 2^65 整除；

这里的整数可能是超大整数，可以达到数百万位以上级的。

既然涉及到大整数，我们不妨先暂时统一规定一下其表达方式。

注意题目中说的“10进制”，
其实仅仅是代表一种便于人们理解其值大小的表达方式，
实际上可以为 10^3 进制，或 10^9 进制等。
也就是每三位或每九位分段表示（适当减少分段数目可减少运算次数）。

现在假定是以 b=1000000000 进制表达大整数 A 为 $a_i ( 0 <=i<=n )$，
即 $A = \sum_{i=0}^{n}(a_i*b^i)$
现在要求如下结果：

1. UINT32 getMax2Exp( const UINT32 * a, SIZE_T n );

复制代码

当然比较传统也比较笨的算法是不停的除以2，直到为奇数时停止；
或直接将该大整数直接转换成2进制表达，然后数尾部连续有多少个“0”；

现在的问题是：请设计一个比较高效的算法，快速得到该值。
（大家在思考这个问题的同时，还可一并考虑 getMax5Exp 的类似问题）

以算法的数学原理讨论为主，伪代码亦可接受。

无心人

首先数末尾多少〇

然后

假设，除去〇的数字以

b = 100000000

表示

从低位起

测试，低位的最高到2^8的幂

如果小于2^8则结束

否则，整体左移位8

重复

gxqcn

最好避免有“整体”“移位”过程，
因为“10^9进制”大整数的“移位”针对10^k很快，若针对2^k则差多了。

无心人

好像免不掉

gxqcn

也可换个角度看这个问题：
　　即便是免不了“移位”运算，可否尽量减少数组里参与“移位”运算的元素？

比方说，对 10000000000000000...(1000000个0)14294967296000000000000000000000000000 (27个0)
其答案是：37，
如果说可以事先判断出前面若干位数字对结果不产生影响，我们就可以避免它们参与运算，从而节省大量时间。

问题是：如何快速去判断（或预估）前面多少数字段确实对结果无任何影响？

无心人

考虑30%长度如何？？

我3#考虑的就是部分结果
按照概率，遇到遍历整个数字的情况是很少的

无心人

5#的想法是不现实的
假设n = 2^65536
显然，必须考虑所有的长度

呵呵

无心人

好像10进制移位也不慢吧

1. 
   
2.     #define base 100000000
   
3.     unsigned int n[128];
   
4.     unsigned int t = 0;
   
5.     for (i = 127; i >= 0; i --)
   
6.       {
   
7.       if (t > 0)   n[i] += t;
   
8.       if (n[i] & 1) t = base; else t = 0;
   
9.        n[i] >>= 1;
   
10.       }
    

复制代码

litaoye

用二分可以么?比如先试2^2,2^4, 2^8......,试到不行,再在相应的区间作二分?

无心人

楼上的想法完全不可行啊