如何使用一些常量和運算符（S）不用乘法/分支

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 

/分支，儘可能高效。

乍一看X^0x80000000的似乎是一個候選，但是當x爲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) y是其他-1 and sgn(x)其他rwise。或者，如果我們只需要爲-2^31（最小無符號整型值）以外的每個值工作，並保留絕對值的好處，則這是根據變量翻轉符號的函數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）函數。

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