Monday, November 19, 2012

Branch-free detection of sign

I found something wrong in the following video,

https://www.youtube.com/watch?v=Z59REm2YKX0

The branch free code by author is,


bool OppositeSign(int a, int b) {
    return (a ^ b) < 0;
}

But the compiler can internally convert the statement "return (a ^ b) < 0;" into conditional code.

Here is a branch free code, if the processor provide bit manipulation instructions (most of the processors provide)



// except inputs every thing is compile time constant
bool OppositeSign(int a, int b) {
    unsigned const shift = sizeof(int)*8-1;
    unsigned const mask  = 1 << shift;
   
    return unsigned((a&mask)^(b&mask)) >> shift;
}


No comments: