mercredi 29 juin 2016

How to avoid trap representations when doing XOR bit-cancellation on signed ints?

As as suggested solution for Given three numbers, find the second greatest of them, I wrote:

int second_largest(int a, int b, int c) {
    int smallest = min(min(a, b), c);
    int largest = max(max(a, b), c);

    /* Toss all three numbers into a bag, then exclude the
       minimum and the maximum */
    return a ^ b ^ c ^ smallest ^ largest;
}

The idea is that ^ smallest ^ largest cancels out the bits such that the middle number remains.

However, @chux pointed out a problem:

A singular problem with int and a ^ b ^ c ^ smallest ^ largest is that an intermediate result may be a trap representation on rare non-2's complement platforms. – chux

@chux Please explain? XOR just operates bit by bit, and doesn't care what the bits represent, right? – 200_success

XOR does not care, but the result maybe a problem: e.g. with say sign-magnitude integers, -1 ^ 1 goes to -0 which maybe a trap value - stopping the code. see C11 §6.2.6.2 2. Bit-wise ops are better used on unsigned types. – chux

Further C11 §6.2.6.2 3 specifies implementation defined behavior for ^ with int on rare non-2's complement platforms . In particular "It is unspecified whether these cases actually generate a negative zero or a normal zero, " rendering a ^ b ^ c ^ smallest ^ largest unspecified that it will work as desired even if a trap value is not used. The next section explains how this can be UB. Best to leave this novel code to unsigned types. – chux

It seems unfortunate that a technique that should be logically and mathematically sound could be derailed by a technicality.

Is there a way to salvage this XOR technique and make it legally safe, ideally with zero runtime overhead? (Something involving unions, maybe?)

Aucun commentaire:

Enregistrer un commentaire