如何使用 32 位整数计算 (2^32)/n
How to compute (2^32)/n using 32-bit integers
我有一个 32 位定时器，我想在 n 步后溢出。这意味着每一步应该是 (2^32)/n。但是，如果我尝试使用 32 位整数计算此数字，编译器会抱怨 (1<<32) 大于我使用的类型。
通过执行类似 (~0)/n 的操作，我可以非常接近我正在寻找的答案。然而，令我烦恼的是，在这种情况下，当 n 是 2 的幂时，我不会得到正确的答案，这意味着在这些情况下，计时器溢出需要额外的一步。
是否有仅使用 32 位整数计算 (2^32)/n 的简单表达式？
如果您希望计数器正好在第 n 步溢出（如果可能的话），那么您需要计算 ceil(2<sup>32</sup> / n )。考虑两种可能的情况：
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.
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[，则无法保证存在适当的步长大小=43=]。对于较大的n，上述过程将计算最大步长，保证在n.
步之前不会发生溢出。
如果您使用 C 作为编程语言，则可以使用其无符号算术。考虑以下因素：
floor(232 / n) = floor((232 - n) / n + 1)
如果您的 n 是无符号类型（例如 uint32_t），那么数学表达式 2<sup>32</sup> - n 可以简单地计算为 -n.
所以在 C:
uint32_t n = ...;
uint32_t d = (-n) / n + 1;
或者：
uint32_t d = (0 - n) / n + 1;
你应该好好记录一下，因为这确实是晦涩难懂的代码。
我有一个 32 位定时器，我想在 n 步后溢出。这意味着每一步应该是 (2^32)/n。但是，如果我尝试使用 32 位整数计算此数字，编译器会抱怨 (1<<32) 大于我使用的类型。
通过执行类似 (~0)/n 的操作，我可以非常接近我正在寻找的答案。然而，令我烦恼的是，在这种情况下，当 n 是 2 的幂时，我不会得到正确的答案，这意味着在这些情况下，计时器溢出需要额外的一步。
是否有仅使用 32 位整数计算 (2^32)/n 的简单表达式？
如果您希望计数器正好在第 n 步溢出（如果可能的话），那么您需要计算 ceil(2<sup>32</sup> / n )。考虑两种可能的情况：
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.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[，则无法保证存在适当的步长大小=43=]。对于较大的n，上述过程将计算最大步长，保证在n.
如果您使用 C 作为编程语言，则可以使用其无符号算术。考虑以下因素：
floor(232 / n) = floor((232 - n) / n + 1)
如果您的 n 是无符号类型（例如 uint32_t），那么数学表达式 2<sup>32</sup> - n 可以简单地计算为 -n.
所以在 C:
uint32_t n = ...;
uint32_t d = (-n) / n + 1;
或者：
uint32_t d = (0 - n) / n + 1;
你应该好好记录一下，因为这确实是晦涩难懂的代码。