实现MyBitSet类

书中第一章主要是使用位向量来解决特定的磁盘文件排序问题。
故此处需要使用Java来表示并操作位向量。
BitSet类提供了这个功能，不过在这里我决定自己实现一个BitSet的类，MyBitSet。

设计

决定只提供解决第一章问题所要用到的功能即可，设计如下：

1. 构造函数MyBitSet(int size)，可存储size个二进制位；
2. getSize()方法，返回size；
3. set(int index)，设置index为1;
4. clear(int index)，设置index为0;
5. get(int index)返回index位的值；
6. toString()，像一个数组一样打印；

实现思路与细节

Java基本类型中有byte，其占用一个字节，8个位，我打算利用它以及Java本身提供的位操作(&, |, ~)来实现上面的设计。

使该类实例持有一个byte[] byteList，client不知其实现细节，通过size与想要操作的index与myBitSet实例交流。

比如client声明：MyBitSet myBitSet = new MyBitSet(4);。
则在构造器中，根据4，考虑到一个byte占用8个位，则用size/8以及size%8的结果可以算出byteList的长度，当size=4时，只需要一个byte即可，即byteList.length为1。

同时，当client要通过set或clear操作某位时，提供的是client所理解的位的index。
比如，myBitSet.set(2);。
通过2/8=0，且2%8=2!=0可以得出，index为2的位对应于byteList数组的第1个元素的下标为2的位，接着，进行下一步操作。

操作某个byte的某个位时，是对8个位同时进行操作的，不能影响到该byte上其他位上的值。
使用几个常量ZERO~SEVEN分别代表0b00000001，0b00000010到ob10000000，用来做mask去与byte进行位操作，达到三个效果，将一个byte中的某一位(0-7)设为1，设为0，取值。
根据set, get, clear的下标index，可以得到byteList中的一个byte b，亦可得到该位在b中的下标byteIndex，以及与byteIndex对应的mask。

经思考后，三种操作分别通过下面的方法实现：
set: b = (byte) (b | mask);
clear: b = (byte) (b & ~mask);
get: b & mask;

关于mask的表示，使用byte即可，取值为1， 2， 4这样的2的次方，而SEVEN应该是128，可是byte最大正整数范围为127，这里我们使用(byte) 128来向下转型，将前面的0截断掉，即得到了需要的2进制序列。

代码

package guerbai.chapter1_opening;

import org.apache.lucene.util.RamUsageEstimator;

public class MyBitSet {
    private static byte ZERO = 1;
    private static byte ONE = 2;
    private static byte TWO = 4;
    private static byte THREE = 8;
    private static byte FOUR = 16;
    private static byte FIVE = 32;
    private static byte SIX = 64;
    private static byte SEVEN = (byte) 128;
    private int size;
    private byte[] byteList;

    public MyBitSet(int size) {
        this.size = size;
        int byteCount = size / 8;
        int remainder = size % 8;
        if (remainder > 0) {
            byteCount++;
        }
        byteList = new byte[byteCount];
    }

    public int getSize() {
        return size;
    }

    public void set(int index) {
        int byteIndex = index / 8;
        int byteRemainder = index % 8;
        byte mask = getMask(byteRemainder);
        byteList[byteIndex] = (byte) (byteList[byteIndex] | mask);
    }

    public void clear(int index) {
        int byteIndex = index / 8;
        int byteRemainder = index % 8;
        short mask = getMask(byteRemainder);
        byteList[byteIndex] = (byte) (byteList[byteIndex] & ~mask);
    }

    public byte get(int index) {
        int byteIndex = index / 8;
        int byteRemainder = index % 8;
        byte mask = getMask(byteRemainder);
        if ((byte) (byteList[byteIndex] & mask) == mask) {
            return 1;
        } else {
            return 0;
        }
    }

    public String toString() {
        StringBuffer s = new StringBuffer();
        s.append('[');
        for (int i=0; i<size; i++) {
            s.append(get(i)+", ");
        }
        s.append(']');
        return new String(s);
    }

    private byte getMask(int remainder) {
        byte mask;
        switch (remainder) {
            case 0:
                mask = MyBitSet.ZERO;
                break;
            case 1:
                mask = MyBitSet.ONE;
                break;
            case 2:
                mask = MyBitSet.TWO;
                break;
            case 3:
                mask = MyBitSet.THREE;
                break;
            case 4:
                mask = MyBitSet.FOUR;
                break;
            case 5:
                mask = MyBitSet.FIVE;
                break;
            case 6:
                mask = MyBitSet.SIX;
                break;
            case 7:
                mask = MyBitSet.SEVEN;
                break;
            default:
                mask = MyBitSet.ZERO;
                break;
        }
        return mask;
    }

    public static void main(String[] args) {
        MyBitSet mbs = new MyBitSet(10000000);
        System.out.println(RamUsageEstimator.sizeOf(mbs));
        MyBitSet mbs2 = new MyBitSet(13);
        System.out.println(mbs2);
        mbs2.set(3);
        System.out.println(mbs2);
        mbs2.set(7);
        System.out.println(mbs2);
        mbs2.set(12);
        System.out.println(mbs2);
        mbs2.clear(7);
        System.out.println(mbs2);
    }
}

输出结果如下：
1250040
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ]
[0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, ]
[0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, ]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, ]

可以看到，10^7个位只占用了1M多内存，同时，set, get, clear, toString等效果符合预期。