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

Question

3

我有一个32位的计时器，希望经过n个步骤后它会溢出。这意味着每一步应该是(2^32)/n。然而，如果我尝试使用32位整数计算这个数字，编译器会抱怨(1<<32)比我正在使用的类型更大。

我可以通过做像(~0)/n这样的事情来接近我要寻找的答案。然而，当n是2的幂时，这种情况会让我感到不安，因为在这些情况下，计时器需要多走一步才能溢出。

是否有一个简单的表达式，只使用32位整数就能计算出(2^32)/n？

- Michael Cooper

2

你想如何舍入结果？如果你向0舍入，那么当n=3时计时器将在第4步溢出。 - user2357112

(2^32)/n = 2*((2^31)/n) - Scott Hunter

@ScottHunter - 不使用整数算术。例如(2 ^ 32) / 3 = 1431655765 <> 2 * ((2 ^ 31) / 3) = 1431655764。 - Joe

1

@user2357112 说得有道理。我想我会选择向上取整，或者计算 (2^32+n-1)/n。 - Michael Cooper

这似乎是一个XY问题：为了尽可能均匀地分配步骤并尽可能接近2^32而不是零，请查看Bresenham算法。 - greybeard

2个回答

1

如果您使用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;

你应该好好记录它，因为这段代码真的很难懂。

- anatolyg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

如果要让计数器在第n步（如果可能的话）精确溢出，则需要计算ceil(2³² / n)。考虑两种可能的情况：

n不是2的幂。在这种情况下，n不是2³²的因数，除法的上舍入值恰好比下舍入值多1。此外，（使用截断整数除法，例如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步之前不会溢出的最大步长。