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

Question

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

f(x, SOME_CONSTANT) -> returns -x (or any negative value) 
f(x, SOME_CONSTANT2) -> returns x (or any positive value) 
f(0, SOME_CONSTANT) -> returns 0 
f(0, SOME_CONSTANT2) -> returns 0 

без умножения/ветвление, насколько это возможно.

На первый взгляд х^0x80000000 кажется кандидатом, но он не работает, когда х = 0.

Answer 1

Хорошо, я, наконец, понял, как сделать это эффективно:

Java:

int f(int x, int y) { 
    return (((x >> 31) | ((unsigned)-x >> 31))^y) - y; 
} 

C/C++:

int f(int x, int y) { 
    return (((x > 0) - (x < 0))^y) - y; 
} 

Приведенные выше функции возвращают -sgn(x) у есть -1 и sgn(x) othe rwise.

Или, если нам просто нужно работать для каждого значения, отличного от -2^31 (минимальное значение без знака int), с сохранением абсолютного значения, это функция, которая переворачивает знак, в зависимости от переменной у:

int f(int x, int y) { 
    return (x^y) - y; // returns -x for y == -1, x otherwise 
} 

вывод: -x == ~ х + 1 == (х^0xFFFFFFFF) + 1 == (х^-1) + 1 == (х^-1) - (-1). Подставляя -1 с y, мы получаем формулу с двумя переменными, которая имеет интересное свойство, которое возвращает неизмененное x, если y задано равным 0, потому что ни (x^0), ни вычитание 0 не изменяет результат. Теперь угол случае, если x равна 0x8000000, когда эта формула не работает. Это можно исправить, применяя функцию sgn (x), поэтому мы имеем (sgn(x)^y) - y). Наконец, мы заменим функции sgn (x) на хорошо известные формулы, не использующие ветвление.

Answer 2

Вот довольно лаконична выражение, которое будет решать эту проблему:

return ((x < 0^y) & x!=0) << 31 | (x!=0) <<31>> 31 & 0x7fffffff & x | x==0x80000000 ;

Это будет работать для целых чисел дополнения 32 бит 2, где x - вход, а y - 1 или 0. 1 означает возврат противоположного знака x, 0 означает возврат того же знака, что и x.

Вот более длинная версия этого выражения в функции f(). Я добавил несколько тестовых примеров для проверки.

#include <limits.h> 
#include <stdio.h> 

int bitsm1 = 31; 
int rightbits = 0x7fffffff; 


int f (x, y) { 
    int sign_x = x < 0; 
    int signtemp = sign_x^y; 
    int notzero = x!=0; 
    int v = notzero << bitsm1; 
    v = v >> bitsm1; 
    v = v & rightbits; 
    int b = v & x; 
    int c = (signtemp & notzero) << bitsm1; 
    int z = c | b; 
    int res = z | (x==INT_MIN); 
    return res; 
} 


int main() { 
printf("%d\n", f(0,0)); // 0 
printf("%d\n", f(0,1)); // 0 
printf("%d\n", f(1,0)); // + 
printf("%d\n", f(1,1)); // - 
printf("%d\n", f(-1,0)); // - 
printf("%d\n", f(-1,1)); // + 
printf("%d\n", f(INT_MAX,0)); // + 
printf("%d\n", f(INT_MAX,1)); // - 
printf("%d\n", f(INT_MIN,0)); // - 
printf("%d\n", f(INT_MIN,1)); // + 


return 0; 
}