News for hackers. Stuff that matters.

A comment on Fast midpoint between two integers without overflow. Parent comment

Re:Fast midpoint between two integers without overflow by ardel95 on Wednesday December 07, 2022 @10:50AM (#33895723)
The correct way most people would write this for positive integers is:

if (a < b)

  return a + (b - a) / 2;
else

  return b + (a - b) / 2;
This method is just more efficient (for places where it matters) as it avoids divisions and branches. But for a vast, vast majority of use-case that tiny efficiency gain doesn’t really matter.
[ Parent | on HN ]
Re:Fast midpoint between two integers without overflow by zimpenfish on Wednesday December 07, 2022 @11:02AM (#33895902)
Is that the right way around? If `a<b` then `a-b` will be negative, surely, and adding that to `a` will be moving down from `a`, not from `a` to `b`?

cf https://go.dev/play/p/SgdWzzqDygn

[ Parent | on HN ]
Re:Fast midpoint between two integers without overflow by ardel95 on Wednesday December 07, 2022 @11:28AM (#33896307)
Eh, that’s what I get for writing code on a cell phone. Fixed.
[ Parent | on HN ]
Re:Fast midpoint between two integers without overflow by Chinjut on Wednesday December 07, 2022 @11:53AM (#33896735)
Wouldn't this still overflow when one of the values is positive, the other is negative, and their difference is sufficiently large?
[ Parent | on HN ]
Re:Fast midpoint between two integers without overflow by ardel95 on Wednesday December 07, 2022 @12:00PM (#33896843)
The tweet said unsigned ints
[ Parent | on HN ]
Re:Fast midpoint between two integers without overflow by Chinjut on Wednesday December 07, 2022 @12:02PM (#33896882)
Tweet? But yes, sorry, I missed that your post said positive ints. The article was about signed ints, though.
[ Parent | on HN ]
Re:Fast midpoint between two integers without overflow by ardel95 on Wednesday December 07, 2022 @12:07PM (#33896951)
Oh, you are right. For some reason I thought I saw unsigned in there.
[ Parent | on HN ]
Re:Fast midpoint between two integers without overflow by kevin_thibedeau on Wednesday December 07, 2022 @03:24PM (#33899747)
C promotion rules can can convert unsigned to signed and vice versa so it still matters.
[ Parent | on HN ]
Re:Fast midpoint between two integers without overflow by glxxyz on Wednesday December 07, 2022 @11:46AM (#33896619)
It can be rewritten without the test:

    return a - (a - b) / 2;
[ Parent | on HN ]
Re:Fast midpoint between two integers without overflow by ardel95 on Wednesday December 07, 2022 @12:03PM (#33896907)
Tweet said unsigned ints, so don’t think this would work. Even with signed I think this can overflow.
[ Parent | on HN ]
Re:Fast midpoint between two integers without overflow by glxxyz on Wednesday December 07, 2022 @12:11PM (#33897000)
> Tweet said unsigned ints

Which tweet?

[ Parent | on HN ]
Re:Fast midpoint between two integers without overflow by noasaservice on Wednesday December 07, 2022 @04:12PM (#33900324)
you can also do

min(a,b) + (max(a,b) - min(a,b))>>1

[ Parent | on HN ]