阅读 1544

遍地都是的位运算,关键时刻竟然有妙用!

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

有 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 类中的一个内部类,关键代码如下:

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

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

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;
	}
}
复制代码

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

manager.addStatus(StatusManager.STATUS_TIME_ASY | STATUS_ADD_FIXED_PSW )
复制代码

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

manager.hasStatus(StatusManager.STATUS_TIME_ASY | STATUS_OPEN_DOOR)
复制代码

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

关注下面的标签,发现更多相似文章
评论