1. What is BitSet?
Note: The following content comes from the JDK API:
The BitSet class implements a bit vector that grows on demand. Each component of the bitset has a boolean value. Index the bits of BitSet with non-negative integers. Each indexed bit can be tested, set, or cleared. Through logical AND, logical or logical XOR operations, one BitSet can be used to modify the content of another BitSet.
By default, the initial values of all bits in set are false.
Each bit set has a current size, that is, the number of bits of the current space used by the bit set. Note that this size is related to the implementation of bitset, so it may change with the implementation. The length of a bit set is related to the logical length of a bit set and is defined independent of implementation.
A Bitset class creates a special type of array to hold bit values. The array size in BitSet will increase as needed. This is similar to the bit vector (vectorofbits).
This is a traditional class, but it has been completely redesigned in Java2.
BitSet defines two constructors.
The first constructor creates a default object:
BitSet()
The second method allows the user to specify the initial size. All bits are initialized to 0.
BitSet(intsize)
2. Java BitSet implementation principle
In java, the implementation of BitSet is located in the java.util package:
public class BitSet implements Cloneable, java.io.Serializable {private final static int ADDRESS_BITS_PER_WORD = 6;private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;/* Used to shift left or right for a partial word mask */private static final long WORD_MASK = 0xffffffffffffffffL;private static final ObjectStreamField[] serialPersistentFields = { new ObjectStreamField("bits", long[].class),};/** * The internal field corresponding to the serialField "bits". */private long[] words;.....}As you can see, the underlying implementation of BitSet uses long arrays as the internal storage structure, so the size of BitSet is an integer multiple of the size of long type (64-bit).
It has two constructors:
1. BitSet(): Create a new bit set, the default size is 64 bits.
public BitSet() { initWords(BITS_PER_WORD); sizeIsSticky = false;}2. BitSet(int nbits): Create a bit set whose initial size is sufficient to explicitly represent bits with an index range of 0 to nbits-1.
public BitSet(int nbits) { // nbits can't be negative; size 0 is OK if (nbits < 0) throw new NegativeArraySizeException("nbits < 0: " + nbits); initWords(nbits); sizeIsSticky = true; }Note:
1. If the initialization size of bitset is specified, it will be regularized to an integer greater than or equal to 64 of this number. For example, for 64 bits, the size of bitset is 1 long, while for 65 bits, the size of bitset is 2 long, that is, 128 bits. This regulation is mainly for memory alignment, while avoiding the consideration of not dealing with special circumstances and simplifying the program.
2: BitSet's size method: Returns this BitSet to represent the actual number of bits used when the bit value is an integer multiple of 64.
length method: Return the "logical size" of this BitSet: the index of the highest set bit in the BitSet is added by 1
3. Use scenarios
A common application scenario is to conduct some statistical work on massive data, such as log analysis, user counting, etc.
I was asked a question before internship interview with Alibaba: There are 10 million random numbers, and the range of random numbers is between 100 million and 100 million. Now I need to write an algorithm to find out the numbers between 100 million and 100 million that are not in random numbers?
The code example is as follows:
public class Alibaba{public static void main(String[] args) {Random random=new Random();List<Integer> list=new ArrayList<>();for (int i=0;i<10000000;i++) {int randomResult=random.nextint(1000000000);list.add(randomResult);}System.out.println("The random number generated is"); for (int i=0;i<list.size();i++) {System.out.println(list.get(i));}BitSet bitSet=new BitSet(100000000);for (int i=0;i<10000000;i++) {bitSet.set(list.get(i));}System.out.println("0 to 100 million are not included in the above random numbers"+bitSet.size());for (int i = 0; i < 100000000; i++) {if(!bitSet.get(i)) {System.out.println(i);}}}}Summarize
The above is all about this article discussing the usage scenarios and code examples of Java BitSet, and I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!