11 ms·
Why not just x/2 + y/2 ?
by zerr 4y ago
Why not just x/2 + y/2 ?
- adwn 4y agoThat doesn't work when both are odd. For example, for x=1 and y=3 this gives 1 instead of 2.
- someweirdperson 4y ago1/2 + 3/2 + 1 = 0 + 1 + 1 = 2
- rocqua 4y agoYour final +1 is not in the expression by OP. You can get it by taking the correction term (x & y & 1) as mentioned in another comment.
- someweirdperson 4y agowoops, misread the indent-depth of the posts as reply, not to the same parent.
- beardyw 4y agoBecause division is a slow operation. Even (x + y)/2 would be quicker
- secondcoming 4y agoDividing by two is just a right shift.
- robocat 4y agoOnly if you are dealing with unsigned integers. For signed integers, you need to be careful depending on the language you are using. Most languages provide a signed right shift that doesn’t lose the sign. Personally, I think shift should always have been a bitwise operator, without sign extension. To me signed right shift feels as sensible as right shifting a floating point number - a shift is bitwise and not an arithmetical operator. But I guess that’s what comes from being brought up on healthy machine code by robots in the steel jungle. C recommendation: “INT13-C. Use bitwise operators only on unsigned operands” https://wiki.sei.cmu.edu/confluence/plugins/servlet/mobile?contentId=87152374 https://wiki.sei.cmu.edu/confluence/plugins/servlet/mobile?c...
- vlovich123 4y agoX+y can overflow which is what the post is saying.
- _ache_ 4y agoDivision by 2 is one of the quickest operation. The correct implies 3 additions instead of one, so you go a point. But y>>1 + x>>1 + (x & y & 1) is easier to remember than ((x^y)>>1) + (x&y).
- mredigonda 4y agoBecause the division is truncated twice, which increases the error. Take x=y=1, or x=y=3 for example.
- pajko 4y agoAssuming integer division, for x=3 and y=5 that would give 3, whereas the midpoint is 4.
- _ache_ 4y agox/2 + y/2 + (x & y & 1) should work.