快速找到下一个数字的倍数

Question

我需要找到从基数开始的数字的第一个倍数.例如:7中3的第一个倍数是9.我的第一次尝试是这样做:

multiple = baseNumber
while(multiple%number !=0 )
    multiple++

最后,"多",将有第一个多number之后baseNumber.问题是当number变得太大时,迭代次数变得太多.所以我的问题是:有更快的方法吗？

Answer 1

如果一切都保证是积极的,试试吧

multiple = baseNumber + number - 1;
multiple -= (multiple % number);

这是在恒定的时间.

首先,我们添加number - 1以确保我们的数字至少与下一个数字一样大但小于之后的数字.然后我们减去除法的余数,number以确保我们有所需的倍数.

如果baseNumber可能是负面的(但number仍然是正面的),我们面临的问题multiple % number可能是负面的,如果multiple < 0,所以上面可以跳过多个number.为了避免这种情况,我们可以使用例如

remainder = multiple % number;
if (remainder < 0) remainder += number;
multiple -= remainder;

如果分支太昂贵,我们可以避免if以两个部门而不是一个部门为代价,

multiple -= (number + (multiple % number)) % number;

但一般来说,if似乎更可取.

如果number可以为负数,请先将其替换为绝对值.

注意:如上所述,baseNumber如果已经是多个,则返回上面的返回值number.如果不需要,请删除- 1第一行.

Answer 2

试试这个（需要整数除法）：

multiple = ((base/number) + 1) * number;

7/3 = 2。3*(2+1) = 9。

您有一个边缘情况，其中baseNumber已经是 的倍数number，您必须使用模运算来测试它。