Уменьшение целого числа до 1, если оно не равно 0
Я пытаюсь устранить утечку времени, удаляя оператор if в моем коде, но из-за интерпретации с ++ целочисленных входных данных в операторах if, я застрял.
Обратите внимание, что я предполагаю, что компилятор создает условную ветвь, что приводит к утечке информации о времени!
Оригинальный код:
int s
if (s)
r = A
else
r = B
Сейчас я пытаюсь переписать это как:
int s;
r = sA+(1-s)B
Поскольку s не связан с [0,1], я сталкиваюсь с проблемой, что он неправильно умножается на A и B, если s выходит за пределы [0,1]. Что я могу сделать, не используя if-оператор для s, чтобы решить эту проблему?
заранее спасибо
Решение
Какие у вас есть доказательства того, что утверждение if приводит к утечке времени?
Если вы используете современный компилятор с включенной оптимизацией, этот код не должен создавать ветвь. Вы должны проверить, что делает ваш компилятор, посмотрев на вывод языка ассемблера.
Например, g ++ 5.3.0 компилирует этот код:
int f(int s, int A, int B) {
int r;
if (s)
r = A;
else
r = B;
return r;
}
к этой сборке:
movl %esi, %eax
testl %edi, %edi
cmove %edx, %eax
ret
Смотри, ма! Нет веток! 😉
Другие решения
Если вы знаете число битов в целом числе, это довольно просто, хотя есть несколько сложностей, которые делают его стандартно чистым с возможностью необычного представления целых чисел.
Вот одно простое решение для 32-битных целых чисел:
uint32_t mask = s;
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;
mask &= 1;
r = b ^ (-mask & (a ^ b)):
Пять операторов сдвига и / или распространяют любой установленный бит в mask так что в конце младший бит равен 1, если маска не была изначально 0. Затем мы выделяем младший бит, в результате чего получаем 1 или 0. Последний оператор является бит-эквивалентом двух ваших умножений и добавляем ,
Вот более быстрый, основанный на наблюдении, что если вы вычесть единицу из числа, а бит знака изменится с 0 на 1, то число будет равно 0:
uint32_t mask = ((uint32_t(s)-1U)&~uint32_t(s))>>31) - 1U;
По сути, это то же самое вычисление, что и вычитание 1 с последующим использованием бита переноса, но, к сожалению, бит переноса не предоставляется языку C (за исключением, возможно, встроенных в компилятор встроенных функций).
Возможны и другие варианты.
Единственный способ сделать это без веток, когда оптимизация недоступна, — прибегнуть к встроенной сборке. Предполагая 8086:
mov ax, s
neg ax ; CF = (ax != 0)
sbb ax, ax ; ax = (s != 0 ? -1 : 0)
neg ax ; ax = (s != 0 ? 1 : 0)
mov s, ax ; now use s at will, it will be: s = (s != 0 ? 1 : 0)