- 位图使用基本情况
- 一个字节有8位,假设第0位表示0,第1位表示1,那么一个字节就可以表示8个数字。整数序列{0,1,4,7}, 在位序列中表示为10010011,左边第一位为低位,表示有效数字0。
- 位序列如何表示?
- Java 整形int 用4个字节表示,可以用整形int 数组表示位序列:
- 初始化一整形数组 int[] bitMap = new int[(N >> 5) + 1]
- bitMap[0] 4个字节共32位,表示区间[0 , 31]
- bitMap[1] 4个字节共32位,表示区间[32, 63]
- 以上规律,整数x 在位序列的位置可以定位到bitMap[(x >> 5)]
- bitMap[(x >> 5)] 4个字节共32位,具体用哪一位表示,由整数x的最低5位确定 (1 << ( x & 0x1F))
- 位序列置位函数
void setBit( int x ) { bitMap[(x >> 5)] |= (1 << ( x & 0x1F))}
- 位序列清位函数
void clrBit( int x ) { bitMap[(x >> 5)] &= ~(1 << ( x & 0x1F))}
- 对一数量为N(小于10000000)的非负整数序列排序,该整数序列中的元素具有唯一性。
private void genDataSet(){
File dataSet = new File(File_PATH);
DataOutputStream out = null;
try{
if( !dataSet.exists()){
dataSet.createNewFile();
}
out = new DataOutputStream(new FileOutputStream(dataSet));
for(int i = DATA_COUNT; i >= 0 ; i--){