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

さて、私はついにこれを効率的に行う方法を見つけました：

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 ^ 0）も0を引いても結果が変わらないため、yが0に設定されている場合に変更されていないxを返す興味深いプロパティを持つ2変数の式が得られます。ここでのコーナーケースは、この式が機能しないときに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 に答える