整数运算：UINT_MAX加1除以n不溢出

Question

有没有办法计算((UINT_MAX+1)/x)*x-1的结果在 C 中而不求助于 unsigned long（其中 x 是 unsigned int）？（相应 "without resorting to unsigned long long" 取决于体系结构。）

Answer 1

sizeof(unsigned long) == sizeof(unsigned int) == 4 在大多数现代编译器上。您可能想使用 use unsigned long long。

Answer 2

对于整数除法，我们有以下等价关系

(y/x)*x == y - y%x

所以我们有

((UINT_MAX+1)/x)*x-1 == UINT_MAX - (UINT_MAX+1)%x

将此结果与以下等价组合

(UINT_MAX+1)%x == ((UINT_MAX % x) +1)%x

我们得到

((UINT_MAX+1)/x)*x-1 == UINT_MAX - ((UINT_MAX % x) +1)%x

可以用 unsigned int 计算。

Answer 3

算术比较简单:

((UINT_MAX + 1) / x) * x - 1 =
((UINT_MAX - x + x + 1) / x) * x - 1 = 
((UINT_MAX - x + 1) / x + 1) * x - 1 =
(UINT_MAX - x + 1) / x) * x + (x - 1)

Integer arithmetic: Add 1 to UINT_MAX and divide by n without overflow