Преобразование в вещественные последовательные операторы if

Question

Я застрял там, пытаясь понять, как преобразовать последние два оператора «если» следующего кода в состояние без разветвления.

int u, x, y; 
x = rand() % 100 - 50; 
y = rand() % 100 - 50; 

u = rand() % 4; 
if (y > x) u = 5; 
if (-y > x) u = 4; 

Или, в случае выше оказывается слишком сложным, вы можете рассматривать их как:

if (x > 0) u = 5; 
if (y > 0) u = 4; 

Я думаю, что заставляет меня является тот факт, что те не имеют else зрелище. Если бы это было так, я мог бы, вероятно, адаптировать вариацию бесконтактной функции abs (или max/min).

rand() Функции, которые вы видите, не являются частью реального кода. Я добавил их так, чтобы просто намекнуть на ожидаемые диапазоны, которые могут иметь переменные x, y и u в то время, когда происходят две ветви.

Сборочный код машины разрешен для этой цели.

EDIT:

После немного braingrinding мне удалось собрать рабочую безфилиальные версию:

int u, x, y; 
x = rand() % 100 - 50; 
y = rand() % 100 - 50; 

u = rand() % 4; 
u += (4-u)*((unsigned int)(x+y) >> 31); 
u += (5-u)*((unsigned int)(x-y) >> 31); 

К сожалению, из-за целочисленную арифметику вовлеченной, оригинальная версия с если заявлениями оказывается быстрее на 30%.

Компилятор знает где вечеринка в.

Answer 1

[Все: этот ответ был написан с предположением, что вызовы rand() были частью проблемы. Я предлагаю улучшение ниже в этом предположении. OP запоздало разъясняет, что он использовал только rand, чтобы рассказать нам диапазоны (и предположительно распределения) значений x и y. Неясно, имел ли он значение для u. Во всяком случае, наслаждайтесь моим улучшенным ответом на проблему, которую он действительно не представлял].

Я думаю, вы бы лучше перекодирования это как:

int u, x, y; 
x = rand() % 100 - 50; 
y = rand() % 100 - 50; 

if (y > x) u = 5; 
else if (-y > x) u = 4; 
else u = rand() % 4; 

Это вызывает последний ранд только 1/4 так часто, как исходный код ФП в. Поскольку я полагаю, что rand (и деления) намного дороже , чем сравнение и ветвь, это будет значительной экономией.

Если ваш генератор рэнд производит много истинно случайных битов (например, 16) на каждом вызове, как должно, вы можете назвать это только один раз (я предполагал рэнд дороже водораздела YMMV):

int u, x, y, t; 
t = rand() ; 
u = t % 4; 
t = t >> 2; 
x = t % 100 - 50; 
y = (t/100) %100 - 50; 

if (y > x) u = 5; 
else if (-y > x) u = 4; 

Я думаю, что функция rand в библиотеке MS C недостаточно хороша для этого, если вы хотите действительно случайные значения. Я должен был закодировать свой собственный; в любом случае, оказалось быстрее.

Вы можете также избавиться от разрыва, используя умножение на ответный (непроверенный):

int u, x, y; 
unsigned int t; 
unsigned long t2; 
t = rand() ; 
u = t % 4; 

{ // Compute value of x * 2^32 in a long by multiplying. 
    // The (unsigned int) term below should be folded into a single constant at compile time. 
    // The remaining multiply can be done by one machine instruction 
    // (typically 32bits * 32bits --> 64bits) widely found in processors. 
    // The "4" has the same effect as the t = t >> 2 in the previous version 
    t2 = (t * ((unsigned int)1./(4.*100.)*(1<<32)); 
} 
x = (t2>>32)-50; // take the upper word (if compiler won't, do this in assembler) 
{ // compute y from the fractional remainder of the above multiply, 
    // which is sitting in the lower 32 bits of the t2 product 
    y = (t2 mod (1<<32)) * (unsigned int)(100.*(1<<32)); 
} 

if (y > x) u = 5; 
else if (-y > x) u = 4; 

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

Answer 2

Некоторые трюки, использующие индексы массивов, могут быть довольно быстрыми, если компилятор/процессор имеет одноэтапные инструкции для преобразования результатов сравнения в значения 0-1 (например, «sete» x86 и т. Д.).

int ycpx[3]; 

/* ... */ 
ycpx[0] = 4; 
ycpx[1] = u; 
ycpx[2] = 5; 
u = ycpx[1 - (-y <= x) + (y > x)]; 

Альтернативные формы

int v1[2]; 
int v2[2]; 

/* ... */ 
v1[0] = u; 
v1[1] = 5; 
v2[1] = 4; 
v2[0] = v1[y > x]; 
u = v2[-y > x]; 

почти нечитаемым ...

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