Search code examples
mathmathematical-expressions

How to get the mid of 2 int32 number elegantly without overflow?

In some conditions like Segment Tree or Binary Search, I have to get the average value of 2 number.

An easy solution is mid = (a + b) / 2. But when it comes to a and b have the same plus-minus signs, The a + b thing will overflow. For example, 1234567 + 2147483647, -1234567 + (-2147483647) in int32 type.

I searched online and got to know mid = (b - a) / 2 + a, it can avoid the situation above, but still not perfect. When it comes to a and b have the different plus-minus signs, mid = (a + b) / 2 won't overflow but (b - a) / 2 + a will. For example, -2147483648 + 2147483647 in int32 type.

To thoroughly solve this problem, I've written the code in pic below. I divide the 2 situations by the plus-minus signs. (I use some bit operations to improve its efficiency.) But it is way too complex for such a simple problem, right?

Is there some elegant solution to this problem?

My Solution Code

I tried to divide the problem to 2 situations and solve them respectively. But I still want a more elegant solution.

Solution

  • Got the answer!

    mid = (a & b) + ((a ^ b) >> 1)

    a & b keeps the same bits that a and b have in common, they need not to be distributed averagely. Like when you find the average value of 102 and 110, you don't need to calculate the 100 they have in common. You can just keep that, and deal with the 2 and 10 part, distribute them averagely to 2 number. As (102 + 110) / 2 = (2 * 100 + 2 + 10) / 2 = 100 + (2 + 10) / 2 = 100 + 6 = 106.

    (a ^ b) >> 1 deals with the "2 and 10 part", it gets all the bits that a and b don't have in common, and divide it by 2.

    Adds up 2 parts above so we get the average value of a and b. Not a strict proof, though.