Java利用位運(yùn)算實(shí)現(xiàn)比較兩個(gè)數(shù)的大小
題目要求
如何不要用任何比較判斷符(>
,==
,<
),返回兩個(gè)數(shù)( 32 位整數(shù))中較大的數(shù)。
主要思路
方法1(不考慮溢出)
要比較 a 和 b 的大小,因?yàn)椴荒苡帽容^符號(hào),我們可以通過(guò) a - b 的符號(hào)位來(lái)判斷,如果 a - b 的符號(hào)位是 1,說(shuō)明 a - b < 0,則 a 小,否則 a 大或者 a 和 b 相等。
如何判斷一個(gè)數(shù)的符號(hào)位是 0 還是 1 ?
由于是 32 位整數(shù),所以如果將一個(gè)數(shù)右移 31 位,然后和 1 相與(&
),如果得到 1,則這個(gè)數(shù)是負(fù)數(shù),如果得到 0,則這個(gè)數(shù)是正數(shù)。
舉個(gè)具體例子,如果要求 a 和 b 誰(shuí)大,我們可以先通過(guò)
((a - b) >> 31) & 1
得到一個(gè)值,如果這個(gè)值是 1 ,說(shuō)明 a 小,否則 a 大或者 a 和 b 相等。
由于不能出現(xiàn)比較符號(hào),所以無(wú)法使用如下代碼
return ((a - b) >> 31) & 1 == 1?b:a;
也無(wú)法使用如下代碼
if (((a - b) >> 31) & 1 == 1){ return b; } return a;
但是我們可以巧妙利用((a - b) >> 31) & 1
結(jié)果去構(gòu)造一個(gè)公式,這個(gè)公式可以在((a - b) >> 31) & 1 == 1
情況下得到 b, 在((a - b) >> 31) & 1 == 0
情況下得到 a。
我們可以利用一個(gè)反轉(zhuǎn)函數(shù)
public int flip(int n) { return n ^ 1; }
這個(gè)函數(shù)的作用就是,當(dāng)n == 1
時(shí),返回 0,當(dāng)n == 0
時(shí),返回 1,我們將判斷符號(hào)的結(jié)果flip
一次,如下代碼
public static int sign(int n) { return flip((n >> 31) & 1); }
這個(gè)方法的作用就是
當(dāng)符號(hào)位是 1 的時(shí)候,返回 0,符號(hào)位是 0 的時(shí)候,返回 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)符號(hào)位是 1 的時(shí)候,scA = 0,符號(hào)位是 0 的時(shí)候,scA = 1。 int scA = sign(c); // scA = 1 時(shí),scB = 0,scA = 0時(shí),scB = 1 int scB = flip(scA); // 如果 scA = 0,說(shuō)明 b 大,直接返回b // 如果 scA = 1,說(shuō)明 a 大,直接返回a return a * scA + b * scB; }
這個(gè)方法沒(méi)有考慮溢出的情況,比如
a = 2147483647; b = -2147480000;
a - b
直接就溢出了,后面的算法就都不適用了。
方法2(考慮溢出情況)
那我們可以先比較 a 與 b 兩個(gè)數(shù)的符號(hào),
會(huì)有如下幾種情況:
情況1:符號(hào)不同,則直接返回符號(hào)為正的那個(gè)數(shù)。
情況2:如果符號(hào)相同,則這種情況下,a - b
的值絕對(duì)不會(huì)溢出,那么就看 c 的符號(hào)(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 的符號(hào)是否一樣,如果 difSab == 1
,則 a 和 b 符號(hào)一樣,如果difSab == 0
,則a 和 b符號(hào)不一樣。
只有當(dāng)difSab == 0
的時(shí)候,要考慮 c 的符號(hào)。因?yàn)?code>difSab == 0,所以int returnA = 0 * sa + 1 * sc;
,即int returnA = sc
,如果 sc 為 1,說(shuō)明 c 的符號(hào)是 0,則a - b > 0
,返回 a 即可,否則返回 b。
方法1和方法2的完整代碼和測(cè)試代碼如下:
// 不要用任何比較判斷,返回兩個(gè)數(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利用位運(yùn)算實(shí)現(xiàn)比較兩個(gè)數(shù)的大小的文章就介紹到這了,更多相關(guān)Java位運(yùn)算內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
java并發(fā)編程synchronized底層實(shí)現(xiàn)原理
這篇文章主要介紹了java并發(fā)編程synchronized底層實(shí)現(xiàn)原理2022-02-02SpringBoot AOP處理請(qǐng)求日志打印功能代碼實(shí)例
這篇文章主要介紹了SpringBoot AOP處理請(qǐng)求日志打印功能代碼實(shí)例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03Java實(shí)現(xiàn)SSL Socket長(zhǎng)連接方式
這篇文章主要介紹了Java實(shí)現(xiàn)SSL Socket長(zhǎng)連接方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-01-01解析本地方法映射Java層的數(shù)據(jù)類(lèi)型
這篇文章給大家介紹了本地方法映射Java層的數(shù)據(jù)類(lèi)型,包括基礎(chǔ)類(lèi)型映射,引用類(lèi)型映射等等,對(duì)java層數(shù)據(jù)類(lèi)型映射相關(guān)知識(shí),感興趣的朋友跟隨腳本之家小編一起看看吧2018-03-03基于 IntelliJ IDEA 模擬 Servlet 網(wǎng)絡(luò)請(qǐng)求示例
這篇文章主要介紹了基于 IntelliJ IDEA 模擬 Servlet 網(wǎng)絡(luò)請(qǐng)求示例,小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-04-04Java通過(guò)反射機(jī)制動(dòng)態(tài)設(shè)置對(duì)象屬性值的方法
下面小編就為大家?guī)?lái)一篇Java通過(guò)反射機(jī)制動(dòng)態(tài)設(shè)置對(duì)象屬性值的方法。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-07-07