fork download
copy 
  1.  
  2. #include <limits>
  3.  
  4. #include <iostream>  // needed for demonstration purpose only
  5. #include <stdexcept> // needed for demonstration purpose only
  6. #include <array>     // needed for demonstration purpose only
  7. #include <utility>   // needed for demonstration purpose only
  8.  
  9. namespace safe
  10. {
  11. 	constexpr static auto max = std::numeric_limits<int>::max();
  12. 	constexpr static auto min = std::numeric_limits<int>::min();
  13.  
  14. 	int negation(int a);
  15.  
  16. 	int multiplication(int a, int b);
  17. 	int division(int a, int b);
  18. 	int addition(int a, int b);
  19. 	int subtraction(int a, int b);
  20. }
  21.  
  22. namespace test
  23. {
  24. 	template <typename Function>
  25. 	void unary(Function function, const char* function_name, int a);
  26.  
  27. 	template <typename Function>
  28. 	void binary(Function function, const char* function_name, int a, int b);
  29. }
  30.  
  31. int main()
  32. {
  33. 	using namespace safe;
  34. 	using UnaryFunction = int (*)(int);
  35. 	using BinaryFunction = int (*)(int, int);
  36. 	using FunctionName = const char*;
  37. 	using TestsUnary = std::array<std::pair<UnaryFunction, FunctionName>, 1>;
  38. 	using TestsBinary = std::array<std::pair<BinaryFunction, FunctionName>, 4>;
  39. 	TestsUnary unary_functions = {std::make_pair(negation, "negation")};
  40. 	TestsBinary binary_functions = {std::make_pair(multiplication, "multiplication"),
  41. 	                                std::make_pair(division, "division"),
  42. 	                                std::make_pair(addition, "addition"),
  43. 	                                std::make_pair(subtraction, "subtraction")};
  44.  
  45. 	std::array<int, 19> values = { min,
  46. 	                              (min / 2) - 1,
  47. 	                               min / 2,
  48. 	                              (min / 2) + 1,
  49. 	                               min / 3,
  50. 	                              -4,
  51. 	                              -3,
  52. 	                              -2,
  53. 	                              -1,
  54. 	                               0,
  55. 	                               1,
  56. 	                               2,
  57. 	                               3,
  58. 	                               4,
  59. 	                               max / 3,
  60. 	                              (max / 2) - 1,
  61. 	                               max / 2,
  62. 	                              (max / 2) + 1,
  63. 	                               max};
  64.  
  65. 	using namespace test;
  66. 	for ( auto& testable : unary_functions )
  67. 	{
  68. 		auto& function = std::get<0>(testable);
  69. 		auto& name = std::get<1>(testable);
  70. 		std::cout << name << ":\n";
  71. 		for ( auto value : values )
  72. 		{
  73. 			test::unary(function, name, value);
  74. 		}
  75. 		std::cout << '\n';
  76. 	}
  77.  
  78. 	for ( auto& testable : binary_functions )
  79. 	{
  80. 		auto& function = std::get<0>(testable);
  81. 		auto& name = std::get<1>(testable);
  82. 		std::cout << name << ":\n";
  83. 		for ( auto value1 : values )
  84. 		{
  85. 			for ( auto value2 : values )
  86. 			{
  87. 				test::binary(function, name, value1, value2);
  88. 			}
  89. 			std::cout << '\n';
  90. 		}
  91. 		std::cout << '\n';
  92. 	}
  93. 	return 0;
  94. }
  95.  
  96. namespace safe
  97. {
  98.  
  99.  
  100. 		/**
  101. 		 * 	Integer multiplication.
  102. 		 * 	
  103. 		 * 	Detailed logic:
  104. 		 * 	if ( a == 0 || b == 0 )
  105. 		 * 	{
  106.  		*		return 0;
  107. 		 * 	}
  108. 		 *  else if ( a == -1 )
  109. 		 *  {
  110. 		 *      return negation(b);
  111. 		 *  }
  112. 		 *  else if ( b == -1 )
  113. 		 *  {
  114. 		 *      return negation(a);
  115. 		 *  }
  116. 		 * 	else if ( a > 0 && b > 0 )
  117. 		 * 	{
  118.  		 *	 	const auto limit_result = max; // result will be positive
  119. 		 * 		const auto limit_a = limit_result / b; // (limit_a + 1) * b > max, which is invalid.
  120. 		 * 		if ( a > limit_a )
  121. 		 * 		{
  122.  		 *			// error
  123. 		 * 		}
  124. 		 * 	}
  125. 		 * 	else if ( a < 0 && b < 0 )
  126. 		 * 	{
  127.  		 * 		const auto limit_result = max; // result will be positive
  128. 	     *	 	const auto limit_a = limit_result / b; // (limit_a - 1) * b > max, which is invalid.
  129. 		 * 		if ( a < limit_a )
  130. 		 * 		{
  131. 		 *			// error
  132. 		 * 		}
  133. 		 * 	}
  134. 		 * 	else if ( a > 0 && b < 0 )
  135. 		 * 	{
  136.  		 * 		const auto limit_result = min; // result will be negative
  137. 		 * 		const auto limit_a = limit_result / b; // (limit_a + 1) * b < min, which is invalid
  138. 		 * 		if ( a > limit_a )
  139. 		 * 		{
  140.   		 * 			// error
  141. 		 * 		}
  142. 		 * 	}
  143. 		 * 	else if ( a < 0 && b > 0 )
  144. 		 *	{
  145. 		 *		const auto limit_result = min; // result will be negative
  146. 		 *		const auto limit_a = limit_result / b; // (limit_a - 1) * b < min, which is invalid
  147. 		 *		if ( a < limit_a )
  148. 		 *		{
  149. 		 *			// error
  150. 		 *		}
  151. 		 * 	}
  152. 		 *	return a * b;
  153. 		 * 
  154. 		 */
  155. 	int multiplication(int a, int b)
  156. 	{
  157. 		if ( (a == 0) || (b == 0) )
  158. 		{
  159. 			return 0;
  160. 		}
  161. 		if ( a == -1 )
  162. 		{
  163. 			return negation(b);
  164. 		}
  165. 		if ( b == -1 )
  166. 		{
  167. 			return negation(a);
  168. 		}
  169. 		const auto limit_result = ((a > 0) == (b > 0)) ? max : min;
  170. 		const auto limit_a = limit_result / b; // well defined, since b != 0, b != -1.
  171. 		if ( (0 < a && limit_a < a) || (0 > a && limit_a > a) )
  172. 		{
  173. 			throw std::invalid_argument("Multiplication overflow.");
  174. 		}
  175. 		return a * b;
  176. 	}
  177.  
  178. 	/**
  179. 	 * 
  180. 	 * 	Integer division can only fail if the divisor is zero.
  181. 	 *  It can also fail, it the divisor is -1 (because then only the sign changes and the magnitude isn't guaranteed to fit.)
  182. 	 */
  183. 	int division(int a, int b)
  184. 	{
  185. 		if ( b == 0 )
  186. 		{
  187. 			throw std::invalid_argument("Division by zero.");
  188. 		}
  189. 		if ( b == -1 )
  190. 		{
  191. 			return negation(a);
  192. 		}
  193. 		return a / b; // division is safe, if divisor is not equal to zero.
  194. 	}
  195.  
  196. 	/**
  197. 		If the operands have different sign, the result cannot be invalid:
  198. 		   w.l.o.g. a < 0 && b > 0
  199. 			min <= a < 0 < b <= max
  200. 			Hence, 
  201. 			a >= min && b > 0, therefore a + b    >= min + b    >= min
  202. 			b <= max && a < 0, therefore b - (-a) <= max - (-a) <= max
  203. 		If the operands have the same sign, the result may be invalid.
  204. 		  If a > 0 and b > 0:
  205. 		    If a + b > max, then conversely a > max - b. max - b is valid.
  206. 		  If a < 0 and b < 0:
  207. 		  	If a + b < min, then conversely a < min - b, min - b is valid.
  208. 	 */
  209. 	int addition(int a, int b)
  210. 	{
  211. 		if ( (a > 0 && b > 0 && max - b < a) ||
  212. 		     (a < 0 && b < 0 && a < min - b) )
  213. 		{
  214. 			throw std::invalid_argument("Addition overflow.");
  215. 		}
  216. 		return a + b;
  217. 	}
  218.  
  219. 	/**
  220. 	 * Technically, this can be done by inverting b and calculating a + (-b).
  221. 	 * This however can fail, if -b cannot be represented.
  222. 	 * 
  223. 	 * Hence, the same logic as in addition is applied:
  224. 	 * If a and b have the same sign, the result is valid.
  225. 	 * If a > 0 and b < 0, the result may be too large, however, max + b is a valid number
  226. 	 * If a < 0 and b > 0, the result may be too small, however, min + b is a valid number.
  227. 	 */
  228. 	int subtraction(int a, int b)
  229. 	{
  230. 		if ( (a > 0 && b < 0 && max + b < a) ||
  231. 		     (a < 0 && b > 0 && a < min + b) )
  232. 		{
  233. 			throw std::invalid_argument("Subtraction overflow.");
  234. 		}
  235. 		return a - b;
  236. 	}
  237.  
  238. 	/**
  239. 		-a is invalid, if it cannot be represented in that range.
  240. 		The integer type either has the range [-2^n, 2^n) or
  241. 		                                      (-2^n, 2^n)
  242. 		That is, either the smallest number is -2^n or -2^n + 1,
  243. 		 while the largest number is always 2^n - 1.
  244.  
  245. 		Hence, the only value that may not be valid input is the smallest number.
  246.  
  247. 		If the range is symmetric, every value can be inverted,
  248. 		otherwise, the negation fails for the smallest number.
  249. 	*/
  250. 	int negation(int a)
  251. 	{
  252. 		constexpr static bool symmetric_range = (min + max == 0);
  253. 		if ( !symmetric_range && a == min )
  254. 		{
  255. 			throw std::invalid_argument("The integer representation doesn't allow negation of the smallest integer.");
  256. 		}
  257. 		return -a;
  258. 	}
  259. }
  260.  
  261. namespace test
  262. {
  263. 	template <typename Function>
  264. 	void unary(Function function, const char* function_name, int a)
  265. 	try
  266. 	{
  267. 		function(a);
  268. 		std::cout << '1';
  269. 	}
  270. 	catch ( ... )
  271. 	{
  272. 		std::cout << '0';
  273. 	}
  274.  
  275. 	template <typename Function>
  276. 	void binary(Function function, const char* function_name, int a, int b)
  277. 	try
  278. 	{
  279. 		function(a, b);
  280. 		std::cout << '1';
  281. 	}
  282. 	catch ( ... )
  283. 	{
  284. 		std::cout << '0';
  285. 	}
  286. }
  287.  
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
negation:
0111111111111111111
multiplication:
0000000001100000000
0000000011100000000
0000000011110000000
0000000111110000000
0000001111111000000
0000011111111100000
0000111111111110000
0001111111111111110
0111111111111111111
1111111111111111111
1111111111111111111
0011111111111111100
0000111111111110000
0000011111111100000
0000001111111000000
0000000111110000000
0000000111110000000
0000000111100000000
0000000011100000000

division:
1111111100111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111
1111111110111111111

addition:
0000000001111111111
0001111111111111111
0011111111111111111
0111111111111111111
0111111111111111111
0111111111111111111
0111111111111111111
0111111111111111111
0111111111111111111
1111111111111111111
1111111111111111110
1111111111111111110
1111111111111111110
1111111111111111110
1111111111111111110
1111111111111111110
1111111111111111110
1111111111111111100
1111111111000000000

subtraction:
1111111111000000000
1111111111111111100
1111111111111111110
1111111111111111110
1111111111111111110
1111111111111111110
1111111111111111110
1111111111111111110
1111111111111111111
1111111111111111111
0111111111111111111
0111111111111111111
0111111111111111111
0111111111111111111
0111111111111111111
0111111111111111111
0011111111111111111
0001111111111111111
0000000001111111111
https://ideone.com/p9FqHn
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!