3 ms·
> 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?
by heavenlyblue 4y ago
> 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?
- stevoski 4y agoIf 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.
- scajanus 4y agoIf a & b are both odd, you end up rounding twice vs. 0 times if you take the sum first.
- eloff 4y agoIt'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.
- Jagerbizzle 4y agoThe 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);
- nick4780167 4y agoMaybe a little slower, but way more readable than the ones in the article.
- bonzini 4y agoIt's still wrong for signed integers if a/2 rounds towards zero. You need a>>1 and b>>1.
- nathell 4y agoBecause, assuming / means integer division, this would return 6 as the midpoint between 7 and 7.