前言
本文主要介紹如何把一個(gè)int型二進(jìn)制數(shù)的最右側(cè)的1提取出來裙品，也就是只保留該int型數(shù)對應(yīng)的二進(jìn)制最右側(cè)的1，其他的都變?yōu)?code>0俗或，并返回對應(yīng)的10進(jìn)制數(shù)字市怎。
現(xiàn)有個(gè)數(shù)num=112256700，這個(gè)num對應(yīng)的二進(jìn)制為00000110101100001110011010111100辛慰，要求把這個(gè)數(shù)的二進(jìn)制最右側(cè)的1保留区匠，其他的位置全部變?yōu)?，也就是變?yōu)?code>00000000000000000000000000000100，變更后的二進(jìn)制數(shù)對應(yīng)的十進(jìn)制為4驰弄。
思路分析
方法一
此方法為比較傳統(tǒng)的方法麻汰，也就是先把num這個(gè)是轉(zhuǎn)為二進(jìn)制形式，放到一個(gè)數(shù)組中戚篙，然后遍歷數(shù)組五鲫，找到最右側(cè)的1，記錄1的位置岔擂，然后轉(zhuǎn)成10進(jìn)制形式位喂。
此方法理解起來簡單、實(shí)現(xiàn)也簡單乱灵，但是沒有什么技術(shù)可言塑崖，也不夠優(yōu)雅，不推薦痛倚。
方法一代碼實(shí)現(xiàn)
public class Code16_FindRightOne {
public static int getRightOne(int num) {
int[] arr = new int[32];
for (int i = 31; i >= 0; i--) {
arr[i] = (num & (1 << i)) == 0 ? 0 : 1;
}
int res = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
res = i;
break;
}
}
return (int) (Math.pow(2, res));
}
public static void main(String[] args) {
int rightOne = getRightOne(112256700);
System.out.println(rightOne);
}
}
復(fù)制代碼
看下運(yùn)行結(jié)果為4规婆。
方法二
此方法，利用了二進(jìn)制的特性蝉稳，可以非常簡單的實(shí)現(xiàn)這個(gè)功能聋呢，先看下解決思路。
要保留左右側(cè)的1颠区，把其他位置都變?yōu)?，首先想到的是位運(yùn)算通铲，再來看下位運(yùn)算的幾個(gè)特性：
與&：兩邊都為1結(jié)果才為1毕莱，否則為0。
或|：兩邊有一個(gè)為1結(jié)果就為1颅夺，都為0時(shí)才為0朋截。
異或^：相同為0，不同為1吧黄。
我們的目的是部服，把最右側(cè)1左邊的數(shù)，全部變?yōu)?拗慨，按照位運(yùn)算來看廓八，相與操作最為可能，只要把1左邊的數(shù)取反再與原來的數(shù)相與就可以了赵抢。
如果把num取反剧蹂，左邊的數(shù)是解決了，那右邊的數(shù)呢烦却？右邊的數(shù)也取反了宠叼，怎么把他還原回來呢？
先看個(gè)例子其爵，比如一個(gè)二進(jìn)制為000101000100冒冬，這個(gè)二進(jìn)制取反后為111010111011伸蚯，現(xiàn)在就差怎么把011變?yōu)?code>100了，這么一看就簡單了简烤，把011加上1不就好了剂邮？111010111011 + 1 = 111010111100。讓這兩個(gè)數(shù)再進(jìn)行相與就能保留最右側(cè)的1了乐埠。
也就是抗斤，把原來的數(shù)num和num取反加1進(jìn)行相與即可。
還記得取反加1又可以怎么表示嗎丈咐？對了瑞眼，num取反加1又可以表示為負(fù)數(shù)即-num。
方法二代碼實(shí)現(xiàn)
來看下代碼吧棵逊。
public class Code17_FindRightOne {
public static void printBinary(int num) {
for (int i = 31; i >= 0; i--) {
System.out.print((num & (1 << i)) == 0 ? "0" : "1");
}
System.out.println();
}
public static void main(String[] args) {
printBinary(112256700);
printBinary(112256700 & -112256700);
System.out.println(112256700 & -112256700);
}
}
復(fù)制代碼
輸出結(jié)果：
00000110101100001110011010111100
00000000000000000000000000000100
4
復(fù)制代碼
可以看到運(yùn)行結(jié)果和方法一是一樣的伤疙，說明方法二的代碼功能實(shí)現(xiàn)也是正確的。
為了查看方便辆影，我把原來的數(shù)以及兩個(gè)數(shù)相與后的結(jié)果的二進(jìn)制形式也打印了出來徒像。從上面結(jié)果來看，是不是把最右側(cè)的1保留下來了呢蛙讥？
總結(jié)
從上面兩個(gè)方案來看锯蛀，方法二使用位運(yùn)算比方法一簡單的太多了，僅僅簡單的一行代碼就把功能給實(shí)現(xiàn)了次慢，而且在效率方面也遠(yuǎn)比方法一高的多旁涤。
把一個(gè)數(shù)的二進(jìn)制最右側(cè)的1提取出來，在很多算法題目中會(huì)經(jīng)常遇到迫像，這里只是簡單的介紹了下如何實(shí)現(xiàn)劈愚，后面會(huì)介紹更多使用此方法的案例。
當(dāng)然實(shí)現(xiàn)方法有很多種闻妓，如果你有更好的辦法菌羽，歡迎在評論區(qū)留言交流
