News for hackers. Stuff that matters.
Re:Fast midpoint between two integers without overflow by heavenlyblue on Wednesday December 07, 2022 @08:27AM (#33894069)
> Then the majority come up with (a / 2) + (b / 2) until they run the unit tests and realize it's wrong.

Why is that wrong?

Re:Fast midpoint between two integers without overflow by eloff on Wednesday December 07, 2022 @08:31AM (#33894112)
It's mathematically correct, but integers use truncating (floor) division. So you can lose a fractional 0.5 from both a/2 and b/2, which would have added up to 1, and now your result is off by one from (a+b)/2.

In general, even with floating point numbers you can get different results by rounding implicitly or intentionally the intermediate values versus the end result.

Re:Fast midpoint between two integers without overflow by stevoski on Wednesday December 07, 2022 @08:29AM (#33894096)
If a=1 and b=1, the midpoint should be 1.

But in computing, assuming we are only dealing with integers, 1/2 == 0. So 1/2 + 1/2 returns 0.

Re:Fast midpoint between two integers without overflow by Jagerbizzle on Wednesday December 07, 2022 @08:43AM (#33894225)
The dev blog from Microsoft in a different comment covers this:

"This will be too low if the original addition contained a carry from bit 0 to bit 1, which happens if bit 0 is set in both of the terms, so we detect that case and make the necessary adjustment."

return (a / 2) + (b / 2) + (a & b & 1);

Re:Fast midpoint between two integers without overflow by bonzini on Wednesday December 07, 2022 @10:21AM (#33895338)
It's still wrong for signed integers if a/2 rounds towards zero. You need a>>1 and b>>1.
Re:Fast midpoint between two integers without overflow by nick4780167 on Wednesday December 07, 2022 @10:17AM (#33895282)
Maybe a little slower, but way more readable than the ones in the article.
Re:Fast midpoint between two integers without overflow by scajanus on Wednesday December 07, 2022 @08:31AM (#33894110)
If a & b are both odd, you end up rounding twice vs. 0 times if you take the sum first.
Re:Fast midpoint between two integers without overflow by nathell on Wednesday December 07, 2022 @08:50AM (#33894297)
Because, assuming / means integer division, this would return 6 as the midpoint between 7 and 7.