3

我正在寻找一个表达式，它可以让我使用以下属性进行编写：

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 时它不起作用。

4

2 回答 2

2

好的，我终于想出了如何有效地做到这一点：

爪哇：

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（最小无符号 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)。用 y 代替 -1，我们得到一个二变量公式，它有一个有趣的属性，如果 y 设置为 0，则返回不变的 x，因为 (x ^ 0) 和减去 0 都不会改变结果。现在，极端情况是如果 x 等于 0x8000000，则此公式不起作用。这可以通过应用 sgn(x) 函数来解决，所以我们有(sgn(x) ^ y) - y). 最后，我们用不使用分支的众所周知的公式替换 sgn(x) 函数。

于 2011-02-16T10:43:18.730 回答
0

这是一个相当简洁的表达式，可以解决这个问题：

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;
}
于 2011-02-02T01:28:25.567 回答