BitSet位图算法

    位图算法，使用bit存储数据并排序，优点是快速、占用资源少，缺点是只能对整数使用。
    Java和C++中都有已经实现的的BitSet类，可以直接使用。
    举个例子，0到10000中随机出1000个数，然后用位图算法排序：
   

import java.util.BitSet;

public class BitSetDemo {

	public static void main(String[] args) {
		int count = 10000;
		BitSet bit = new BitSet(count);
		int i = 1000;
		while(i > 0) {		
			bit.set((int)(Math.random()*count));
			i--;
		}
		
		for(int index=0; index<count; index++) {
			if(bit.get(index)) {
				System.out.print(index+",");
			}
		}
		System.out.println("end");			
	}
}

 

    Java中的BitSet还有很多其他用法，比如and、or、xor等操作，看下文档就明白了。

 

      下面是我自己的一个简单实现:

package chroya.java;

/**
 * 
 * @author chroya
 *
 */
public class BitSet {

	private int[] mBits;
	private int mSize;
	
	/**
	 * 初始化指定个bit
	 * @param size 初始化的bit数目
	 */
	public BitSet(int size) {
		mSize = size;
		initBits();
	}
	
	/**
	 * 将指定bit位置设为1
	 * @param pos 
	 */
	public void set(int pos) {
		//得到此pos在数组中的索引
		int index = (int)Math.floor(pos/32f);
		//把当前整数的第n位设置为1
		mBits[index] = mBits[index] | (1<<(pos%32));
	}
	
	/**
	 * 获取指定位是否存在
	 * @param pos
	 * @return
	 */
	public boolean get(int pos) {
		int index = (int)Math.floor(pos/32f);
		return mBits[index] == (mBits[index] | 1<<(pos%32));
	}
	
	/**
	 * 指定bit位置设为0
	 * @param pos
	 */
	public void reset(int pos) {
		int index = (int)Math.floor(pos/32f);
		//把当前整数的第n位设置为0
		mBits[index] = mBits[index] & ~(1<<(pos%32));
	}
	
	/**
	 * 初始化整型数组
	 */
	private void initBits() {
		//Java中整型为32位，所以数组长度为位长度/32。
		int count = (int) Math.ceil(mSize/32f);
		mBits = new int[count];
		clear();
	}
	
	/**
	 * 清空，全部置零
	 */
	private void clear() {
		int len = mBits.length;
		for(int index=0; index<len; index++) {
			mBits[index] = 0;
		}
	}
}

重点在：

set:     mBits[index] | (1<<(pos%32))    1移到指定位，加到原数上。如原数为4，pos为3，则0100 | 1000 = 1100
get:     mBits[index] == (mBits[index] | 1<<(pos%32)) 判断重新set指定位之后是否跟原数相等
reset：     mBits[index] & ~(1<<(pos%32))    原数减去1移到指定位的数。如原数为6，pos为2，则0110 & 1011 = 0010

评论

4 楼 chroya 2010-12-12  

Coding.Ghost 写道

呵呵，多谢捧场。

3 楼 Coding.Ghost 2010-12-12  

2 楼 chroya 2010-10-22  

kimmking 写道

不错，
为啥叫位图？

因为每个数据都只用一个bit来存储

1 楼 kimmking 2010-10-21  

不错，
为啥叫位图？