Andorid 算法之美 : 位運(yùn)算

給定一個(gè)整數(shù)蚯瞧，請(qǐng)寫一個(gè)函數(shù)判斷該整數(shù)的奇偶性

該題目作為后續(xù)題目的鋪墊勇凭，看上去還是沒有任何難度的啃勉。主要考察了面試能否想到用二進(jìn)制的位運(yùn)算方法去解決煌茴。我們先回顧下 & | ~等運(yùn)算符随闺。

與運(yùn)算符 &

兩位同時(shí)為“1”，結(jié)果才為“1”蔓腐，否則為“0”矩乐。

0&0=0; 0&1=0; 1&0=0; 1&1=1;

或運(yùn)算符 |

只要有一位為1，其值為1，否則為0散罕。
0|0=0分歇； 0|1=1； 1|0=1欧漱； 1|1=1职抡；

非運(yùn)算符～

如果位為0，結(jié)果是1误甚。如果位為1缚甩，結(jié)果是0

~0=1； ~1=0窑邦；

^ 異或運(yùn)算符

兩個(gè)操作數(shù)進(jìn)行異或時(shí)擅威，對(duì)于同一位上，如果數(shù)值相同則為 0冈钦，數(shù)值不同則為 1郊丛。

1 ^ 0 = 1,
1 ^ 1 = 0,
0 ^ 0 = 0;

3 ^ 5 = 6

值得注意的是 3 ^ 5 = 6,而 6 ^ 5 = 3

針對(duì)這個(gè)特性，我們可以將異或運(yùn)算作為一個(gè)簡(jiǎn)單的數(shù)據(jù)加密的形式瞧筛。比如厉熟，將一個(gè)mp4文件所有數(shù)值與一個(gè)種子數(shù)值進(jìn)行異或得到加密后的數(shù)據(jù)，解密的時(shí)候再將數(shù)據(jù)與種子數(shù)值進(jìn)行異或一次就可以了较幌。

**所以說異或運(yùn)算可以作為簡(jiǎn)單的加解密運(yùn)算

>> 右移運(yùn)算符

a >> b 將數(shù)值 a 的二進(jìn)制數(shù)值從整體向右方向移動(dòng) b 位揍瑟，正數(shù)符號(hào)位不變，高位空出來的位補(bǔ)數(shù)值 0绅络。

5 >> 1 ===>  0000 0000 0000 0101 >> 1  = 0000 0000 0000 0010 = 2
7 >> 2 ===>  0000 0000 0000 0111 >> 2  = 0000 0000 0000 0001 = 1
9 >> 3 ===>  0000 0000 0000 1001 >> 3  = 0000 0000 0000 0001 = 1
11 >> 2 ===> 0000 0000 0000 1011 >> 2 = 0000 0000 0000 0010 = 2
大家發(fā)現(xiàn)什么規(guī)律沒有？a >> b = a / ( 2 ^ b ) ,所以 5 >> 1= 5 / 2 = 2,11 >> 2 = 11 / 4 = 2嘁字。

<< 左移運(yùn)算符

a << b 將數(shù)值 a 的二進(jìn)制數(shù)值從整體向左方向移動(dòng) b 位恩急，正數(shù)符號(hào)位不變，低位空出來的位補(bǔ)數(shù)值 0纪蜒。

5 << 1 ===>  0000 0000 0000 0101 << 1  = 0000 0000 0000 1010 = 10
7 << 2 ===>  0000 0000 0000 0111 << 2  = 0000 0000 0001 1100 = 28
9 << 3 ===>  0000 0000 0000 1001 << 3  = 0000 0000 0100 1000 = 72
11 << 2 ===> 0000 0000 0000 1011 << 2 =  0000 0000 0010 1100 = 44
很明顯就可以看出 a << b = a * (2 ^ b)

綜合上面兩個(gè)可以看到衷恭，如果某個(gè)數(shù)值右移 n 位，就相當(dāng)于拿這個(gè)數(shù)值去除以 2 的 n 次冪纯续。如果某個(gè)數(shù)值左移 n 位随珠，就相當(dāng)于這個(gè)數(shù)值乘以 2 ^ n。

場(chǎng)景一（或運(yùn)算符的使用）

android:layout_gravity="bottom|right"

這里的 bottom 和 right 在位上肯定是錯(cuò)開的猬错，這樣做位運(yùn)算窗看，才能同時(shí)保存該控件 “居右”和“底部” 的屬性。什么叫位上錯(cuò)開倦炒，且看下面代碼

// 0x001 = 0000 0001
int right = 0x001;
// 0x002 = 0000 0010
int bottom = 0x002;
// 結(jié)果 = 0000 0011 = 3
System.out.println("right | bottom = " + (right | bottom));

通過上面的代碼显沈，或許你已經(jīng)恍然大悟，其實(shí)位錯(cuò)開是為了或運(yùn)算時(shí)，進(jìn)行值的保留拉讯。 讓兩個(gè)或多個(gè)狀態(tài)保存在一個(gè)屬性中涤浇，目的是為了節(jié)省空間。

與運(yùn)算符的使用

我們用或運(yùn)算組裝成一個(gè)值魔慷，要怎么使用它呢只锭？安卓源碼中怎么知道我們?cè)O(shè)置了 right 這個(gè)居右的狀態(tài)呢？這個(gè)便需要使用 “與” 運(yùn)算符來取值院尔。具體操作如下代碼：

int right = 0x001;
int bottom = 0x002;
int top = 0x008;
int state = right | bottom;
System.out.println("是否存在 right = " + ((state & right) == right));
System.out.println("是否存在 top = " + ((state & top) == top));

//運(yùn)行結(jié)果 
是否存在 right = true
是否存在 top = false

非運(yùn)算符的使用

如果我想剔除當(dāng)前已經(jīng)包含的一個(gè)值蜻展，需要怎么辦？這時(shí)候就是“非”和“與”運(yùn)算符聯(lián)合使用的時(shí)候了召边，且看下面代碼

int right = 0x001;
int bottom = 0x002;
int top = 0x008;
int state = right | bottom;
System.out.println("剔除 right 狀態(tài)前 " + state);
state &= ~right;
System.out.println("剔除 right 狀態(tài)后 " + state);
state &= ~top;
System.out.println("剔除不存在的 top 狀態(tài) " + state);

運(yùn)行結(jié)果
剔除 right 狀態(tài)前 3
剔除 right 狀態(tài)后 2
剔除不存在的 top 狀態(tài) 2

JVM 的基礎(chǔ)數(shù)據(jù)字節(jié)長(zhǎng)度是一致的

int：4 個(gè)字節(jié)铺呵。
short：2 個(gè)字節(jié)。
long：8 個(gè)字節(jié)隧熙。
byte：1 個(gè)字節(jié)片挂。
float：4 個(gè)字節(jié)。
double：8 個(gè)字節(jié)贞盯。
char：2 個(gè)字節(jié)音念。
boolean：boolean屬于布爾類型，在存儲(chǔ)的時(shí)候不使用字節(jié)躏敢，僅僅使用 1 位來存儲(chǔ)闷愤，范圍僅僅為0和1，其字面量為true和false件余。

接下來我們看看原碼反碼補(bǔ)碼讥脐。我們知道 int 型 4 個(gè)字節(jié)。每個(gè)字節(jié) 8 位啼器。它的最高位是符號(hào)位旬渠。

最高位0表示正數(shù)。
最高位1表示負(fù)數(shù)

原碼將一個(gè)數(shù)字轉(zhuǎn)換成二進(jìn)制就是這個(gè)數(shù)值的原碼端壳。

int a = 5; //原碼  0000 0000 0000 0101
int b = -3;  //原碼  1000 0000 0000 0011

反碼

分兩種情況：正數(shù)和負(fù)數(shù)

正數(shù)的反碼就是原碼告丢。
負(fù)數(shù)的反碼是在原碼的基礎(chǔ)上，符號(hào)位不變损谦，其它位都取反岖免。

5 的原碼：0000 0000 0000 0101
5 的反碼：0000 0000 0000 0101

-3 的原碼：1000 0000 0000 0011
-3 的反碼：1111 1111 1111 1100

補(bǔ)碼

正數(shù) 正數(shù)的補(bǔ)碼就是原碼。
負(fù)數(shù) 負(fù)數(shù)的補(bǔ)碼在反碼的基礎(chǔ)上加1

5 的補(bǔ)碼：  0000 0000 0000 0101

-3 的原碼：1000 0000 0000 0011
-3 的反碼：1111 1111 1111 1100
-3 的補(bǔ)碼: 1111 1111 1111 1101

計(jì)算機(jī)在進(jìn)行數(shù)值運(yùn)算的時(shí)候照捡，是通過補(bǔ)碼表示每個(gè)數(shù)值的颅湘。

5 - 3 = 5 + ( -3 )
相當(dāng)于 0000 0000 0000 0101
 +    1111 1111 1111 1101
    =  0000 0000 0000 0010

整數(shù)可以分為正數(shù)，負(fù)數(shù)栗精，0栅炒。也可以分為奇數(shù)和偶數(shù)。偶數(shù)的定義是：如果一個(gè)數(shù)是2的整數(shù)倍數(shù)，那么這個(gè)數(shù)便是偶數(shù)赢赊。如果不使用位運(yùn)算的方法乙漓，我們完全可以使用下面的方式解決：

public boolean isOdd(int num){//odd 奇數(shù)
    return num % 2 != 0;
}

可是面試題不可能去簡(jiǎn)單就考察這么簡(jiǎn)單的解法，進(jìn)而我們想到了二進(jìn)制中如果一個(gè)數(shù)是偶數(shù)那么最后一個(gè)一定是 0 如果一個(gè)數(shù)是奇數(shù)那么最后一位一定是 1释移；而十進(jìn)制 1 在 8 位二進(jìn)制中表示為 0000 0001叭披，我們只需將一個(gè)數(shù)個(gè)與1相與得到的結(jié)果如果是 1 則表示該數(shù)為奇數(shù)，否知為偶數(shù)玩讳。所以這道題的最佳解法如下：

public boolean isOdd(int num){
    return num & 1 != 0;
}

#include <stdio.h>
#include <math.h>

//函數(shù)聲明
int isOdd(int num);

int  main()
{
    if( isOdd(0)>0)
    {
        printf("是奇數(shù)");
    }
    else
    {
        printf("是偶數(shù)");
    }
    return 0;
}

int  isOdd(int num)
{
    return (num & 1);
}

輸出結(jié)果是偶數(shù)

同樣給定一個(gè)整數(shù)涩蜘，請(qǐng)寫一個(gè)函數(shù)判斷該整數(shù)是不是2的整數(shù)次冪

這道題仍舊考察面試者對(duì)于一個(gè)數(shù)的二進(jìn)制的表示特點(diǎn)，一個(gè)整數(shù)如果是2的整數(shù)次冪熏纯，那么他用二進(jìn)制表示完肯定有唯一一位為1其余各位都為 0同诫，形如 0..0100...0。比如 8 是 2的3次冪樟澜，那么這個(gè)數(shù)表示為二進(jìn)制位 0000 1000 误窖。

除此之外我們還應(yīng)該想到，一個(gè)二進(jìn)制如果表示為 0..0100...0秩贰，那么它減去1得到的數(shù)二進(jìn)制表示肯定是 0..0011..1 的形式霹俺。那么這個(gè)數(shù)減一,與上自己得到結(jié)果肯定為0。

所以該題最佳解法為：

public boolean IsLog2(int num){
   return (num & (num - 1)) == 0;
}

int IsLog2(int num){
       return (num & (num -1)) == 0;
}

//測(cè)試
int  main()
{
   printf("是否是2的整數(shù)次冪 ：%d\n",IsLog2(1));
   printf("是否是2的整數(shù)次冪 ：%d\n",IsLog2(2));
   printf("是否是2的整數(shù)次冪 ：%d\n",IsLog2(3));
    return 0;
}

結(jié)果
是否是2的整數(shù)次冪： 1 //是 true
是否是2的整數(shù)次冪： 1 //是 true
是否是2的整數(shù)次冪： 0 //不是 false

給定一個(gè)整數(shù)毒费，請(qǐng)寫一個(gè)函數(shù)判斷該整數(shù)的二進(jìn)制表示中1的個(gè)數(shù)

判斷一個(gè)整數(shù)二進(jìn)制表示中1的個(gè)數(shù)丙唧，假設(shè)這個(gè)整數(shù)用32位表示，可正可負(fù)可0觅玻，那么這個(gè)數(shù)中有多少個(gè)1想际，就需要考慮到符號(hào)位的問題了。

相信讀者應(yīng)該都能想到最近基本的解法即通過右移運(yùn)算后與 1 相與得到的結(jié)果來計(jì)算結(jié)果溪厘，如果采用這種解法胡本，那么這個(gè)題的陷阱就在于存在負(fù)數(shù)的情況，如果負(fù)數(shù)的話標(biāo)志位應(yīng)該算一個(gè)1桩匪。所以右移的時(shí)候一定要采用無符號(hào)右移才能得到正確的解法打瘪。

所以此題一種解法如下：

public int count1(int n) {
   int res = 0;
   while (n != 0) {
       res += n & 1;
       n >>>= 1;
   }
   return res;
}

#include <stdio.h>

int  bit(unsigned int n)
{
    int count=0;
    while (n != 0) {
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int main()
{
    printf("1在二進(jìn)制中1的個(gè)數(shù)：%d\n",bit(1));
    printf("-1在二進(jìn)制中1的個(gè)數(shù)：%d\n",bit(-1));
     printf("4在二進(jìn)制中1的個(gè)數(shù)：%d\n",bit(4));
    return 0;
}

結(jié)果

1在二進(jìn)制中1的個(gè)數(shù)：1
-1在二進(jìn)制中1的個(gè)數(shù)：32
4在二進(jìn)制中1的個(gè)數(shù)：1

在Android源碼里面對(duì)于它的應(yīng)用還是算是較多的友鼻，一般是用于存儲(chǔ)多種變量傻昙，或者說是flag的存儲(chǔ)和判斷，在這里也就舉幾個(gè)例子彩扔。

MeasureSpec

興許最早在Android源碼里面接觸位運(yùn)算的話就是在自定義View部分的時(shí)候妆档，當(dāng)書里面提及MeasureSpec這個(gè)變量的時(shí)候采用如下描述：

MeasureSpec代表一個(gè)32位int值，高2位代表SpecMode虫碉，低30位代表SpecSize贾惦，SpecMode是指測(cè)量模式，而SpecSize是指在某種測(cè)量模式下的規(guī)格大小。

這里面就是典型的位運(yùn)算的運(yùn)用须板，不論是這個(gè)變量需要分別拆分獲得 $\color{#34a853}{SpecMode}$ 和 $\color{#34a853}{SpecSize}$ 碰镜，還是其他的一些相關(guān)的操作，都需要位運(yùn)算习瑰。

首先是 $\color{#34a853}{SpecMode}$ 绪颖，在描述之中是高2位的部分，那么在處理之中一定會(huì)運(yùn)用到左移或者右移來完成需求甜奄。

在這個(gè)類里面柠横，一開始就聲明了兩個(gè)基本變量以及不同測(cè)量模式的值，已經(jīng)用到了位運(yùn)算中的左移

private static final int MODE_SHIFT = 30;
// 聲明位移量
private static final int MODE_MASK  = 0x3 << MODE_SHIFT;
// 后期截取SpecMode或SpecSize時(shí)使用的變量
// 3對(duì)應(yīng)的二進(jìn)制是11课兄，左移30位后牍氛，int值的前2位就都是1，后30位為0

public static final int UNSPECIFIED = 0 << MODE_SHIFT;
public static final int EXACTLY     = 1 << MODE_SHIFT;
public static final int AT_MOST     = 2 << MODE_SHIFT;
// 三種測(cè)量模式對(duì)應(yīng)的值

先看看是如何通過位運(yùn)算來獲取SpecMode和SpecSize：

@MeasureSpecMode
// 等價(jià)于@IntDef(value={...})烟阐。一種枚舉類注釋
public static int getMode(int measureSpec) {
    return (measureSpec & MODE_MASK);
    // 讓低30位的值變?yōu)?搬俊，只保留高2位的值
}

public static int getSize(int measureSpec) {
    return (measureSpec & ~MODE_MASK);
    // 非運(yùn)算直接讓MASK值變成int值高2位為0，低30位為1
    // 進(jìn)行與運(yùn)算曲饱，直接將高2位的值變?yōu)?
}

這里就是典型的通過位運(yùn)算來截取對(duì)應(yīng)值悠抹，利用的是x & 1 = x, x & 0 = 0，其中x代表0與1兩種值扩淀。這種方式讓一個(gè)變量能夠存儲(chǔ)多個(gè)內(nèi)容方式實(shí)現(xiàn)楔敌，甚至也可以使用這樣的方式將合成的值作為特定的key來做匹配或者相似需求。

接下來是如何獲得 $\color{#34a853}{MeasureSpec}$ 值：

public static int makeMeasureSpec(
    @IntRange(from = 0, to = (1 << MeasureSpec.MODE_SHIFT) - 1) int size,
    // 要求傳入的size值在指定范圍內(nèi)
    @MeasureSpecMode int mode) {
            if (sUseBrokenMakeMeasureSpec) {// 是否用原來的方法對(duì)MeasureSpec進(jìn)行構(gòu)建
                return size + mode;
            } else {
                return (size & ~MODE_MASK) | (mode & MODE_MASK);
            }
        }

在API17及其以下的時(shí)候驻谆，是按照size + mode的方式進(jìn)行構(gòu)建卵凑，一個(gè)是只有int前2位有值，一個(gè)是只有int后30位有值胜臊，這么思考處理也情有可原勺卢。但假若兩個(gè)值有溢出情況就會(huì)嚴(yán)重影響MeasureSpec的結(jié)果。故Google官方在API17之后就對(duì)該方法進(jìn)行了修正象对，也是采用的位運(yùn)算的形式：
(size & ~MODE_MASK) | (mode & MODE_MASK)
相當(dāng)于就是分別獲得了SpecSize和SpecMode后通過或運(yùn)算獲得結(jié)果黑忱。

最后編輯于：2020.09.09 19:38:28

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市勒魔，隨后出現(xiàn)的幾起案子甫煞，更是在濱河造成了極大的恐慌，老刑警劉巖冠绢，帶你破解...
沈念sama閱讀 211,817評(píng)論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件抚吠，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡弟胀，警方通過查閱死者的電腦和手機(jī)楷力，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,329評(píng)論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門喊式，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人萧朝，你說我怎么就攤上這事岔留。” “怎么了检柬？”我有些...
開封第一講書人閱讀 157,354評(píng)論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵贸诚，是天一觀的道長(zhǎng)。經(jīng)常有香客問我厕吉，道長(zhǎng)酱固，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 56,498評(píng)論 1贊 284
?港島之戀（遺憾婚禮）
正文為了忘掉前任头朱，我火速辦了婚禮运悲，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘项钮。我一直安慰自己班眯，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 65,600評(píng)論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布烁巫。她就那樣靜靜地躺著署隘，像睡著了一般。火紅的嫁衣襯著肌膚如雪亚隙。梳的紋絲不亂的頭發(fā)上磁餐，一...
開封第一講書人閱讀 49,829評(píng)論 1贊 290
城市分裂傳說
那天，我揣著相機(jī)與錄音阿弃，去河邊找鬼诊霹。笑死，一個(gè)胖子當(dāng)著我的面吹牛渣淳，可吹牛的內(nèi)容都是我干的脾还。我是一名探鬼主播，決...
沈念sama閱讀 38,979評(píng)論 3贊 408
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼入愧，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼鄙漏！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起棺蛛，我...
開封第一講書人閱讀 37,722評(píng)論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤怔蚌，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后鞠值，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體媚创，經(jīng)...
沈念sama閱讀 44,189評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡渗钉，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,519評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年彤恶，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了钞钙。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,654評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡声离，死狀恐怖芒炼，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情术徊，我是刑警寧澤本刽，帶...
沈念sama閱讀 34,329評(píng)論 4贊 330
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站赠涮，受9級(jí)特大地震影響子寓，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜笋除，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,940評(píng)論 3贊 313
男人毒藥：我在死后第九天來索命
文/蒙蒙一斜友、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧垃它，春花似錦鲜屏、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,762評(píng)論 0贊 21
一樁弒父案洛史，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至酱吝，卻和暖如春也殖，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背务热。一陣腳步聲響...
開封第一講書人閱讀 31,993評(píng)論 1贊 266
情欲美人皮
我被黑心中介騙來泰國打工毕源，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人陕习。一個(gè)月前我還...
沈念sama閱讀 46,382評(píng)論 2贊 360
代替公主和親
正文我出身青樓霎褐，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國和親该镣。傳聞我的和親對(duì)象是個(gè)殘疾皇子冻璃，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,543評(píng)論 2贊 349