Bit-map算法学习
Little-endian和big-endian
Big endian 认为第一个字节是最高位字节（按照从低地址到高地址的顺序存放数据的高位字节到低位字节）；而 Little endian 则相反，它认为第一个字节是最低位字节（按照从低地址到高地址的顺序存放据的低位字节到高位字节）。
关于Bit-map
用一个bit位来标记某个元素对应的Value， key0|1表示该元素是否存在(类似于桶排序算法)，由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。
假设我们要对0-7内的6个不重复元素排序，开辟一个8个Bit(1Bytes)的内存空间，此时所有的bit位为0，遍历6个元素，将对应下标的bit位置为1 (采用big-endian)。处理完所有元素后，对Bytes区域进行遍历，将该位是一的位的编号输出，达到排序的目的。对于更多的元素排序，可以扩展为Bytes数组进行存储排序。
思想
使用bit数组来表示某些元素是否存在，达到节省空间的目的。
算法实现-Java
public class BitmapTest {
//保存数据的
private byte[] bitArray;
//能够存储多少bit数据
private int capacity;
public BitmapTest(int capacity) {
this.capacity = capacity;
this.bitArray = new byte[(capacity >>3 )+1];
}
/**
* byte[index] ——> Index(N) = N/8 = N >> 3;
* bit位Position ——> Position(N) = N%8 = N & 0x07;
*/
public void add(int num){
// byte[]的index
int arrayIndex = num >> 3;
// byte[index]的Position位置
int position = num & 0x07;
//将1左移position后，Position位置置为1，然后和byte里的数据做|操作，byte数据里的position为1。
bitArray[arrayIndex] |= 1 << position;
}
public void clear(int num){
// byte[]的index
int arrayIndex = num >> 3;
// byte[index]的Position位置
int position = num & 0x07;
//将1左移position后，Position位置置为1，然后对取反，再与byte里的数据做&操作，即可清除当前的位置了.
bitArray[arrayIndex] &= ~(1 << position);
}
public boolean contain(int num){
// num/8得到byte[]的index
int arrayIndex = num >> 3;
// num%8得到在byte[index]的Position位置
int position = num & 0x07;
//将1左移position后，Position位置置为1，然后与byte里的数据做&，判断是否为0即可
return (bitArray[arrayIndex] & (1 << position)) !=0;
}
}
常见实例
- 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
Bitmap的方法，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
- 在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数
采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存。扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。