c++ - 安全地添加整数，并证明安全性

Question

编程类(class)作业要求

• 编写一个(安全的)函数，将两个整数相加，并且
• 表明该函数是安全的。

以下代码代表我的解决方案。我不是 C 标准(或形式验证方法)方面的专家。所以我想问:是否有更好(或不同)的解决方案？

谢谢

#include <limits.h>

/*
      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 < 0) {

    /**  We have: **********************************************/
    /*                                                         */
    /*          0  >     op2                                   */
    /*          0  <   - op2                                   */
    /*    INT_MIN  <   - op2 + INT_MIN                         */
    /*    INT_MIN  <           INT_MIN - op2                   */
    /*    INT_MIN  <=          INT_MIN - op2                   */
    /*                                                         */
    /**  Also, we have: ****************************************/
    /*                                                         */
    /*              op2  >=    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              */
    /*                                                         */
    /*    i.e. 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  <=  INT_MAX     */
    /*                                            */
    /*    i.e. the addition does not overflow.    */
    /*                                            */
    /**********************************************/

  }
  else {

    /**  We have: **********************************************/
    /*                                                         */
    /*              op2  >=  0                                 */
    /*            - op2  <=  0                                 */
    /*    INT_MAX - op2  <=  INT_MAX                           */
    /*                                                         */
    /**  Also, we have: ****************************************/
    /*                                                         */
    /*              INT_MAX  >=    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              */
    /*                                                         */
    /*    i.e. the following subtraction does not overflow.    */
    /*                                                         */
    /***********************************************************/

    if (op1 > 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     */
    /*                                            */
    /*    i.e. the addition does not overflow.    */
    /*                                            */
    /**********************************************/

  }

  *res = op1 + op2;
  return 0;
}

Answer 1

我会这样做:

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

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

需要思考的函数是将两个正数相加的函数:将您的两个输入转换为无符号类型。添加那些。这保证不会溢出无符号类型，因为您可以在无符号整数中存储(至少)两倍于有符号整数的值(对于 1s 恭维恰好两倍，比 2s 多一个恭维)。

然后只有在无符号值足够小的情况下才尝试转换回有符号。