最多三個使用按位運算的整數？

如何僅使用按位操作返回三個無符號整數的最大值，如！，〜，|，&，^，+，>>，< <。我不知道從哪裏開始。任何幫助，將不勝感激。最多三個使用按位運算的整數？

編輯：

我只允許使用特定的法律OPS，多數民衆贊成它。

/** maxOfThree - Returns the maximum of three integers. 
* NOTE: x, y, z are all in the range [0, TMax]. 
* Examples: maxOfThree(1, 2, 3) = 3 
* Legal Ops: ! ~ &^| + << >> 
* Max Ops: 25 
int maxOfThree(int x, int y, int z) { 
}

來源

2014-02-16 user3316874

由於您根本沒有任何代碼顯示，因此您可以參考以下提示：在1到100之間取10個整數。對它們進行排序記下它們的二進制表示。看看二進制數字。也許你有一個想法。 –

查看「bit-twiddling hacks」頁面，並研究如何實現最大值/最小值。

如果你能弄清楚兩個數字的最大值是如何工作的，那麼你可以將這個情況歸納爲三個數字。

讓我向你解釋一下這兩個號碼的情況下獲得最大的價值：

-(a<b)可以返回-1或0，那麼你可以有11111111 11111111 11111111 11111111（-1補一個int）或00000000 00000000 00000000 00000000（-0.0爲int）。

記住，a^b^b = a和a^b^a = b（無關緊要的順序是什麼，這是xor操作），你有，在第一種情況：

如果a < b需要返回b的結果，所以

a^((a^b) & -(a < b))必須等於a^a^b ..和實際上它是因爲-(a<b)返回11111111 11111111 11111111 11111111，和上一個和按位操作爲無符號整數使編號保持不變...因此a^a^b = b。這是最大的。

如果a > b然後a < b是假的，從而(anything & 00000000 00000000 00000000 00000000)爲0。因此你纔會有a^0，這是一個。最大值。

最後，我們有解決方案概括爲三個數字：

#include <stdio.h> 

int getMax(unsigned int a, unsigned int b, unsigned int c) { 
    int temp = a^((a^b) & -(a < b)) ; 
    int r = c^((c^temp) & -(c < temp)); 
    return r; 
} 

int main(void) { 
    unsigned int a = 3, b = 1, c = 9; 

    printf("%d", getMax(a,b,c)); 
    return 0; 
}

編輯：如果你不能使用「<」，然後使用第二個版本

x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));

並記住以下摘錄

請注意，1989 ANSI C規範未指定簽名右移的結果，因此這些不可移植。如果在溢出時拋出異常，則x和y的值應爲無符號或強制轉換爲以避免不必要的減法，以避免不必要地拋出異常，但是右移需要有符號操作數才能生成所有一位負，所以轉換爲簽訂有

編輯II：這應該與您發佈的規範工作：

#include <stdio.h> 

int getMax(int x, int y, int z) { 
    int r = (x + ~((x+~y+1) & ((x+~y+1) >> 31))+1); // if possible use sizeof(int)*sizeof(char)+~0 instead of 31 
    int r2 = (z + ~((z+~r+1) & ((z+~r+1) >> 31))+1); // if possible use sizeof(int)*sizeof(char)+~0 instead of 31 
    return r2; 
} 

int main(void) { 
    unsigned int a = 5, b = 7, c = 1; 

    printf("%d", getMax(a,b,c)); 
    return 0; 
}

請注意，這將是，如果你不需經過更好d使用sizeof（）而不是假設int是4字節（在所有平臺上都不是這樣）。

來源

2014-02-16 21:12:47

我不認爲你被允許使用'<'。 –

幸運的是，你*可以使用'{'。這些學校任務有多傻？ – usr2564301

就像我喜歡這個頁面一樣，上面的回答並不完美，因爲如果允許'a a） *（ba）'，這比上面簡單得多。我不認爲'a abligh

如果你可以使用-（你建議+），我建議以下（未經測試），我認爲它比位旋轉頁更高效，特別是如果第一個max是作爲宏，並且我們知道我們正在處理簽署的整數。

#define MAX2(a,b) (a-((a-b) >> (sizeof(int) * CHAR_BIT - 1))*(b-a)) 
int 
max3 (int x, int y, int z) 
{ 
    return MAX2(MAX2(x, y), z); 
}

CHAR_BIT應該#define倒是到8在大多數平臺上。

這也依賴於負數右移的未定義行爲。

如果您不允許使用-，使用~和另外1

大衛Kernin的回答就比較一般了，雖然。

來源

2014-02-16 21:42:48 abligh

最多三個使用按位運算的整數？

回答

相關問題