objective-c - 查找数字的下一个倍数的快速方法

Question

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

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

最后，“multiple”将具有numberafter的第一个倍数baseNumber。问题是当number变得太大时，迭代次数变得太多。所以我的问题是：有没有更快的方法来做到这一点？

Answer 1

如果一切都保证是积极的，请尝试

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

这是在恒定时间内完成的。

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

ifbaseNumber可以是负数（但number仍然是正数），我们面临的问题multiple % number是 if 可能是负数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，您必须使用模数运算对其进行测试。

Answer 3

为什么需要循环？

倍数 = (楼层(number/baseNumber)+1)*baseNumber

Answer 4

 while(multiple * number < baseNumber)
      multiple++;

所以对于 baseNumber = 3，number = 7，你的倍数是 3；

不过，有些事情告诉我bignums即将出现在这里。