快速计算一个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进制移位也不慢吧

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......,试到不行,再在相应的区间作二分?

无心人

楼上的想法完全不可行啊