Jiancong Li's Blog
0%

C++关于乘法溢出的判断

Posted on Edited on In

概述

首先我们对于乘法溢出的判断，先写测试用例：

1592715337389

由上图我们简化测试用例：

1592715602260

我们可以这样设计乘法溢出函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/// 判断两入参相乘是否溢出，溢出返回true，否则返回false
bool is_multi_overflow(int x, int y) {
  if (x > 0 && y > 0) {
    /// 同为正号
      return x > INT_MAX/y;
  } else if (x < 0 && y < 0) {
    /// 同为负号
    if (y == INT_MIN && x <= -1) {
      return true;
    }
    return x < INT_MIN/-y;
  } else if (x > 0 && y<0 || (x < 0 && y > 0)) {
    /// 异号的情况稍等补上
    return false;
  } else {
    return false;
  }
}

接下来我们添加测试用例

1592727579022

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cassert>
#include <iostream>
#include <numeric>

/// 判断两入参相乘是否溢出，溢出返回true，否则返回false
bool is_multi_overflow(int x, int y) {
  if (x > 0 && y > 0) {
    /// 同为正号
      return x > INT_MAX/y;
  } else if (x < 0 && y < 0) {
    /// 同为负号
    if (y == INT_MIN && x <= -1) {
      return true;
    }
    return x < INT_MIN/-y;
  } else if (x > 0 && y<0 || (x < 0 && y > 0)) {
    /// 异号的情况稍等补上
    return false;
  } else {
    return false;
  }
}

int main() {
  int x = 0;
  int y = 0;
  int max_num = std::numeric_limits<int>::max();
  int min_num = std::numeric_limits<int>::min();

  /// case 1 #1
  x = 7;
  y = 1 + max_num / x;
  assert(is_multi_overflow(x, y));
  x = max_num - 1;
  y = 1 + max_num / x;
  assert(is_multi_overflow(x, y));

  /// case 1 #2
  x = 7;
  y = max_num / x;
  assert(!is_multi_overflow(x, y));
  x = max_num - 1;
  y = max_num / x;
  assert(!is_multi_overflow(x, y));

  /// case 2 #1
  x = -7;
  y = -1 + min_num / -x;
  assert(is_multi_overflow(x, y));
  x = min_num + 1;
  y = -1 + min_num / -x;
  assert(is_multi_overflow(x, y));

  /// case 2 #2
  x = -7;
  y = min_num / -x;
  assert(!is_multi_overflow(x, y));
  x = min_num + 1;
  y = min_num / -x;
  assert(!is_multi_overflow(x, y));
}

接下来为特殊数值来添加判断：

1592727736048

添加异号情况的判断：

1592730284047

把函数改为模板，一并添加测试用例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cassert>
#include <iostream>
#include <numeric>

/// 判断两入参相乘是否溢出，溢出返回true，否则返回false
template <typename T1, typename T2>
bool is_multi_overflow(T1 x, T2 y) {
  static_assert(std::is_same<T1, T2>::value,
                "is_multi_overflow need same type!");
  static_assert(std::is_integral<T1>::value,
                " is_multi_overflow need integral type!");
  int num_max = std::numeric_limits<T1>::max();
  int num_min = std::numeric_limits<T1>::min();
  if (x == 0 || y == 0 || x == 1 || y == 1) {
    return false;
  }
  if (x == -1) {
    return y == num_min;
  } else if (y == -1) {
    return x == num_min;
  }

  if (x > 0 && y > 0) {
    /// 同为正号
    return x > num_max / y;
  } else if (x < 0 && y < 0) {
    /// 同为负号
    if (y == num_min && x <= -1) {
      return true;
    }
    return x < num_min / -y;
  } else if (x > 0 && y < 0 || (x < 0 && y > 0)) {
    /// 异号的情况
    if (x > y) {
      std::swap(x, y);
    }
    return x < num_min / y;
  } else {
    return false;
  }
}

int main() {
  int x = 0;
  int y = 0;
  int max_num = std::numeric_limits<int>::max();
  int min_num = std::numeric_limits<int>::min();

  /// case 1 #1
  x = 7;
  y = 1 + max_num / x;
  assert(is_multi_overflow(x, y));
  x = max_num - 1;
  y = 1 + max_num / x;
  assert(is_multi_overflow(x, y));

  /// case 1 #2
  x = 7;
  y = max_num / x;
  assert(!is_multi_overflow(x, y));
  x = max_num - 1;
  y = max_num / x;
  assert(!is_multi_overflow(x, y));

  /// case 2 #1
  x = -7;
  y = -1 + min_num / -x;
  assert(is_multi_overflow(x, y));
  x = min_num + 1;
  y = -1 + min_num / -x;
  assert(is_multi_overflow(x, y));

  /// case 2 #2
  x = -7;
  y = min_num / -x;
  assert(!is_multi_overflow(x, y));
  x = min_num + 1;
  y = min_num / -x;
  assert(!is_multi_overflow(x, y));

  /// case 3
  x = 0;
  y = max_num;
  assert(!is_multi_overflow(x, y));
  x = min_num;
  y = 0;
  assert(!is_multi_overflow(x, y));
  x = 0;
  y = 0;
  assert(!is_multi_overflow(x, y));

  /// case 4
  x = 1;
  y = max_num;
  assert(!is_multi_overflow(x, y));
  x = INT_MIN;
  y = 1;
  assert(!is_multi_overflow(x, y));

  /// case 5
  x = -1;
  y = max_num;
  assert(!is_multi_overflow(x, y));
  x = -1;
  y = min_num;
  assert(is_multi_overflow(x, y));

  /// case 6
  x = 2;
  y = min_num / 2;
  assert(!is_multi_overflow(x, y));
  assert(!is_multi_overflow(y, x));
  x = 2;
  y = -1 + min_num / 2;
  assert(is_multi_overflow(x, y));
  assert(is_multi_overflow(y, x));
}

最后附上完整测试用例：

1592730393076

后记

我们既然有了判断乘法溢出的函数，我们可以借此封装一个带有检查溢出的乘法函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <optional>

template <typename T1, typename T2>
std::optional<T1> multiplies_s(const T1 x, const T2 y) noexcept {
  static_assert(std::is_same<T1, T2>::value, "Multiplies_s need same type!");
  static_assert(std::is_integral<T1>::value,
                "Multiplies_s need integral type!");
  if (is_multi_overflow(x, y)) return {};
  return x * y;
}

int main()
{
  int x = 5;
  int y = 5;
  int result = multiplies_s(x, y).value_or(0);
}