用 int 来储存 boolean 数组

2017-12-05  本文已影响0人  steamed_bun

此方法是看Zxing的源码的时候学到哒~ Zxing源码

效果:

      将 boolean 数组"压缩",然后再还原---用速度换内存

Zxing中介绍:

A simple, fast array of bits, represented compactly by an array of ints internally.
一个简单,快速的位数组,由内部的一系列int整数表示


原理解析:

1、int 有四个字节 ,每个字节有8个 bit,共32个 bit 位,都是由0、1组成;
2、boolean 数组每32个,压缩到一个 int 中;


代码解析:github 上的代码

简书上的代码
建议直接运行起来再往下看^ _ ^
size:是 boolean 数组的下标
bits:最终得到的 int 数组

1、压缩主要代码:
  public void encode(boolean bit){
        if (bit){
            bits[size / 32] |= 1 << (size & 0x1F);
        }
        size++;
    }

解析:
其实主要就这一句:bits[size / 32] |= 1 << (size & 0x1F);
①、size / 32 :每32位压缩到一个 int 中;
②、size & 0x1F:0x1F 是31,其二进制是 00011111,与 size 相与 可以确保结果值不大于31;
③、1 << size & 0x1F:1的二进制是 00000001,<< 的就是将1向左移位,每移一位相当于乘2;
④、|=:按位相或赋值
e.g.
int temp = 3;

表达式 计算 结果
temp |= 1 00000011
|(或)
00000001 = 00000011
3
temp |= 8 00000011
|(或)
00001000 = 00001011
11

⑤、上面所有的运行下来如下表:
如果 boolean 数组全部为 true:

size size & 0x1F 1 << (size & 0x1F) |= 结果
0 0 1 00000000
|(或)
00000001 = 00000001
bits[0] = 1
1 1 00000001
<< (左移)
1
00000010 = 2
00000001
|(或)
00000010 = 00000011
bits[0] = 3
2 2 00000001
<< (左移)
2
00000100 = 4
00000011
|(或)
00000100 = 00000111
bits[0] = 7
3 3 00000001
<< (左移)
3
00001000 = 8
00000111
|(或)
00001000 = 00001111
bits[0] = 15
... ... ... ... ...
31 31 00000001
<< (左移)
31
10..(28个0)..00 = 32
01..(28个1)..11
|(或)
10..(28个0)..00
=
11..(28个1)..11
bits[0] = -1
over
32 0 00000001
<< (左移)
0
00000001 = 1
00000001
|(或)
00000000 = 00000001
bits[1] = 1
... ... ... ... ...

结果:
bit 位的0、1正好与 boolean 数组的 true、false 逆序
e.g.
boolean 数组:false,true,false,false,true,true
bits 数组:bits[0] --- 00110010

2、解压缩主要代码
    public boolean get(int index){
        return (bits[index / size] & (1 << (index & 0x1F))) != 0;
    }

又是一句话的事...根据上面的过程逆推回去(感觉是编码和解编码的常用套话^ _ ^)

注意:Zxing 源码中并未将 bits 数组的大小提前定好,而是在运行过程中随时扩容的。
扩容代码:

private void ensureCapacity(int size) {
    if (size > bits.length * 32) {
      int[] newBits = makeArray(size);
      System.arraycopy(bits, 0, newBits, 0, bits.length);
      this.bits = newBits;
    }
}

private static int[] makeArray(int size) {
    return new int[(size + 31) / 32];
}

上一篇 下一篇

猜你喜欢

热点阅读