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
anda ^ 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. – chuxFurther 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