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.


Inkyrius
@Inkyrius

Hmm, just checked and (low + (high - low) / 2) also fails in certain other cases (when both are negative and one is odd I think, but it might be more specific), however it works if you get low and high with the absolute min and max (position relative to zero) rather than just the regular min and max (position relative to -inf).


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.