Fast midpoint between two integers without overflow

Re:Fast midpoint between two integers without overflow by eloff on Wednesday December 07, 2022 @08:35AM (#33894150)

You don't necessarily need that actually, there are carry flags that are set on overflow that you can check to get that extra bit of precision.

In Rust you can actually do this using the checked add/sub/etc methods. It's one of the things I really appreciate about the language. By default, it panics on overflow in debug builds. You have to use the wrapping variants to declare that's intentional.

How about:

  if a > b { 
    mid = (a-b)/2 
  } else { 
    mid = (b-a)/2 
  }

There must be a way to do it without the branch? edit: Yes, in the article, I'm an idiot.

[ Parent | on HN ]

Re:Fast midpoint between two integers without overflow by tromp on Wednesday December 07, 2022 @08:55AM (#33894337)

    if a > b { 
      mid = (a-b)/2

That only avoids overflow on unsigned types (where it would be called wraparound) ...

[ Parent | on HN ]

Re:Fast midpoint between two integers without overflow by eloff on Wednesday December 07, 2022 @09:01AM (#33894394)

The point of the midpoint calculation is to find the mid-index usually (e.g. binary search, quicksort). So a and b would be unsigned. You're right about signed integers though.

[ Parent | on HN ]