安全地添加整数，并certificate安全性

编程课程作业要求

• 写一个（安全）函数，添加两个整数，和
• 表明该function是安全的。

以下代码代表我的解决方案。 我不是C标准（或正式validation方法）的专家。 所以我想问：有更好（或不同）的解决方案吗？

谢谢

#include  /* Try to add integers op1 and op2. Return 0 (success) or 1 (overflow prevented). In case of success, write the sum to res. */ int safe_int_add(int * res, int op1, int op2) { if (op2  op2 */ /* 0 < - op2 */ /* INT_MIN < - op2 + INT_MIN */ /* INT_MIN < INT_MIN - op2 */ /* INT_MIN = INT_MIN */ /* - op2 <= - INT_MIN */ /* INT_MIN - op2 <= - INT_MIN + INT_MIN */ /* INT_MIN - op2 <= 0 */ /* INT_MIN - op2 <= INT_MAX */ /* */ /** Hence, we have: ***************************************/ /* */ /* INT_MIN <= INT_MIN - op2 <= INT_MAX */ /* */ /* ie the following subtraction does not overflow. */ /* */ /***********************************************************/ if (op1 < INT_MIN - op2) { return 1; } /** We have: *********************************/ /* */ /* INT_MIN - op2 <= op1 */ /* INT_MIN <= op1 + op2 */ /* */ /** Also, we have: ***************************/ /* */ /* op2 < 0 */ /* op1 + op2 < op1 */ /* op1 + op2 < INT_MAX */ /* op1 + op2 <= INT_MAX */ /* */ /** Hence, we have: **************************/ /* */ /* INT_MIN <= op1 + op2 = 0 */ /* - op2 <= 0 */ /* INT_MAX - op2 = op2 */ /* - INT_MAX <= - op2 */ /* INT_MAX - INT_MAX <= - op2 + INT_MAX */ /* 0 <= - op2 + INT_MAX */ /* 0 <= INT_MAX - op2 */ /* INT_MIN <= INT_MAX - op2 */ /* */ /** Hence, we have: ***************************************/ /* */ /* INT_MIN <= INT_MAX - op2  INT_MAX - op2) { return 1; } /** We have: *********************************/ /* */ /* op1 <= INT_MAX - op2 */ /* op1 + op2 <= INT_MAX */ /* */ /** Also, we have: ***************************/ /* */ /* 0 <= op2 */ /* op1 <= op2 + op1 */ /* INT_MIN <= op2 + op1 */ /* INT_MIN <= op1 + op2 */ /* */ /** Hence, we have: **************************/ /* */ /* INT_MIN <= op1 + op2 <= INT_MAX */ /* */ /* ie the addition does not overflow. */ /* */ /**********************************************/ } *res = op1 + op2; return 0; } 

Answer 1

OP的方法可以最佳地移植到int类型中以及安全 – 没有任何int组合的未定义行为（UB）。 它独立于特定的int格式（2的补码，2的补码，符号幅度）。

在C中， int overflow /（下溢）是未定义的行为。 所以代码，如果保持int ，必须事先确定溢出潜力。 当op1正时， INT_MAX - op1不能溢出。 此外，如果op1负，则INT_MIN - op1不会溢出。 因此，在正确计算和测试边缘的情况下， op1 + op2不会溢出。

 // Minor re-write: int safe_int_add(int * res, int op1, int op2) { assert(res != NULL); if (op1 >= 0) { if (op2 > INT_MAX - op1) return 1; } else { if (op2 < INT_MIN - op1) return 1; } *res = op1 + op2; return 0; } 

也可以看看

如果知道更广泛的类型 ，代码可以使用

 int safe_int_add_wide(int * res, int op1, int op2) { int2x sum = (int2x) op1 + op2; if (sum < INT_MIN || sum > INT_MAX) return 1; *res = (int) sum; return 0; } 

使用unsigned等的方法首先需要限定UINT_MAX > = INT_MAX - INT_MIN 。 这通常是正确的，但不能通过C标准保证。

Answer 2

我就是这样做的：

如果输入参数具有不同的符号，那么结果总是可计算的而没有任何溢出的风险。

如果两个输入参数都是负数，则计算-safe_int_add(res, -op1, -op2); 。 （你需要检查op1或op2不是2s赞美中最大的负数）。

需要思考的function是添加两个正数的function：将两个输入转换为无符号类型。 添加那些。 这保证不会溢出无符号类型，因为你可以在unsigned int中存储（至少）两倍大的值而不是在signed int中（对于1s补码来说恰好是两倍，比2s补码多一次）。

然后，如果无符号值足够小，则只尝试转换回签名。

Answer 3

您可以查看JDK 8的实现，它可以很好地参考来自Henry S. Warren，Jr。的Hacker’s Delight一书：

http://hg.openjdk.java.net/jdk8/jdk8/jdk/rev/b971b51bec01

 public static int addExact(int x, int y) { int r = x + y; // HD 2-12 Overflow iff both arguments have the opposite sign of the result if (((x ^ r) & (y ^ r)) < 0) { throw new ArithmeticException("integer overflow"); } return r; } 

在我的本书中，虽然是第2-13章。 在那里你可以找到关于整个问题的冗长解释。