Как я могу переписать этот оператор if-else, чтобы он не использовал переход?

Question

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

Проблема выглядит так:

if (x)
    y = a;
else
    y = b;

x может быть только 0 или 1. Как записать это условие без перехода?

Одно решение со структурой данных:

int temp[2] = {b, a};
y = temp[x];

Другое арифметическое решение:

y = x * a + (1 - x) * b;

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

Answer 1

y = a ^ ((x - 1U) & (a ^ b));

Используется побитовый х или

Answer 2

Вы говорите, что не хотите переходить в коде source или на уровне процессора?

На моем компиляторе

int choose(int x, int a, int b)
{
    int y;

    if (x)
        y = a;
    else
        y = b;

    return y;
}

компилируется в это -

test    ecx, ecx
cmovne  r8d, edx
mov eax, r8d
ret 0

Хотя я написал переход на уровне кода C, в сгенерированном машинном коде его нет, так как компилятор может использовать инструкцию условного перемещения.

Answer 3

Возможно, это не лучшее решение, но я думаю, что оно является побитовым эквивалентом без переходов:

y = (~(x*UINT_MAX) & a) | (~(1 - x) & b);

Answer 4

Для процессоров, которые допускают условное выполнение операторов:

y = a;
if (x != 0) y = b;

На процессоре ARM в 32-битном режиме это должно переводиться в следующие псевдоинструкции:

mov y, a; move a into y.
test x; (or XOR X, X ; to set condition codes)
MOVNZ y, b ; move b into y if condition is non-zero.

Без переходовучаствует здесь, по крайней мере, на уровне ассемблера.

Примечание. Решение для конкретной платформы может быть недействительным для процессоров без возможности выполнения условных инструкций.

Answer 5

Я согласен с Йенсом; троичный оператор сделает трюк без прыжка.

y = x ? a : b

Кстати, есть дочерний сайт, Code Golf , где люди задают вопросы такого типа: «Как я могу решить проблему x с кратчайшим количеством кода при сохранении ограничения y?»

Answer 6

Используйте троичный оператор ?:. Это сделано для этого.

Answer 7

Что-то вроде функции выбора здесь?

#include <stdio.h>

int choose(unsigned int x, int a, int b)
{
    unsigned int selector = -x;    

    return (a & selector) | (b & ~selector);
}

int main()
{
    printf("%d\n", choose(0, 123, 200));
    printf("%d\n", choose(1, 123, 200));
}

Answer 8

В следующем коде используется прием, который, поскольку x равен 1 или 0, x-1 равен 0 или -1 (например, 0xFFFFFFFF, предполагая 32-битное целое число: с). Если x равно 1, результат & равен нулю, поэтому результат равен a. Когда x равно нулю, результат & будет b-a, тогда общий результат будет a+(b-a) или просто b.

int test(int x, int a, int b)
{
  return a + ( (((unsigned int)x)-1) & (b - a) );
}

На фиктивном микроконтроллере (без каких-либо необычных инструкций условного перемещения) это приведет к четырем инструкциям:

ADD   #-1 R12
SUB   R13, R14
AND   R14, R12
ADD   R13, R12

Правда, это очень похоже на решение XOR, опубликованное @ 6502.

Answer 9

РЕДАКТИРОВАТЬ: я неправильно понял вопрос, который гласит, что код C не должен использовать переход вообще.

Я думаю, я бы пошел с

y = b;
if (x)
    y = a;

Если я правильно прочитал следующий дизассемблированный код, то должен быть только один переход:

0000000000400474 <main>:
  400474:   55                      push   %rbp
  400475:   48 89 e5                mov    %rsp,%rbp
  400478:   8b 45 fc                mov    -0x4(%rbp),%eax
  40047b:   89 45 f8                mov    %eax,-0x8(%rbp)
  40047e:   83 7d f4 00             cmpl   $0x0,-0xc(%rbp)
  400482:   74 06                   je     40048a <main+0x16>
  400484:   8b 45 f0                mov    -0x10(%rbp),%eax
  400487:   89 45 f8                mov    %eax,-0x8(%rbp)
  40048a:   c9                      leaveq
  40048b:   c3                      retq
  40048c:   90                      nop
  40048d:   90                      nop
  40048e:   90                      nop
  40048f:   90                      nop

Answer 10

switch (x) {
   case 1:
      y = a;
      break;
   default:
      y = b;
      break;
}

РЕДАКТИРОВАТЬ: оригинальный вопрос сказал "с прыжками" ... не "без"