Код без веток, который отображает нуль, отрицательный, и положительный 0, 1, 2

Предполагая дополнение до 2, арифметический сдвиг вправо и отсутствие переполнения при вычитании:

#define SHIFT (CHARBIT*sizeof(int) - 1)

int Compare(int x, int y)
{
    int diff = x - y;
    return -(diff >> SHIFT) - (((-diff) >> SHIFT) << 1);
}

Дополнение до двух:

#include <limits.h>
#define INT_BITS (CHAR_BITS * sizeof (int))

int Compare(int x, int y) {
    int d = y - x;
    int p = (d + INT_MAX) >> (INT_BITS - 1);
    d = d >> (INT_BITS - 2);
    return (d & 2) + (p & 1);
}

Предполагая, что компилятор работает нормально, это не вызовет аппаратное обеспечение сравнения вашей системы и не использует сравнение на языке. Чтобы проверить: если x == y, то d и p явно будут равны 0, поэтому окончательный результат будет равен нулю. Если (x - y)> 0, то ((x - y) + INT_MAX) установит старший бит целого числа, в противном случае он будет сброшен. Таким образом, младший бит p будет установлен тогда и только тогда, когда (x - y)> 0. Если (x - y) <0, тогда будет установлен его старший бит, а d установит второй младший бит.

Код без ответвлений (на уровне языка), который отображает отрицательные значения на -1, ноль на 0 и положительные на +1, выглядит следующим образом

int c = (n > 0) - (n < 0);

, если вам нужно другое сопоставление, вы можете просто использовать явное отображение, чтобы переназначить его

const int MAP[] = { 1, 0, 2 };
int c = MAP[(n > 0) - (n < 0) + 1];

или, для запрошенного отображения, использовать какой-нибудь числовой трюк, например

int c = 2 * (n > 0) + (n < 0);

(очевидно, очень легко сгенерировать любое отображение из этого, пока 0 отображается в 0. И код вполне читабелен . Если 0 сопоставляется с чем-то другим, он становится более сложным и менее читаемым.)

В качестве дополнительного примечания: сравнение двух целых чисел путем вычитания одного из другого на уровне языка C является ошибочной техникой, так как обычно имеет тенденцию к переполнению . Прелесть вышеупомянутых методов в том, что их можно сразу же использовать для сравнений без вычитания, например

int c = 2 * (x > y) + (x < y);

Сравнение без знака, которое возвращает -1,0,1 (cmpu), - это один из случаев, на который проверяется GNU SuperOptimizer .

cmpu: compare (unsigned)
int cmpu(unsigned_word v0, unsigned_word v1)
{
    return ( (v0 > v1) ? 1 : ( (v0 < v1) ? -1 : 0) );
}

A SuperOptimizer тщательно ищет в пространстве инструкций наилучшую возможную комбинацию инструкций, которая будет реализовывать данную функцию. Предполагается, что компиляторы автоматически заменят указанные выше функции их супероптимизированными версиями (хотя не все компиляторы делают это). Например, в Руководстве по написанию компилятора PowerPC ( powerpc-cwg.pdf ) функция cmpu показана в Приложении D, стр. 204:

cmpu: compare (unsigned)
PowerPC SuperOptimized Version
subf  R5,R4,R3
subfc R6,R3,R4
subfe R7,R4,R3
subfe R8,R7,R5

Это очень хорошо, не правда ли ... просто четыре вычитания (и с переносом и / или расширенными версиями). Не говоря уже о том, что это действительно без ветвей на уровне кода операции . Вероятно, существует эквивалентная последовательность для ПК / Intel X86, которая так же коротка, поскольку GNU Superoptimizer работает как для X86, так и для PowerPC.

Обратите внимание, что сравнение без знака (cmpu) может быть преобразовано в сравнение со знаком (cmps) на 32-битной системе. сравните, добавив 0x80000000 к обоим входам со знаком перед передачей его в cmpu.

cmps: compare (signed)
int cmps(signed_word v0, signed_word v1)
{
    signed_word offset=0x80000000;
    return ( (unsigned_word) (v0 + signed_word),
        (unsigned_word) (v1 + signed_word) );
}

Это всего лишь один вариант ... SuperOptimizer может найти более короткий cmps, который не должен добавлять смещения и вызывать cmpu.

Чтобы получите запрошенную версию, которая возвращает ваши значения {1,0,2}, а не {-1,0,1}, используйте следующий код, который использует функцию SuperOptimized cmps.

int Compare(int x, int y)
{
    static const int retvals[]={1,0,2};
    return (retvals[cmps(x,y)+1]);
}

Объединение ответов Стивена Кэнона и Тордека:

int Compare(int x, int y)
{
    int diff = x - y; 
    return -(diff >> 31) + (2 & (-diff >> 30));
} 

Результат: (g ++ -O3)

subl     %esi,%edi 
movl     %edi,%eax
sarl     $31,%edi
negl     %eax
sarl     $30,%eax
andl     $2,%eax
subl     %edi,%eax 
ret 

Точно! Однако версия Пола Хси содержит еще меньше инструкций:

subl     %esi,%edi
leal     0x7fffffff(%rdi),%eax
sarl     $30,%edi
andl     $2,%edi
shrl     $31,%eax
leal     (%rdi,%rax,1),%eax
ret

int Compare(int x, int y)
{
    int diff = x - y;

    int absdiff = 0x7fffffff & diff; // diff with sign bit 0
    int absdiff_not_zero = (int) (0 != udiff);

    return
        (absdiff_not_zero << 1)      // 2 iff abs(diff) > 0
        -
        ((0x80000000 & diff) >> 31); // 1 iff diff < 0
}

Я присоединяюсь к исходному ответу Тордека:

int compare(int x, int y) {
    return (x < y) + 2*(y < x);
}

Компиляция с gcc -O3 -march = pentium4 приводит к получению кода без ветвей, который использует условные инструкции setg и setl (см. это объяснение инструкций x86 ).

push   %ebp
mov    %esp,%ebp
mov    %eax,%ecx
xor    %eax,%eax
cmp    %edx,%ecx
setg   %al
add    %eax,%eax
cmp    %edx,%ecx
setl   %dl
movzbl %dl,%edx
add    %edx,%eax
pop    %ebp
ret 

Good god, this has haunted me.

Whatever, I think I squeezed out a last drop of performance:

int compare(int a, int b) {
    return (a != b) << (a > b);
}

Although, compiling with -O3 in GCC will give (bear with me I'm doing it from memory)

xorl  %eax, %eax
cmpl  %esi, %edi
setne %al
cmpl  %esi, %edi
setgt %dl
sall  %dl, %eax
ret

But the second comparison seems (according to a tiny bit of testing; I suck at ASM) to be redundant, leaving the small and beautiful

xorl  %eax, %eax
cmpl  %esi, %edi
setne %al
setgt %dl
sall  %dl, %eax
ret

(Sall may totally not be an ASM instruction, but I don't remember exactly)

So... if you don't mind running your benchmark once more, I'd love to hear the results (mine gave a 3% improvement, but it may be wrong).