Java利用位運算實現比較兩個數的大小
題目要求
如何不要用任何比較判斷符(>
,==
,<
),返回兩個數( 32 位整數)中較大的數。
主要思路
方法1(不考慮溢出)
要比較 a 和 b 的大小,因為不能用比較符號,我們可以通過 a – b 的符號位來判斷,如果 a – b 的符號位是 1,說明 a – b < 0,則 a 小,否則 a 大或者 a 和 b 相等。
如何判斷一個數的符號位是 0 還是 1 ?
由於是 32 位整數,所以如果將一個數右移 31 位,然後和 1 相與(&
),如果得到 1,則這個數是負數,如果得到 0,則這個數是正數。
舉個具體例子,如果要求 a 和 b 誰大,我們可以先通過
((a - b) >> 31) & 1
得到一個值,如果這個值是 1 ,說明 a 小,否則 a 大或者 a 和 b 相等。
由於不能出現比較符號,所以無法使用如下代碼
return ((a - b) >> 31) & 1 == 1?b:a;
也無法使用如下代碼
if (((a - b) >> 31) & 1 == 1){ return b; } return a;
但是我們可以巧妙利用((a - b) >> 31) & 1
結果去構造一個公式,這個公式可以在((a - b) >> 31) & 1 == 1
情況下得到 b, 在((a - b) >> 31) & 1 == 0
情況下得到 a。
我們可以利用一個反轉函數
public int flip(int n) { return n ^ 1; }
這個函數的作用就是,當n == 1
時,返回 0,當n == 0
時,返回 1,我們將判斷符號的結果flip
一次,如下代碼
public static int sign(int n) { return flip((n >> 31) & 1); }
這個方法的作用就是
當符號位是 1 的時候,返回 0,符號位是 0 的時候,返回 1。
這樣flip
後,
sign(a - b)
如果得到 1, 則:a - b > 0
,則返回 a。
sign(a - b)
如果得到 0, 則:a - b <= 0
,則返回 b。
公式可以定義成
sign(a - b) * a + flip(sign(a - b)) * b
主函數直接做如下調用
public static int getMax1(int a, int b) { int c = a - b; //當符號位是 1 的時候,scA = 0,符號位是 0 的時候,scA = 1。 int scA = sign(c); // scA = 1 時,scB = 0,scA = 0時,scB = 1 int scB = flip(scA); // 如果 scA = 0,說明 b 大,直接返回b // 如果 scA = 1,說明 a 大,直接返回a return a * scA + b * scB; }
這個方法沒有考慮溢出的情況,比如
a = 2147483647; b = -2147480000;
a - b
直接就溢出瞭,後面的算法就都不適用瞭。
方法2(考慮溢出情況)
那我們可以先比較 a 與 b 兩個數的符號,
會有如下幾種情況:
情況1:符號不同,則直接返回符號為正的那個數。
情況2:如果符號相同,則這種情況下,a - b
的值絕對不會溢出,那麼就看 c 的符號(c為正返回a,c為負返回b)
方法2的核心代碼如下
int c = a - b; int sa = sign(a); int sb = sign(b); int sc = sign(c); int difSab = sa ^ sb; int sameSab = flip(difSab); int returnA = difSab * sa + sameSab * sc; int returnB = flip(returnA); return a * returnA + b * returnB;
其中: int difSab = sa ^ sb
就是判斷 a 和 b 的符號是否一樣,如果 difSab == 1
,則 a 和 b 符號一樣,如果difSab == 0
,則a 和 b符號不一樣。
隻有當difSab == 0
的時候,要考慮 c 的符號。因為difSab == 0
,所以int returnA = 0 * sa + 1 * sc;
,即int returnA = sc
,如果 sc 為 1,說明 c 的符號是 0,則a - b > 0
,返回 a 即可,否則返回 b。
方法1和方法2的完整代碼和測試代碼如下:
// 不要用任何比較判斷,返回兩個數中較大的數 public class Code_GetMax { public static int flip(int n) { return n ^ 1; } public static int sign(int n) { return flip((n >> 31) & 1); } public static int getMax1(int a, int b) { int c = a - b; int scA = sign(c); int scB = flip(scA); return a * scA + b * scB; } public static int getMax2(int a, int b) { int c = a - b; int sa = sign(a); int sb = sign(b); int sc = sign(c); int difSab = sa ^ sb; int sameSab = flip(difSab); int returnA = difSab * sa + sameSab * sc; int returnB = flip(returnA); return a * returnA + b * returnB; } public static void main(String[] args) { int a = -16; int b = -19; System.out.println(getMax1(a, b)); System.out.println(getMax2(a, b)); a = 2147483647; b = -2147480000; System.out.println(getMax1(a, b)); // wrong answer because of overflow System.out.println(getMax2(a, b)); } }
到此這篇關於Java利用位運算實現比較兩個數的大小的文章就介紹到這瞭,更多相關Java位運算內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!