Java利用位運算實現(xiàn)比較兩個數(shù)的大小
題目要求
如何不要用任何比較判斷符（>,==,<），返回兩個數(shù)( 32 位整數(shù))中較大的數(shù)。
主要思路
方法1（不考慮溢出）
要比較 a 和 b 的大小，因為不能用比較符號，我們可以通過 a - b 的符號位來判斷，如果 a - b 的符號位是 1，說明 a - b < 0，則 a 小，否則 a 大或者 a 和 b 相等。
如何判斷一個數(shù)的符號位是 0 還是 1 ？
由于是 32 位整數(shù)，所以如果將一個數(shù)右移 31 位，然后和 1 相與(&)，如果得到 1，則這個數(shù)是負(fù)數(shù)，如果得到 0，則這個數(shù)是正數(shù)。
舉個具體例子，如果要求 a 和 b 誰大，我們可以先通過
((a - b) >> 31) & 1 得到一個值，如果這個值是 1 ，說明 a 小，否則 a 大或者 a 和 b 相等。
由于不能出現(xiàn)比較符號，所以無法使用如下代碼
return ((a - b) >> 31) & 1 == 1?b:a;
也無法使用如下代碼
if (((a - b) >> 31) & 1 == 1){
return b;
}
return a;
但是我們可以巧妙利用((a - b) >> 31) & 1結(jié)果去構(gòu)造一個公式，這個公式可以在((a - b) >> 31) & 1 == 1情況下得到 b， 在((a - b) >> 31) & 1 == 0情況下得到 a。
我們可以利用一個反轉(zhuǎn)函數(shù)
public int flip(int n) {
return n ^ 1;
}
這個函數(shù)的作用就是，當(dāng)n == 1時，返回 0，當(dāng)n == 0時，返回 1，我們將判斷符號的結(jié)果flip一次，如下代碼
public static int sign(int n) {
return flip((n >> 31) & 1);
}
這個方法的作用就是
當(dāng)符號位是 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
主函數(shù)直接做如下調(diào)用
public static int getMax1(int a, int b) {
int c = a - b;
//當(dāng)符號位是 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 兩個數(shù)的符號，
會有如下幾種情況：
情況1：符號不同，則直接返回符號為正的那個數(shù)。
情況2：如果符號相同，則這種情況下,a - b的值絕對不會溢出，那么就看 c 的符號（c為正返回a，c為負(fù)返回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符號不一樣。
只有當(dāng)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的完整代碼和測試代碼如下：
// 不要用任何比較判斷，返回兩個數(shù)中較大的數(shù)
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));
}
}
到此這篇關(guān)于Java利用位運算實現(xiàn)比較兩個數(shù)的大小的文章就介紹到這了,更多相關(guān)Java位運算內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
java并發(fā)編程synchronized底層實現(xiàn)原理
這篇文章主要介紹了java并發(fā)編程synchronized底層實現(xiàn)原理2022-02-02
這篇文章主要介紹了JAVA版排序算法之快速排序,結(jié)合實例形式分析了基于java版的遍歷、遞歸實現(xiàn)快速排序功能的具體步驟與操作技巧,需要的朋友可以參考下2017-01-01
這篇文章主要給大家分享介紹了一次詭異的full gc查找問題全部過程，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧啊2018-11-11
這篇文章主要介紹了SpringBoot AOP處理請求日志打印功能代碼實例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-03-03
這篇文章主要介紹了Java實現(xiàn)SSL Socket長連接方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01
這篇文章給大家介紹了本地方法映射Java層的數(shù)據(jù)類型，包括基礎(chǔ)類型映射，引用類型映射等等，對java層數(shù)據(jù)類型映射相關(guān)知識，感興趣的朋友跟隨腳本之家小編一起看看吧2018-03-03
基于 IntelliJ IDEA 模擬 Servlet 網(wǎng)絡(luò)請求示例
這篇文章主要介紹了基于 IntelliJ IDEA 模擬 Servlet 網(wǎng)絡(luò)請求示例，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-04-04
這篇文章主要介紹了Spring中的依賴注入DI源碼詳細(xì)解析,Spring的依賴注入(Dependency Injection,DI)是Spring框架核心的一部分,它是實現(xiàn)控制反轉(zhuǎn)(Inversion of Control,IoC)的一種方式,需要的朋友可以參考下2023-11-11
Java應(yīng)用程序通過直接方式從操作系統(tǒng)中申請的內(nèi)存,叫堆外內(nèi)存,這篇文章主要給大家介紹了關(guān)于jvm堆外內(nèi)存排查的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-12-12
Java通過反射機制動態(tài)設(shè)置對象屬性值的方法
下面小編就為大家?guī)硪黄狫ava通過反射機制動態(tài)設(shè)置對象屬性值的方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-07-07