BitSet的用法

时间:2022-09-17 19:28:18

1,BitSet类
    大小可动态改变, 取值为true或false的位集合。用于表示一组布尔标志。

此类实现了一个按需增长的位向量。位 set 的每个组件都有一个 boolean 值。用非负的整数将 BitSet 的位编入索引。可以对每个编入索引的位进行测试、设置或者清除。通过逻辑与、逻辑或和逻辑异或操作,可以使用一个 BitSet 修改另一个 BitSet 的内容。

默认情况下,set 中所有位的初始值都是 false。

每个位 set 都有一个当前大小,也就是该位 set 当前所用空间的位数。注意,这个大小与位 set 的实现有关,所以它可能随实现的不同而更改。位 set 的长度与位 set 的逻辑长度有关,并且是与实现无关而定义的。

除非另行说明,否则将 null 参数传递给 BitSet 中的任何方法都将导致 NullPointerException。 在没有外部同步的情况下,多个线程操作一个 BitSet 是不安全的。

2,构造函数: BitSet() or BitSet(int nbits)

3,方法:

public void set(int pos): 位置pos的字位设置为true。 
public void set(int bitIndex, boolean value) 将指定索引处的位设置为指定的值。 
public void clear(int pos): 位置pos的字位设置为false。
public void clear() : 将此 BitSet 中的所有位设置为 false。 
public int cardinality() 返回此 BitSet 中设置为 true 的位数。 
public boolean get(int pos): 返回位置是pos的字位值。 
public void and(BitSet other): other同该字位集进行与操作,结果作为该字位集的新值。 
public void or(BitSet other): other同该字位集进行或操作,结果作为该字位集的新值。 
public void xor(BitSet other): other同该字位集进行异或操作,结果作为该字位集的新值。
public void andNot(BitSet set) 清除此 BitSet 中所有的位,set - 用来屏蔽此 BitSet 的 BitSet
public int size(): 返回此 BitSet 表示位值时实际使用空间的位数。
public int length() 返回此 BitSet 的“逻辑大小”:BitSet 中最高设置位的索引加 1。 
public int hashCode(): 返回该集合Hash 码, 这个码同集合中的字位值有关。 
public boolean equals(Object other): 如果other中的字位同集合中的字位相同,返回true。 
public Object clone() 克隆此 BitSet,生成一个与之相等的新 BitSet。 
public String toString() 返回此位 set 的字符串表示形式。

例1:标明一个字符串中用了哪些字符

import java.util.BitSet;
public class WhichChars{
private BitSet used = new BitSet();
public WhichChars(String str){
for(int i=0;i< str.length();i++)
used.set(str.charAt(i)); // set bit for char
}
public String toString(){
String desc="[";
int size=used.size();
for(int i=0;i< size;i++){
if(used.get(i))
desc+=(char)i;
}
return desc+"]";
}
public static void main(String args[]){
WhichChars w=new WhichChars("How do you do");
System.out.println(w);
}
}

运行:
C:\work>java WhichChars

[ Hdouwy]

4

java.util.BitSet可以按位存储。
计算机中一个字节(byte)占8位(bit),我们java中数据至少按字节存储的,
比如一个int占4个字节。
如果遇到大的数据量,这样必然会需要很大存储空间和内存。
如何减少数据占用存储空间和内存可以用算法解决。
java.util.BitSet就提供了这样的算法。
比如有一堆数字,需要存储,source=[3,5,6,9]
用int就需要4*4个字节。
java.util.BitSet可以存true/false。
如果用java.util.BitSet,则会少很多,其原理是:
1,先找出数据中最大值maxvalue=9
2,声明一个BitSet bs,它的size是maxvalue+1=10
3,遍历数据source,bs[source[i]]设置成true.
最后的值是:
(0为false;1为true)
bs [0,0,0,1,0,1,1,0,0,1]
                3,   5,6,       9

这样一个本来要int型需要占4字节共32位的数字现在只用了1位!
比例32:1  
这样就省下了很大空间。

例子:

package com;  

import java.util.BitSet;  

public class MainTestThree {  

    /**
* @param args
*/
public static void main(String[] args) {
BitSet bm=new BitSet();
System.out.println(bm.isEmpty()+"--"+bm.size());
bm.set(0);
System.out.println(bm.isEmpty()+"--"+bm.size());
bm.set(1);
System.out.println(bm.isEmpty()+"--"+bm.size());
System.out.println(bm.get(65));
System.out.println(bm.isEmpty()+"--"+bm.size());
bm.set(65);
System.out.println(bm.isEmpty()+"--"+bm.size());
} }

输出:
 true--64
false--64
false--64
false
false--64
false--128

例子2:

package com;  

import java.util.BitSet;  

public class MainTestFive {  

    /**
* @param args
*/
public static void main(String[] args) {
int[] shu={2,42,5,6,6,18,33,15,25,31,28,37};
BitSet bm1=new BitSet(MainTestFive.getMaxValue(shu));
System.out.println("bm1.size()--"+bm1.size()); MainTestFive.putValueIntoBitSet(shu, bm1);
printBitSet(bm1);
} //初始全部为false,这个你可以不用,因为默认都是false
public static void initBitSet(BitSet bs){
for(int i=0;i<bs.size();i++){
bs.set(i, false);
}
}
//打印
public static void printBitSet(BitSet bs){
StringBuffer buf=new StringBuffer();
buf.append("[\n");
for(int i=0;i<bs.size();i++){
if(i<bs.size()-1){
buf.append(MainTestFive.getBitTo10(bs.get(i))+",");
}else{
buf.append(MainTestFive.getBitTo10(bs.get(i)));
}
if((i+1)%8==0&&i!=0){
buf.append("\n");
}
}
buf.append("]");
System.out.println(buf.toString());
}
//找出数据集合最大值
public static int getMaxValue(int[] zu){
int temp=0;
temp=zu[0];
for(int i=0;i<zu.length;i++){
if(temp<zu[i]){
temp=zu[i];
}
}
System.out.println("maxvalue:"+temp);
return temp;
}
//放值
public static void putValueIntoBitSet(int[] shu,BitSet bs){
for(int i=0;i<shu.length;i++){
bs.set(shu[i], true);
}
}
//true,false换成1,0为了好看
public static String getBitTo10(boolean flag){
String a="";
if(flag==true){
return "1";
}else{
return "0";
}
} }

输出:

maxvalue:42
bm1.size()--64
[
0,0,1,0,0,1,1,0,
0,0,0,0,0,0,0,1,
0,0,1,0,0,0,0,0,
0,1,0,0,1,0,0,1,
0,1,0,0,0,1,0,0,
0,0,1,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0
]

这样便完成了存值和取值。
注意它会对重复的数字过滤,就是说,一个数字出现过超过2次的它都记成1。
出现的次数这个信息就丢了。

BitSet的用法的更多相关文章

  1. STL中bitset的用法

    终于又来写博客了 == bitset存储的是二进数位,就和一个bool性数组差不多.用法上和数组的操作方式也差不多. 每位只占一个字节,大大优化了空间,可以通过数组形式访问. bitset定义 可以用 ...

  2. bitset简单用法

    bitset的创建: #include<bitset> bitset<32> ar; //默认全为0 bitset<32> ar(n); //n的二进制 bitse ...

  3. bitset基础用法&plus;心得

    今天上午听AntiLeaf学长讲课,获悉了bitset这种神奇的操作,还是大喊一句:stl大法吼啊! bitset是用来进行一些状态储存的操作.类似于一个标记数组,又类似于状压里面的二进制. 它与状压 ...

  4. bitset常用用法&amp&semi;&amp&semi;简单题分析

    Preface bitset,还是一个比较好用的STL,可以给一些题目做到神奇的常数优化(\(O(\frac{原来的复杂度}{机器的位数(32位or64位)})\)) 关于一些具体的函数等内容可以参考 ...

  5. 位运算 进制转化 STL中bitset用法

    2017-08-17 16:27:29 writer:pprp /* 题目名称:输入十进制以二进制显示 程序说明:同上 作者:pprp 备注:无 日期:2017/8/17 */ #include &l ...

  6. 比特镇旅游&lpar;Tourist Attractions&rpar;【暴力&plus;Bitset 附Bitset用法】

    Online Judge:NOIP2016十连测第一场 T2 Label:暴力,Bitset 题目描述 在美丽的比特镇一共有n个景区,编号依次为1到n,它们之间通过若干条双向道路连接. Byteasa ...

  7. hdu5745&lpar;dp&plus;bitset&rpar;

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=5745 C++ bitset的用法:https://www.cnblogs.com/magisk/p/880 ...

  8. Bipartite Graph hdu 5313 bitset 并查集 二分图

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=5313 题意: 给出n个顶点,m条边,问最多添加多少条边使之构成一个完全二分图 存储结构: bitset   ...

  9. cdoj 1259 线段树&plus;bitset 区间更新&sol;查询

    Description 昊昊喜欢运动 他N天内会参加M种运动(每种运动用一个[1,m]的整数表示) 现在有Q个操作,操作描述如下 昊昊把第l天到第r天的运动全部换成了x(x∈[1,m]) 问昊昊第l天 ...

随机推荐

  1. Partition2:对表分区

    在SQL Server中,普通表可以转化为分区表,而分区表不能转化为普通表,普通表转化成分区表的过程是不可逆的,将普通表转化为分区表的方法是: 在分区架构(Partition Scheme)上创建聚集 ...

  2. ebs R12&period;2启动报错&quot&semi;failed to start a managed process after the maximum retry limit&quot&semi;

    启动日志: Error --> Process (index=1,uid=1739599208,pid=4479) failed to start a managed process after ...

  3. TortoiseSVN的相关问题

    图标覆盖问题: 创建一个保存文档的目录,创建一个工作目录,工作目录创建后,没有显示覆盖图标.解决办法如下: 找到设置,在工作目录下右键 打开界面如下: 从包含路径中设置就可以. 目录检出后把它从检出状 ...

  4. Java for LeetCode 169 Majority Element

    Given an array of size n, find the majority element. The majority element is the element that appear ...

  5. hdu4570Multi-bit Trie

    链接 13年长沙邀请赛的题,神题意~ 题意:摘自http://blog.csdn.net/libin56842/article/details/9703457 这题题意确实有点难懂,起码对于我这个英语 ...

  6. map&comma;set的模板&lbrack;STL&rsqb;

    之前写某题单词查找的时候,有用到set,晚上写codeforces#497 div2 D题有用到map 感觉set,map的功能挺类似的,在此小结: 这里就不具体比较相同点和不同点了,免得看起来乱七八 ...

  7. ubuntu在指定的文件夹下创建python3和python2的虚拟环境

    1.用pip安装virtualenv sudo apt-get install python-virtualenv 2.创建python2和python3虚拟环境 2.1 创建python2的虚拟环境 ...

  8. nmap - 网络扫描

    NMap,Network Mapper 最早是Linux下的网络扫描和嗅探工具包 网络链接扫描; nmap -PT 192.168.1.1-111 # 先ping在扫描主机开放端口 nmap -O 1 ...

  9. Putty实现Linux与Windows互传文件

    putty远程连接VPS,先开一贴,有空来整理. 从putty官网下载putty,选择[A Windows installer for everything except PuTTYtel]安装包,下 ...

  10. vim的vim-addons的问题

    最近急切想把vim变成IDE,这个过程的毕竟之路就是装插件,vim有自己的插件管理软件装起插件来相当方便,首先安装这个软件: sudo apt-get install vim-addon-manage ...