減少操作次數

Question

我有一個函數來查找三個數字的最大值，但它使用了24個操作數，我想將它減少到20個操作數。僅使用按位操作。

int maxOfThree(int x, int y, int z) { 
int a1 = (x+(~y+1))>>31; 
int a2 = (x+(~z+1))>>31; 
int a3 = (y+(~z+1))>>31; 
return ((~a1&((a2&z)|(~a2&x))) | (a1& ((a3&z)|(~a3&y)))) ; 
} 

Answer 1

假設你的代碼編寫不使用任何「非法」操作（即你是+1 OK），那麼你可以寫

#include <stdio.h> 

int main(void) { 
int x, y, z; 
int mxy, mxyz; 
x = 5; 
y = 123; 
z = 9; 
mxy = x - ((x - y) & ((x - y) >> 31)); // max(x, y) 
mxyz = mxy - ((mxy - z) & ((mxy - z) >> 31)); 
printf("max is %d\n", mxyz); 
} 

只有10人作戰。每-可以用一個~和+1來代替，再添加6個操作。我將把它作爲一個練習。要點是 - 您無需分別評估max(x,y)和max(y,z)和max(x,z)。 max(x,y,z) = max(max(x,y),z) ......這就是你的儲蓄來自哪裏。只使用+1和位運算符

UPDATE：

#include <stdio.h> 

int main(void) { 
    unsigned int x, y, z, r; 
    unsigned int mxy, mxyz; 
    unsigned int xmy; 
    unsigned int mxymz; 

    x = 5; 
    y = 123; 
    z = 9; 
    xmy = x + (~y+1); // x minus y 
    mxy = x + ~(xmy & (xmy >> 31)) + 1; // max(x, y) 
    mxymz = mxy + (~z+1); // max(x,y) minus z 
    mxyz = mxy + (~(mxymz & (mxymz >> 31))+1); // max(x,y,z) 
    printf("max is %d\n", mxyz); 
} 

16，營業總（加3箇中間分配給變量，如果你不算那些）。僅使用+ ~ >>。我認爲這很重要。

幾個要點：

1. 硬連線值31真的應該sizeof(int) * CHAR_BIT - 1
2. 您應該使用無符號整數，因爲>>31操作建議不要在符號整數（見https://www.securecoding.cert.org/confluence/display/seccode/INT13-C.+Use+bitwise+operators+only+on+unsigned+operands）