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

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

2 голосов
/ 01 февраля 2011

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

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

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

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

Ответы [ 2 ]

2 голосов
/ 16 февраля 2011

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

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) y, равное -1 и sgn(x) в противном случае.

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

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

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

0 голосов
/ 02 февраля 2011

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

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;
}
...