algorithm - 如何使用 32 位整数计算 (2^32)/n

Question

我有一个 32 位定时器，我想在 n 步后溢出。这意味着每一步应该是 (2^32)/n。但是，如果我尝试使用 32 位整数计算此数字，编译器会提示 (1<<32) 大于我正在使用的类型。

通过执行类似 (~0)/n 的操作，我可以非常接近我正在寻找的答案。然而，令我烦恼的是，在这种情况下，当 n 是 2 的幂时，我不会得到正确的答案，这意味着在这些情况下，计时器溢出需要一个额外的步骤。

是否有一个简单的表达式可以仅使用 32 位整数来计算 (2^32)/n？

Answer 1

如果您希望计数器恰好在第 n 步溢出(如果可能的话)，那么您需要计算 ceil(2<sup>32</sup> / n) .考虑两种可能的情况:

1. n 不是 2 的幂。在这种情况下，n 不是 2<sup>32</sup> 的因数。 ，而师的天花板恰好比地板多一个。此外，(使用截断整数除法，如在 C 或 Java 中)floor(2<sup>32</sup> / n) == floor((2<sup>32</sup> - 1) / n) .所以所需的步骤是 (2<sup>32</sup> - 1)/n + 1 .

2. n 是 2 的幂。在这种情况下，n 精确地整除 2<sup>32</sup>。 ，等等 (2<sup>32</sup> - 1) / n会比2<sup>32</sup> / n少一.所以所需的步骤是 (2<sup>32</sup> - 1)/n + 1 .方便的是，这与第一种情况下的值相同。

注意:正如@greybeard 在评论中指出的那样，如果n > 2<sup>16</sup>，则不能保证存在适当的步长。 .对于更大的 n , 上述过程将计算最大步长，保证在步 n 之前不会发生溢出。 .