Set就是集合类型，最常见用操作就是判有判无。
常见的底层实现有位向量实现和有序链表实现。
有序链表很简单，双指针撸到底，这里不详细讲。下面我们谈谈java实现位向量。
不止java，C++中也没有直接的位操作。所以想把整数类型映射到一个bit位上，我们要自己定义操作。
C++比较方便的是有unsigned类型。在unsigned 上左移右移都补0。
可java没有unsigned类型。这就麻烦了。如果我们定义short[] 作为位向量 是肯定会出现错误的。
虽然java有额外的>>>移位，右移始终补0。但对于short，它会先将short转为int,再移位，最后再截短赋值。这就会出现错误。
由于short 16bit， int 32bit，演示过于麻烦。我们将其截半，结果是一样的。
比如-1， 8bit 表示 1111 1111 如果>>>2 移位， 我们期望的结果是 0011 1111。
但实际上 -1 会先转为16位： 1111 1111 1111 1111, 再移位： 0011 1111 1111 1111, 最后截短赋值： 1111 1111。
看，本来我们期望结果是0011 1111，但实际上却是1111 1111。这对于我们实现值位映射是不利的。
所以用java实现位向量，不可用short[]，直接用int[]，不可用算术右移>>, 直接用逻辑右移>>>。这样就没问题了。
这样的话，一个int可以存放32个元素的有无信息，充分利用了存储空间。
看，java也可以如此底层。
至于集合的交，并，差等，可以用位运算& | ~ 等实现。最最核心的代码时实现值位存取映射。
下面给出代码：
public class BitSet {
private int setSize; // setSize is the element number of set
private int vectorSize; // vectorSize is the storage that needed by the set
private int[] bitVector;
public BitSet(){
this.setSize = 1000;
this.vectorSize = (this.setSize + 31) >> 5;
this.bitVector = new int[this.vectorSize];
}
/**
* set the volume of the set
* @param setSize the volume of the set
*/
public BitSet(int setSize){
this.setSize = setSize;
this.vectorSize = (setSize + 31) >> 5;
this.bitVector = new int[this.vectorSize];
}
/**
* set member value.Note that the min member should be 1, not 0.
* @param element the element of set
* @param value the value to set; only 0 or 1
* @return true or false
*/
public boolean setMemberValue(int element, int value){
if (element < 1 || element > setSize){
System.err.println("Out of Range!");
return false;
}
element -= 1; // begin with 0 instead of 1.
int id = element / 32;
int ad = element % 32;
int tmp = bitVector[id];
int last = tmp >>> (31 - ad);
tmp = tmp << (ad + 1);
if (last % 2 == 0 && value == 1){
last = last + 1;
}
if (last % 2 == 1 && value == 0){
last -= 1;
}
bitVector[id] = (last << (31 - ad)) | (tmp >>> (ad + 1));
return true;
}
/**
* get the value of the element. Note that the min element is 1, not 0;
* @param element
* @return if the element in the set, return 1; else 0.
*/
public int getMemberValue(int element){
if (element < 1 || element > setSize){
System.err.println("Out Of Range!");
return -1;
}
element -= 1;
int id = element / 32;
int ad = element % 32;
int result = bitVector[id] >>> (31-ad);
result %= 2;
return result;
}
/**
* add the element to the set
* @param element
* @return
*/
public boolean addMember(int element){
if (getMemberValue(element) == 1){
System.err.println("Already In!");
return false;
}
return setMemberValue(element,1);
}
/**
* delete the element of the set
* @param element
* @return
*/
public boolean delMember(int element){
if (getMemberValue(element) == 0){
System.err.println("Not have it!");
return false;
}
return setMemberValue(element,0);
}
/**
* print an int in binary string, from the first bit that not 0.
* @param value
*/
public void printBinaryValue(int value){
System.out.println(Integer.toBinaryString(value));
}
public static void main(String[] args) {
// write your code here
BitSet bitSet = new BitSet(5000);
bitSet.addMember(1);
bitSet.addMember(31);
bitSet.addMember(20);
bitSet.addMember(32);
bitSet.addMember(2);
bitSet.printBinaryValue(bitSet.bitVector[0]);
bitSet.addMember(21);
bitSet.printBinaryValue(bitSet.bitVector[0]);
bitSet.delMember(21);
bitSet.printBinaryValue(bitSet.bitVector[0]);
System.out.println(bitSet.getMemberValue(1));
System.out.println(bitSet.getMemberValue(20));
}
}