很多人都可能在面试的时候遇到过这样一道题目:

有 1000 个一模一样的瓶子,其中有 999 瓶是普通的水,其中有一瓶含有剧毒(稀释后仍然具有毒性),你只有 10 条小白鼠,它们在喝下毒药后会马上死去,怎样利用它们在最短的时间内判断出哪瓶是毒药?

我们都知道,在计算机语言当中,所有的数字最终都会转化为二进制进行计算,而二进制中每一个“位”能够表示两种状态,它们分别是数字 0 和 1。

回到刚才的题目,每条小白鼠的生和死的状态都可以表示二进制中的一个“位”, 10 条小白鼠一共就能表示 1024 种组合状态,因此这道题目一个解决思路就是,给这 1000 瓶水都按照二进制的格式标上记号(10 位二进制数就能标记全部),让这 10 条小白鼠分别对应这十位二进制中的一位,然后将这十位二进制数中当前位上是 1 的水混合在一起给对应此位的小白鼠喝,根据小白鼠的死亡情况就能定位哪瓶水有毒。

从 MeasureSpec 中理解位运算

在 Android 开发中,我们也时常见到位运算的身影。在进行自定义 View 的时候,都会用到 int makeMeasureSpec(int size, int mode) 方法去获取 View 的尺寸和测量模式,那么它是怎么把两个变量组装成一个的呢?简单地讲就是用一个 32 位二进制数字中的高两位来存储测量模式 MeasureMode,用低 30 位来存储尺寸 MeasureSize,MeasureSpec 是 android.view.View 类中的一个内部类,关键代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static class MeasureSpec {
private static final int MODE_SHIFT = 30;
// SpecMode 掩码,用于屏蔽高两位
// 11 000000 00000000 00000000 00000000
private static final int MODE_MASK = 0x3 << MODE_SHIFT;
// 00 000000 00000000 00000000 00000000
public static final int UNSPECIFIED = 0 << MODE_SHIFT;
// 01 000000 00000000 00000000 00000000
public static final int EXACTLY = 1 << MODE_SHIFT;
// 10 000000 00000000 00000000 00000000
public static final int AT_MOST = 2 << MODE_SHIFT;

// 获取 MeasureSpec
public static int makeMeasureSpec(int size, int mode) {
// API 17 之前,忽略此条件
if (sUseBrokenMakeMeasureSpec) {
return size + mode;
} else {
return (size & ~MODE_MASK) | (mode & MODE_MASK);
}
}

// 获取 SpecMode
public static int getMode(int measureSpec) {
return (measureSpec & MODE_MASK);
}

// 获取 SpecSize
public static int getSize(int measureSpec) {
return (measureSpec & ~MODE_MASK);
}
}

位运算的操作符有以下几种:

  1. 或运算符| : 0|0=0,0|1=1,1|1=1

  2. 与运算符& : 0&0=0,0&1=0,1&1=1

  3. 非运算符~ : ~0=1,~1=0

  4. 异或运算符^ : 相同为 0,不同为 1:0^0=0,1^0=1,0^1=1,1^1=0

  5. 右移运算符 >> 和左移运算符 << : 001<<2=100,110>>1=11

在 MeasureSpec 类中,getMode 方法是将参数 measureSpec 与 MODE_MASK 进行与运算,MODE_MASK 可以理解为 SpecMode 的掩码,运算的结果是保留measureSpec 的高两位,剩下的后 30 位置 0,得到的是 MeasureMode。

getSize 方法是先将 MODE_MASK 取反再跟 measureSpec 进行与运算,结果是高两位为 0 低 30 位不变的值,即 SpecSize。

makeMeasureSpec 方法中,size & ~MODE_MASK 的结果是 size 的 SpecSize,mode & MODE_MASK 的结果是 SpecMode,将他们进行或操作,得到的就是是两者的叠加值。

位运算在实际开发中的使用

类似的,在日常开发中,我们也可以用位运算来简化一些操作,假如服务端返回一个数字,可能存在几种状态叠加的情况(下图),如果按照传统的方法来处理将会很麻烦,这时候就需要利用位运算了。

status.png
status.png

我们可以新建一个 StatusManager 类用来处理这个复杂的状态:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class StatusManager {
// 正常
public static final int STATUS_NORMAL = 0 ; // 0000

//时间同步失败
public static final int STATUS_TIME_ASY = 1 ; // 0001

// 开门指令失败
public static final int STATUS_OPEN_DOOR = 1 << 1; // 0010

// 添加固定密码失败
public static final int STATUS_ADD_FIXED_PSW = 1 << 2; // 0100

// 删除固定密码失败
public static final int STATUS_DEL_FIXED_PSW = 1 << 3; // 1000

// 存储目前的权限状态
private int flag;

/**
* 重置状态
*/
public void setStatus(int status) {
flag = status;
}

/**
* 添加一种或者多种状态
*/
public void addStatus(int status) {
flag |= status;
}

/**
* 删除一种或者多种状态
*/
public void deleteStatus(int status) {
flag &= ~status;
}

/**
* 是否具有某些状态
*/
public boolean hasStatus(int status) {
return (flag & status) == status;
}

/**
* 是否不具有某些状态
*/
public boolean isHasnotStatus(int status) {
return (flag & status) == 0;
}

/**
* 是否仅仅具有某些状态
*/
public boolean isOnlyHas(int status) {
return flag == status;
}
}

添加状态时,可以这样写:

1
manager.addStatus(StatusManager.STATUS_TIME_ASY | STATUS_ADD_FIXED_PSW )

如果需要判断是否时间同步和开门指令同时失败,可以这样写:

1
manager.hasStatus(StatusManager.STATUS_TIME_ASY | STATUS_OPEN_DOOR)

这时候回去理解文章开头的面试题目是不是很容易了?