bitmap

利用bit位来表示数据，节省空间，redis、elsaticsearch 等中间件都使用了bitmap数据结构。

因为java中不能直接操作bit，因此使用int类型（或者long类型）的正数来存储bit位，对于大量数据，可以使用int数组或者long数组，相对单个多了一次数组的索引定位

public class BitMap {
    //存储，最多32位
    private int word = 0;
}

• 设置 bit

public void setBit(int index, boolean flag) {
    if (flag) {
      	// word | 00000000...1...00000000
      	word |= (1 << index);
    } else {
      	// word & 11111111...0...11111111
      	word &= ~(1L << index);
    }
}

• 获取某位的bit

public boolean getBit(int index) {
        return (word & (1 << index)) != 0;
}

• 统计bit

public int bitCount1() {
      int n = word;
      int count = 0;
      while (n != 0) {
        count += n & 1;
        //每次算术右移一位，高位补0
        n = n >>> 1;
      }
      return count;
}

public int bitCount2() {
      int n = word;
      int count = 0;
      while (n != 0) {
        count++;
        n -= (n & -n);   //减掉低位1
      }
      return count;
}

//java Integer.bitCount 的实现
public int bitCount3() {
      //Integer.bitCount
      int i = word;
      i = i - ((i >>> 1) & 0x55555555);
      i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
      i = (i + (i >>> 4)) & 0x0f0f0f0f;
      i = i + (i >>> 8);
      i = i + (i >>> 16);
      return i & 0x3f;
}