如何使用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³² / n)。考虑两种可能的情况：

n不是2的幂。在这种情况下，n不是2³²的因子，并且除法的上限恰好是地板的一个。而且，（使用截断整数除法，如在C或Java中）floor(2³² / n) == floor((2³² - 1) / n)。因此，所需的步骤是(2³² - 1)/n + 1。
n是2的幂。在这种情况下，n精确地划分2³²，因此(2³² - 1) / n将比2³² / n少一个。因此，所需的步骤是(2³² - 1)/n + 1。方便地，这与第一种情况中的值相同。

注意：正如@greybeard在评论中指出的那样，如果n > 2¹⁶，则无法保证存在适当的步长。对于较大的n，上述过程将计算最大步长，以确保在步骤n之前不会发生溢出。

Answer 2

如果您使用C作为编程语言，则可以使用其无符号算术。考虑以下：

floor(2³² / n) = floor((2³² - n) / n + 1)

如果你的n有一个无符号类型（例如uint32_t），那么数学表达式2³² - n可以简单地计算为-n。

所以在C：

uint32_t n = ...;
uint32_t d = (-n) / n + 1;

或者：

uint32_t d = (0 - n) / n + 1;

你应该记录好，因为这是非常模糊的代码。