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

litaoye · 发表于 2009-3-6 15:41:01

原帖由 litaoye 于 2009-3-6 15:38 发表
如果也可以考虑的话,就给了我很大的鼓舞呀!呵呵!再想想!

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

不好意思,想错了,想成了单纯的2^m了,再乘上一个数的话,就没规律了!

mathe · 发表于 2009-3-6 19:17:47

如果经常需要做这种判断，我想到另外一种方法。
比如需要判断这个整数n被5的最多几次方整除。
我们可以事先保存一个整数$2^h$的10进制表示，其中h足够大,但是(2^h应该同整数n差不多大)
我们可以计算$n*2^h$,然后判断乘积后面有几个0就可以了。

gxqcn · 发表于 2009-3-7 21:32:58

这倒是一个不错的算法。

qianyb · 发表于 2009-11-23 17:35:35

10^3约等于2^10，大概就可以判定了吧

ssikkiss · 发表于 2010-6-30 00:48:28

突然想到，几千年前
欧几里德
就把你这个问题想好了：

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)；//答案

}
最大公约数算法，收敛超快，这比以上各位的速度快吧！

gxqcn · 发表于 2010-6-30 07:56:35

用最大公约数的算法，应该更慢。

如果求一个10进制大数与2的整数次幂（指数足够大）的公约数，
我宁愿将其转化为本话题的快速算法，而不是反其道而行之。

ssikkiss · 发表于 2010-6-30 08:40:36

特翻书，找GCD的复杂度
假设a的10进制位数是n
只需进行对数级次数的除法运算
则绝不会超过4.8*n-0.32次除法运算
而平均是
1.9405*n次除法运算。
不过除法操作的两个数越来越小

gxqcn · 发表于 2010-6-30 08:46:12

这个问题是个特定问题，应该用更简洁更高效的算法。

你可以看看 5# 里提出的问题，若用GCD，肯定非常不划算。

gxqcn · 发表于 2010-6-30 09:13:47

25# ssikkiss

这里，你可能还忽略了一个问题，n 通常会比较大，比如 n=10000，
那么 l=33219（也许还得+1），此时 M 是无法用 UINT32 表达的，
而在十进制中，2^l 计算并不是如2进制移位那么快就可完成的。

wayne · 发表于 2010-6-30 09:47:50

除了移位判断，我实在没其他的招数了。
不过，对于此题，用大一统的GCD算法的确是没有充分利用2的幂这个特殊条件

账号		自动登录	找回密码
密码			欢迎注册

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