-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathAverageTests.cpp
138 lines (108 loc) · 5.31 KB
/
AverageTests.cpp
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <algorithm>
#include <chrono>
#include <random>
#include <ratio>
#include <vector>
#include <execution>
int AverageOverflowFree(int a, int b)
{
int average_ab;
if ((a >= 0 && b >= 0) || (a < 0 && b < 0))
average_ab = a + (b - a) / 2;
else
average_ab = (a + b) / 2;
return average_ab;
}
long long AverageOverflowFree(long long a, long long b)
{
long long average_ab;
if ((a >= 0 && b >= 0) || (a < 0 && b < 0))
average_ab = a + (b - a) / 2;
else
average_ab = (a + b) / 2;
return average_ab;
}
unsigned int AverageUnderflowFree(unsigned int a, unsigned int b)
{
unsigned int average_ab;
if (b >= a)
average_ab = a + (b - a) / 2;
else
average_ab = b + (a - b) / 2;
return average_ab;
}
size_t AverageUnderflowFree(size_t a, size_t b)
{
size_t average_ab;
if (b >= a)
average_ab = a + (b - a) / 2;
else
average_ab = b + (a - b) / 2;
return average_ab;
}
size_t AverageUnderflowFreeModulo(size_t a, size_t b)
{
return a / 2 + b / 2 + (a % 2 + b % 2) / 2;
}
void TestAverageOfTwoIntegers()
{
unsigned c_u = 6;
unsigned d_u = 8;
unsigned ave_cd_0 = (c_u + d_u) / 2; // correct result of 7
unsigned ave_cd_1 = c_u + (c_u - d_u) / 2; // wrong result of 2147483653
unsigned ave_cd_2 = c_u + (d_u - c_u) / 2; // correct result of 7
unsigned ave_cd_3 = ((c_u ^ d_u) >> 1) + (c_u & d_u);
printf("Average #0 = %u Average #1 = %u Average #2 = %u Average #3 = %u\n", ave_cd_0, ave_cd_1, ave_cd_2, ave_cd_3);
unsigned a_u = 1;
unsigned b_u = UINT32_MAX;
unsigned ave_ab_0 = (a_u + b_u) / 2; // wrong result of 0
unsigned ave_ab_1 = a_u + (b_u - a_u) / 2; // wrong result of 2
unsigned ave_ab_2 = a_u + (b_u - a_u) / 2; // correct result of 2147483648
unsigned ave_ab_3 = b_u + (a_u - b_u) / 2; // wrong result of 0
unsigned ave_ab_4 = ((a_u ^ b_u) >> 1) + (a_u & b_u); // correct result of 2147483648
printf("Average #0 = %u Average #1 = %u Average #2 = %u Average #3 = %u (a_u - b_u) = %u AverageMod = %u Average = %u\n",
ave_ab_0, ave_ab_1, ave_ab_2, ave_ab_3, (a_u - b_u), (unsigned)AverageUnderflowFreeModulo(a_u, b_u), ave_ab_4);
int e_i = 1;
int f_i = INT32_MAX;
int ave_ef_0 = (e_i + f_i) / 2; // wrong result of -1073741824
int ave_ef_1 = f_i + (e_i - f_i) / 2; // correct result of 1073741824
int ave_ef_2 = e_i + (f_i - e_i) / 2; // correct result of 1073741824
int sum_ef_0 = e_i + f_i; // wrong result of -2147483648
printf("Average #0 = %d Average #1 = %d Average #2 = %d Sum #0 = %d\n", ave_ef_0, ave_ef_1, ave_ef_2, sum_ef_0);
e_i = -1;
f_i = INT32_MIN;
ave_ef_0 = (e_i + f_i) / 2; // wrong result of 1073741823
ave_ef_1 = f_i + (e_i - f_i) / 2; // correct result of -1073741824
ave_ef_2 = e_i + (f_i - e_i) / 2; // correct result of -1073741824
int ave_ef_3 = ((unsigned)e_i + (unsigned)f_i) >> 1; // wrong result 1073741823
sum_ef_0 = e_i + f_i; // wrong result of 2147483647
printf("Average #0 = %d Average #1 = %d Average #2 = %d Average #3 = %d Sum #0 = %d\n", ave_ef_0, ave_ef_1, ave_ef_2, ave_ef_3, sum_ef_0);
e_i = 1;
f_i = INT32_MIN;
ave_ef_0 = (e_i + f_i) / 2; // corrent result of -1073741823
ave_ef_1 = f_i + (e_i - f_i) / 2; // wrong result of 1073741825
ave_ef_2 = e_i + (f_i - e_i) / 2; // wrong result of 1073741824
ave_ef_3 = ((unsigned)e_i + (unsigned)f_i) >> 1; // wrong result of 1073741824
sum_ef_0 = e_i + f_i; // correct result of -2147483647
int sub_ef_0 = e_i - f_i; // wrong result of -2147483647
printf("Average #0 = %d Average #1 = %d Average #2 = %d Average #3 = %d Sum #0 = %d Sub #0 = %d\n", ave_ef_0, ave_ef_1, ave_ef_2, ave_ef_3, sum_ef_0, sub_ef_0);
// Idea for unsigned: compare the two values, use the case of (larger - smaller)
// Idea for signed: compare the two values with zero, if both negative then compare to each other and use (smaller - larger)
// if both positive then compare to each other and use (larger - smaller), if oposite signs then can subtract without comparing to each other
// Another clever solution for integers if you know they will be positive: ave = ((unsigned)low + (unsigned)high) / 2 . This works because
// If we know that high >= low, then int mid = low + ((high - low) / 2 ) works
if (f_i >= e_i)
ave_ef_2 = e_i + (f_i - e_i) / 2;
else
ave_ef_2 = e_i + (e_i - f_i) / 2;
printf("\n\n");
printf("AverageSafe = %d input A = %d input B = %d\n", AverageOverflowFree( -1, INT32_MIN), -1, INT32_MIN);
printf("AverageSafe = %d input A = %d input B = %d\n", AverageOverflowFree(INT32_MIN, -1), INT32_MIN, -1);
printf("AverageSafe = %d input A = %d input B = %d\n", AverageOverflowFree( 1, INT32_MAX), 1, INT32_MAX);
printf("AverageSafe = %d input A = %d input B = %d\n", AverageOverflowFree(INT32_MAX, 1), INT32_MAX, 1);
printf("AverageSafe = %d input A = %d input B = %d\n", AverageOverflowFree(INT32_MAX, INT32_MIN), INT32_MAX, INT32_MIN);
printf("AverageSafe = %d input A = %d input B = %d\n", AverageOverflowFree(INT32_MIN, INT32_MAX), INT32_MIN, INT32_MAX);
printf("AverageSafe = %d input A = %d input B = %d\n", AverageOverflowFree( 5, -1), 5, -1);
printf("AverageSafe = %d input A = %d input B = %d\n", AverageOverflowFree( -1, 5), -1, 5);
}