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).


Inkyrius
@Inkyrius

Realised I was going to add my code and then never did, but I'm pretty sure this works for all cases unless one of the numbers is INT_MIN (abs(INT_MIN) == INT_MAX + 1 which obviously breaks. Pretty easy to fix, you can find closest to zero without abs because it will always be fed numbers of the same sign, but I can't be bothered at the moment):

#include <stdio.h>
#include <stdlib.h>

int absmax(int a, int b) { return (abs(a) > abs(b)) ? a : b; }
int absmin(int a, int b) { return (abs(a) < abs(b)) ? a : b; }

int signedAvg(int a, int b) {
  if ((a < 0) != (b < 0)) {
    return (a + b) / 2;
  }
  else {
    int low = absmin(a, b);
    int high = absmax(a, b);
    return low + ((high - low) / 2);
  }
}
syntax highlighting by codehost

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.