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.
Why is that wrong?