c ++中的三向条件确定两个数字的符号等值

Question

我需要最有效的方法(在cpu周期中)来确定两个数字是否具有相同/不同的符号.但问题是,如果任一数字为零,我需要能够将其与具有相同/不同符号的数字区分开(即,零被视为"第三"符号).以下代码与我需要的类似,但只要只有三个不同的返回值,返回值就可以是任何值.

int foo(int x, int y) {
    if (x * y > 0) return 1;
    if (x * y < 0) return -1;
    return 0;
}

对于我的具体问题,值在[-6,6]范围内,并且X保证不为0.我找到了一个解决方案,找出两个数字是否具有相同的符号,并对其进行修改以获得以下解决方案.

return y? (((x^y) >= 0)? 1 : -1) : 0;

应该有一些bitops /比较比使用乘法,分支,比较更快的结果.

Answer 1

怎么样:

int foo(int x,int y)
{
    // As suggested by Luther Blissett below in the comments.
    // Increased the size of the array to 16x16.
    // This allows for simpler optimization for the compiler
    // Also use +8 rather +6 in the hopes that compiler optimization will be easier
    // you never know (there may be some fancy trick.
    static int sign[16][16] = {
                { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1},
                { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1},
                { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1},
                { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1},
                { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1},
                { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1},
                { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1},
                { 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, -1, -1, -1, -1, -1, -1},
                { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1},
                { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1},
                { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1},
                { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1},
                { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1},
                { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1},
                { -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1}
            };

    return sign[x+8][y+8];
}

这应该很快,因为没有分支会使处理器停滞不前.

使用g ++ -O3 -S:

__Z3fooii:
  pushl   %ebp
  movl    %esp, %ebp
  movl    8(%ebp), %eax
  movl    12(%ebp), %edx
  popl    %ebp
  sall    $4, %eax
  addl    %edx, %eax
  movl    _ZZ3fooiiE4sign+544(,%eax,4), %eax
  ret

Answer 2

这是另一个版本(具有丑陋的,非便携式位操作技巧):

int foo(int x, int y) {
    return ((x^y) >> 4) - ((x^(-y)) >> 4);
}

一些解释:

• ((x^y) >> 4) 如果x和y中只有一个是负数,则为-1,否则为0.
• ((x^(-y)) >> 4) 如果x和-y中只有一个是负数,则为-1,否则为0.
• 如果x> 0且y> 0,则结​​果为0 - (-1)= 1.
• 如果x <0且y <0,则结果为0 - (-1)= 1.
• 如果x> 0且y = 0,则结​​果为0 - 0 = 0.
• 如果x <0且y = 0,则结​​果为(-1) - ( - 1)= 0.
• 如果x> 0且y <0,则结果为(-1) - 0 = -1.
• 如果x <0且y> 0,则结​​果为(-1) - 0 = -1.

假设二进制补码算法并假设>>使用符号扩展进行移位.

Answer 3

你的例子没有用,因为你没有括号括起来(x ^ y)

这是有效的:

return y? (((x^y) >= 0) ? 1 : -1) : 0;

如果你想返回-1,1或0,我认为你不能做得更快.这是因为-1是11111111并且与0和1完全不同.一组位操作将返回11111111,0或1会很复杂,肯定比上面的代码慢.

编辑:如果不是-1和1,你可以处理任何负数或正数,那么你可以消除一个分支

return y ? ((x^y) | 1) : 0;

Answer 4

编辑:

((x*y)>>7) | -(-(x*y)>>7)

如果两者都是相同的符号,则返回1,如果两者是不同的符号则返回-1.
如果两者都是正数,则返回1,如果两者都是负数,则返回-1.

假设有符号的32位值.使用| x,y | <7,您可以移动3.

  ((x&y)>>31)  // -1 or 0
-((-x&-y)>>31) //  1 or 0

((x&y)>>31) | -((-x&-y)>>31)

假设<是1或0.

-((x&y)<0)     // -1 or 0
((-x&-y)<0)    //  1 or 0

-((x&y)<0) | ((-x&-y)<0)

无论哪种方式看起来像8个操作.