A bitwise shortcut for calculating the signed result of `(x - y) / z`, given unsigned operands

Question

I'm looking for a neat way (most likely, a "bitwise shortcut") for calculating the signed value of the expression (x - y) / z, given unsigned operands x, y and z.

Here is a "kinda real kinda pseudo" code illustrating what I am currently doing (please don't mind the actual syntax being "100% perfect C or C++"):

int64 func(uint64 x, uint64 y, uint64 z)
{
    if (x >= y) {
        uint64 result = (x - y) / z;
        if (int64(result) >= 0)
            return int64(result);
    }
    else {
        uint64 result = (y - x) / z;
        if (int64(result) >= 0)
            return -int64(result);
    }
    throwSomeError();
}

Please assume that I don't have a larger type at hand.

I'd be happy to read any idea of how to make this simpler/shorter/neater.

Answer 1

There is a shortcut, by using a bitwise trick for conditional-negation twice (once for the absolute difference, and then again to restore the sign).

I'll use some similar non-perfect C-ish syntax I guess, to match the question.

First get a mask that has all bits set iff x < y:

uint64 m = -uint64(x < y);

(x - y) and -(y - x) are actually the same, even in unsigned arithmetic, and conditional negation can be done by using the definition of two's complement: -a = ~(a - 1) = (a + (-1) ^ -1). (a + 0) ^ 0 is of course equal to a again, so when m is -1, (a + m) ^ m = -a and when m is zero, it is a. So it's a conditional negation.

uint64 absdiff = (x - y + m) ^ m;

Then divide as usual, and restore the sign by doing another conditional negation:

return int64((absdiff / z + m) ^ m);