Inkyrius

The Girl Anachronism

 


 
This place is not a place of honour. No highly esteemed deed is commemorated here. Nothing valued is here.

 
Inkyrius or Inky or Kyrie are all fine.
Girl with a dash of Void.

 
Queer Trans Nerd. Mostly Harmless.
Interests include programming, formerly Minecraft modding, conlangs, worldbuilding, maps, typography, etc.

 




quat
@quat
This page's posts are visible only to users who are logged in.

Inkyrius
@Inkyrius

I think the obvious solution is to switch between what I would consider the two “intuitive” answers (1st and 5th on your list) based on the characteristics of the numbers. (a + b) can only fail in cases when both numbers are of the same sign, while (high - low) can only fail in cases where both numbers have different signs.

It would be nicer to have a single equation for it though. I'm going to be thinking about this all day aren't I, damn.


You must log in to comment.

in reply to @quat's post:

high - low underflows

That's an overflow too. Subtraction of integers cannot underflow since the result is an integer too and not a real.
Underflow is when the result has a floating point whose exponent overflows.

You can also solve the overflow by using min and max, which Bloch is enforcing with a check. The issue then is that it only works when both operands are of the same sign.

(low + (high - low) / 2) (that Joshua Bloch blogged about at Google). Fails when high - low underflows.

Bloch posted about this:

int mid =(low + high) / 2;

and suggested the one you posted as a fix

Hacker's Delight has a solution for the one failure case of (a & b) + (a ^ b)/2 that you pointed out. Written for 32-bit signed integers:

t <- (a & b) + ((a ^ b) s>> 1);
t + ((t u>> 31) & (a ^ b))

where s>> is signed shift right and u>> is unsigned (doesn't do sign extension). The second line adds 1, if a + b is negative and odd.