CODEWITHSUNDEEP
javamath
钱黑子
钱黑子

Reputation: 31

Method to safely calculate the average of two numbers in Java

In Java, when we calculate the average of two numbers (for example, int), to prevent overflow, we usually write:

int mid = a + (b - a) / 2;

However, why don't we write:

int mid = a - (a - b) / 2;

I don't know what's the difference between the two expressions. I am sure that the second is incorrect. But Why?

Upvotes: 1

Views: 826

Answers (2)

Joop Eggen
Joop Eggen

Reputation: 109557

Assuming a < b

Then the average prevents overflow for a + b > MAX_VALUE by

int mid = a + (b - a)/2;
        = b - (b - a)/2;
        = b + (a - b)/2;

However b - a might overflow, for instance when b = MAX_VALUE and a = MIN_VALUE. In that case the solution without overflow would be:

int mid = (a + b)/2;

int mid = (a < 0) != (b < 0) ? (a + b)/2 : a + (b - a)/2;

It should be mentioned that this is neither very practical in programming, and also that some other languages sometimes deal with overflow on the compiler level (using the Overflow flag of the CPU). As it is about bit 31 - how often would it happen?

Also Arrays.binSearch for instance only has non-negative indices; would not overflow and could do >>>1 instead of /2.

Upvotes: 0

GBlodgett
GBlodgett

Reputation: 12819

Neither is incorrect. All that is happening in the two equations is that you are factoring a negative out of the parenthesis.

int mid = a + (b - a) / 2;

Becomes:

int mid = a + -(-b + a) / 2;

Which simplified is:

int mid = a - (a - b) / 2;

Upvotes: 1

Related Questions