谈谈位运算

位运算,不论是计算机底层处理编码的时候,还是我们看源码的时候都一定有概率能够看见它。某种程度来说也算是比较熟悉了吧。
个人认为,位运算某种程度上是契合了数字电路之中的逻辑运算,通过一定的逻辑关系将二进制的数据进行快速处理。
虽然本质来说,位运算就是直接操作内存中的整数进行逻辑运算。这个从代码到硬件的过程大概从代码到内存到不同的芯片之间,不同的逻辑门之间进行运算从而得到结果,再反馈给计算机本身,不过这些东西并不是重点,点到即止就是。

位运算之中的运算步骤都需要将数字转换为二进制之后才进行操作,毕竟是针对计算机内部本身的一个运算,使用二进制来进行处理也情有可原。所以说这跟逻辑电路也有那么些联系。既然是要转换为二进制来计算,那么肯定有两个数字转换为二进制之后位数不相同的情况(指人为进行计算),在这里,通常的解决方式是在位数少的那个数前面补零。

运算

要使用位运算之前,肯定是要了解下面的这些运算符号以及作用的。

  • 与运算(and)
    &表示,当两个相同位对应的数都是1的时候,该位获得的结果才是1,否则为0
    例如说6 & 11,转换为二进制就是0110 & 1011,结果为0010

  • 或运算(or)
    |表示,当两个相同位对应的数只要有一个数1的时候,该位获得的结果为1,否则为0
    还是用6和11这两个数做例子,就是0110 | 1011 = 1111

  • 非运算(not)
    ~表示,这个运算只针对一个数字,将数字全部取反(原来是0结果就是1,原来是1结果就是0)
    例如说:~110 = 001

  • 异或运算(xor)
    ^表示,当两个相同位对应的数字不同的时候为1,否则为0
    例如说:0110 ^ 1011 = 1101

  • 左移(shl)
    <<表示,a << b表示a左移b位,由于依偎在末位多出来的未知数字补零。
    在这里面可以等价为a * 2^b这个运算(针对十进制)。

  • 右移(shr)
    >>表示,a >> b表示将a右移b位,原本的末位进行右移后会被舍弃,若有需求会在高位进行补零。
    同样的,右移在十进制里面也可以近似为a / (2^b)的形式,不过要对结果取整,也不一定准确,只能够说意思大概如此。

针对位运算的左移右移,民间一直有一种说法,就是若对数字做对2以及二的倍数的乘法或者除法,使用位运算会比直接使用乘号或者除号的处理速度来的快。对此他们的解释一直都是以位运算是直接对内存进行操作导致运算效率来解释的,说乘号或者除号都是对位运算的一种包裹,当然我一直也是这么认为的,不过总觉得这种东西很微妙。未必这真的在一定程度上影响整个程序的运行效率?

还是废话不多说,直接代码验证。(这里指Java)

想法其实很简单粗暴,也就不贴代码上来了,思路就是对相同的一个数字进行相同次数(这个数足够大)的右移或者左移,记录时间差值,另外一边就是做等价的乘除法运算,记录时间差值并比较。

结果如下:(运算次数的话是999999999)

1
2
3
4
a/2,8281
a>>1,682
a*2,354
a<<1,345

就结果来说,针对乘法和左移,两者的效率相近(运行速度差异不大)
但是就针对除法和右移来说,显然右移效率远高于除法,某种程度来说是相当微妙了。
不过并没有去了解产生这种差异的根本原因。顺便一提,假如说这个次数不大的话整体的移位和乘除法的效率是基本相似的。所以说,非必要情况还是别用位运算了,影响代码阅读体验。

在某些工作情境下,位运算是妙用,有些情况下就是影响阅读了。所以使用它的时候也要考虑情境(如果是效率高于一切的选手这句话当我没说…)

写这篇博客的初衷自然不是来探究左右移的效率的,更想谈谈的是这个东西在Android里面的运用。在看书的时候发现很多部分的源码都有位运算的成分在里面,假如说一知半解的话观看体验极差就是了,所以说写一写具体应用。

Android中的应用

在Android源码里面对于它的应用还是算是较多的,一般是用于存储多种变量,或者说是flag的存储和判断,在这里也就举几个例子。

MeasureSpec

兴许最早在Android源码里面接触位运算的话就是在自定义View部分的时候,当书里面提及MeasureSpec这个变量的时候采用如下描述:

MeasureSpec代表一个32位int值,高2位代表SpecMode,低30位代表SpecSizeSpecMode是指测量模式,而SpecSize是指在某种测量模式下的规格大小。(引用自《Android开发艺术探索》)

这里面就是典型的位运算的运用,不论是这个变量需要分别拆分获得SpecModeSpecSize,还是其他的一些相关的操作,都需要位运算。

首先是SpecMode,在描述之中是高2位的部分,那么在处理之中一定会运用到左移或者右移来完成需求。

Talk is cheap, show me the code. :)

在这个类里面,一开始就声明了两个基本变量以及不同测量模式的值,已经用到了位运算中的左移

1
2
3
4
5
6
7
8
9
10
private static final int MODE_SHIFT = 30;
// 声明位移量
private static final int MODE_MASK = 0x3 << MODE_SHIFT;
// 后期截取SpecMode或SpecSize时使用的变量
// 3对应的二进制是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;
// 三种测量模式对应的值

先看看是如何通过位运算来获取SpecModeSpecSize

1
2
3
4
5
6
7
8
9
10
11
12
@MeasureSpecMode
// 等价于@IntDef(value={...})。一种枚举类注释
public static int getMode(int measureSpec) {
return (measureSpec & MODE_MASK);
// 让低30位的值变为0,只保留高2位的值
}

public static int getSize(int measureSpec) {
return (measureSpec & ~MODE_MASK);
// 非运算直接让MASK值变成int值高2位为0,低30位为1
// 进行与运算,直接将高2位的值变为0
}

这里就是典型的通过位运算来截取对应值,利用的是x & 1 = x, x & 0 = 0,其中x代表0与1两种值。
这种方式让一个变量能够存储多个内容方式实现,甚至也可以使用这样的方式将合成的值作为特定的key来做匹配或者相似需求。

接下来是如何获得MeasureSpec值:

1
2
3
4
5
6
7
8
9
10
public static int makeMeasureSpec(
@IntRange(from = 0, to = (1 << MeasureSpec.MODE_SHIFT) - 1) int size,
// 要求传入的size值在指定范围内
@MeasureSpecMode int mode) {
if (sUseBrokenMakeMeasureSpec) {// 是否用原来的方法对MeasureSpec进行构建
return size + mode;
} else {
return (size & ~MODE_MASK) | (mode & MODE_MASK);
}
}

在API17及其以下的时候,是按照size + mode的方式进行构建,一个是只有int前2位有值,一个是只有int后30位有值,这么思考处理也情有可原。但假若两个值有溢出情况就会严重影响MeasureSpec的结果。故Google官方在API17之后就对该方法进行了修正,也是采用的位运算的形式:
(size & ~MODE_MASK) | (mode & MODE_MASK)
相当于就是分别获得了SpecSizeSpecMode后通过或运算获得结果。

有关Flag存储和运算

上文提到过可以通过一些操作来实现一个变量存储多个内容,而在Android源码之中在很多也确实做到了,下面就简单举个例子。

因为源码中涉及这种运算的太多了,就不具体拿源码中的某个内容举例子了,想深究的可以去看看源码…大概Flag关键字就能找到挺多相关的内容。

使用的时候需要注意,对应的标志位需要设计好,假如说有内容交叉的话就会非常影响结果。Google官方工程师为了保证这一点也是费尽心思

在这之前,得先知道位运算的运算优先级:
~><</>>>&>^>|>&=/^=/|=

  • A | B
    添加标志B,可以添加多个(只要不冲突)
    例如:mViewFlags = SOUND_EFFECTS_ENABLED | HAPTIC_FEEDBACK_ENABLED | FOCUSABLE_AUTO;

  • A & B
    判断A中是否有标志B
    原理就是与运算之中的1 & 1 = 1, 0 & 1 = 0,以此来判断flag对应位是否存在该flag
    (mViewFlags & FOCUSABLE_AUTO) != 0这个判断语句为例:
    若为真,则与的结果不等于0,表示flag之中有该标志

  • A & ~B
    去除标志B
    上者的逆运算
    例如:mViewFlags = (mViewFlags & ~FOCUSABLE) | newFocus用于去除原有的标志位并附上新的标志位(相当于更新)

  • A ^ B
    取出A与B不同的部分,一般用于判断A是否发生改变

    1
    2
    3
    4
    int changed = mViewFlags ^ old;
    if (changed == 0) {
    return;
    }

(mViewFlags & ENABLED_MASK) == ENABLED类似于这种类型的原理就等同于在MeasureSpec中获得SpecModeSpecSize,采取对应位直接截断的方式拿到对应值,然后跟指定flag进行比较。

总结

虽然说位运算常用于算法里面,不过在开发过程之中的某些需求之下还是可以巧用位运算得到高效率。但是不要滥用,毕竟影响观感。