BitSet位图算法 博客分类: 算法 算法IDEA

位图算法,使用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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

Java HashMap的工作原理

面试的时候经常会遇见诸如:“java中的HashMap是怎么工作的”,“HashMap的get和put内部的工作原理”这样的问题。本文将用一个简单的例子来解释下...

8310
来自专栏开发与安全

数据结构:双向链表实现队列与循环链表

一、双向链表(double linked list)如图26.5,是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,...

30480
来自专栏Golang语言社区

Golang语言--布尔型和数值类型

布尔类型 布尔类型是 bool。Go语言提供了内置的布尔值true和flase。Go语言支持标准的逻辑和比较操作。这些操作的结果都是布尔值。 布尔值和表达式可以...

39680
来自专栏desperate633

LeetCode 17. Letter Combinations of a Phone Number题目分析代码

以上的答案是按照词典编撰顺序进行输出的,不过,在做本题时,你也可以任意选择你喜欢的输出顺序。

9310
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高二十】集合指定初始容量&asList缺陷&subList缺陷

【Java提高二十】集合指定初始容量 &asList缺陷&subList缺陷 集合指定初始容量 集合是我们在Java编程中使用非常广泛的,它就像大海,海纳百川,...

39970
来自专栏Android知识点总结

Java容器源码攻坚战--第一战:Iterator

11310
来自专栏轮子工厂

深入理解Java中的List、Set与Map集合

12740
来自专栏Python爬虫实战

LeetCode刷题:Array系列之Remove Element

#include <iostream> #include <vector> using namespace std;

8310
来自专栏python3

Python变量类型

有符号整数,就是C语言中所指的整型,也就是数学中的整数,它的大小与安装的解释器的位数有关

19820
来自专栏Kevin-ZhangCG

Java集合总结

18520

扫码关注云+社区

领取腾讯云代金券