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

mathe

我觉得直接10进制转2进制已经不错了

无心人

那这个帖子也可以结束了
呵呵

我想，算法就是先得到10进制末尾的0
10移位去掉0

再根据进制测试末位的2的幂次

如果达到最大，再考虑2移位测试

没有则直接结束

gxqcn

谢谢大家。

其实我当前能想到的算法也是大家所说的，
把这个问题抛出来，只是想看看是否还存在特别精妙的算法。

把一个大整数转化成二进制形式是很快的，
也就是说当前的算法 getMax2Exp 是可行的，
但若求 getMax5Exp 呢？

即：如何快速计算一个大整数最多可被5的多少次方整除？

无心人

也是我说的思路吧

先根据末尾确定一个幂

再根据最后若干位确定小幂次
一旦达到最大幂次
比如8或者9
再测试高位

无非是用5除

litaoye

原帖由 无心人 于 2009-3-4 17:53 发表
楼上的想法完全不可行啊

是吗?那就PASS掉好了!我也只是瞎猜一下!呵呵!

gxqcn

litaoye 的二分法思想也是可以考虑的。

但最好修正成 2^9、2^18、2^36、。。。这样的序列。

算法可以这样设计：
1、s = 数组A前端元素连续为0的个数；k = 1；
2、r = a、a[s+1]、。。。、a[s+k-1] 构成的大数最多可被2整除的次数
3、若 r >= 9*k 且 s+k<n，则 k = 2*k，goto 2；
4、否则，return (9*s + r)

其中第2步可以避免大整数高位的无效计算。

kon3155

我觉得二分法也是可以的，因为问题本质上是一个在有序数列中查找某个数的问题，无疑二分法是最快的。

无心人

写出代码比较下

我想99%可能是在最末字即结束
所以看具体输入的数值的分布

gxqcn

如果是在上述假设前提下，
16# 的算法就更具优势。

litaoye

如果也可以考虑的话,就给了我很大的鼓舞呀!呵呵!再想想!

说个思路,不一定实用!可以先算一下Mod 9,这个好算,数位加和就行了!
这样可以相对在查找2^N的时候可以更明确1些,2^m % 9 是个循环!