Трехстороннее условное в c ++ для определения знака эквивалентности двух чисел

Question

Мне нужен наиболее эффективный способ (в циклах процессора), чтобы определить, имеют ли два числа одинаковый / разный знак. Но выгода в том, что если любое число равно нулю, мне нужно уметь отличать его от чисел с одинаковыми / разными знаками (т. Е. ноль рассматривается как «третий» знак ). Следующий код похож на то, что мне нужно, но возвращаемые значения могут быть любыми, если только есть три различных возвращаемых значения.

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;

Должны быть некоторые биты / сравнения, которые дают более быстрые результаты, чем использование умножения, ветвления, сравнения.

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) равно -1, если ровно один из x и y отрицателен, в противном случае он равен 0.
• ((x^(-y)) >> 4) равно -1, если ровно один из x и -y отрицателен, в противном случае он равен 0.
• Если x> 0 и y> 0, результат будет 0 - (-1) = 1.
• Если x <0 и y <0, результат будет 0 - (-1) = 1. </li>
• Если x> 0 и y = 0, результат будет 0 - 0 = 0.
• Если x <0 и y = 0, результат будет (-1) - (-1) = 0. </li>
• Если x> 0 и y <0, результат будет (-1) - 0 = -1. </li>
• Если 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. </p>

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

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

Предполагая, что <равно 1 или 0. </p>

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

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

В любом случае похоже на 8 операций.

Answer 5

Чтобы выразить знак числа x как "нормализованное" целое число (т.е. -1, 0, +1), используйте

inline int sign(int x) { return (x > 0) - (x < 0); }

Исходя из вышеизложенного, для сравнения x и y для равенства знаков используйте

inline bool same_sign(int x, int y) { 
  return sign(x) == sign(y);
}

для логического результата.

Или, для -1, 0, +1 результат

inline int compare_sign(int x, int y) { 
  return sign(x) * sign(y);
}

Насколько эффективным будет ваш финальный код, конечно же, зависит от качества компилятора, который вы используете.

Answer 6

Вы могли бы сделать что-то вроде этого (Только с правильными именами переменных и сделать гораздо менее уродливо!) Обратите внимание, что работает ТОЛЬКО с номерами комплиментов 2s, и если ваши значения ограничены от -6 до 6, как в ваших вопросах.

Профилируйте его, чтобы убедиться, что это быстрее, чем простой способ, и ТОЛЬКО пишите такой код, как только вы определили, что не можете удовлетворить свои требования, используя гораздо более очевидный подход. с предсказанием ветвлений и т. д., ветки не всегда медленны, например, на x86. Я бы никогда не написал непереносимый код, как этот, если бы у меня не было выбора для удовлетворения требований к производительности.

В основном извлекаем биты знака и эксклюзив или их, чтобы получить желаемый результат.

int foo(int x, int y)
{
    int s;

    if (x == 0 || y == 0) return 0;

    x = x >> 4; // Bit 0 of x will be the sign bit of x
    y = y >> 4; // Bit 0 of y will be the sign bit of y

    s = (x ^ y) & 1; // sign is 0 if they have the same sign, 1 otherwise

    return  1 - 2 * s;  // Make it 1 for the same sign, -1 otherwise
}

это компилируется на моем компиляторе в пару быстрых тестов на ноль и что после этого выглядит довольно эффективной битовой манипуляцией ...

    test    ecx, ecx
    je  SHORT $LN1@foo
    test    edx, edx
    je  SHORT $LN1@foo
; Line 12
    xor ecx, edx
    mov eax, 1
    sar ecx, 4
    and ecx, 1
    add ecx, ecx
    sub eax, ecx
; Line 13
    ret 0
$LN1@foo:
; Line 5
    xor eax, eax
; Line 13
    ret 0

Answer 7

Если ограничение [-6 .. + 6] не выполняется (ни x! = 0), решение без ответвлений дается (5 операций):

x*= y;
return (x >> 31) - (-x >> 31); // Sign(x * y)

и решение, которое работает для полного целочисленного диапазона (9 ops):

return ((x >> 31) - (-x >> 31)) * ((y >> 31) - (-y >> 31)); // Sign(x) * Sign(y)

Answer 8

Смесь решений AndreyT и Loki Astari: безветвительные, компактные, эффективные (два поиска в одномерном массиве, один умноженный):

static int S[13]= { -1, -1, -1, -1, -1, -1, 0, +1, +1, +1, +1, +1, +1 }, * Sign= &S[6];

return Sign[x] * Sign[y];

В качестве альтернативы, менее компактный, более эффективный подход (одно умножение, один поиск в одномерном массиве):

static int S[73]= { 
-1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1,
-1, -1, -1, -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, +1, +1, +1,
 +1, +1, +1, +1, +1, +1,
 +1, +1, +1, +1, +1, +1,
 +1, +1, +1, +1, +1, +1 }, * Sign= &S[36];

return Sign[x * y];