Bit Sets Core Java

The Java platform BitSet class stores a sequence of bits. (It is not a set in the mathematical sense—bit vector or bit array would have been more appropriate terms.) Use a bit set if you need to store a sequence of bits (for example, flags) efficiently. Because a bit set packs the bits into bytes, it is far more efficient to use a bit set than to use an ArrayList of Boolean objects. The BitSet class gives you a convenient interface for reading, setting, or resetting individual bits. Use of this interface avoids the masking and other bit-fiddling operations that would be necessary if you stored bits in int or long variables.

For example, for a BitSet named bucketOfBits,

returns true if the i’th bit is on, and false otherwise. Similarly,

turns the i’th bit on. Finally,

turns the i’th bit off.

C++ NOTE: The C++ bitset template has the same functionality as the Java platform BitSet.

java.util.BitSet 1.0

  • BitSet(int initialCapacity)
    constructs a bit set.
  • int length()
    returns the “logical length” of the bit set: 1 plus the index of the highest set bit.
  • boolean get(int bit)
    gets a bit.
  • void set(int bit)
    sets a bit.
  • void clear(int bit)
    clears a bit
  • void and(BitSet set)
    logically ANDs this bit set with another.
  • void or(BitSet set)
    logically ORs this bit set with another.
  • void xor(BitSet set)
    logically XORs this bit set with another.
  • void andNot(BitSet set)
    clears all bits in this bit set that are set in the other bit set.

The “Sieve of Eratosthenes” Benchmark As an example of using bit sets, we want to show you an implementation of the “sieve
of Eratosthenes” algorithm for finding prime numbers. (A prime number is a number like 2, 3, or 5 that is divisible only by itself and 1, and the sieve of Eratosthenes was one of the first methods discovered to enumerate these fundamental building blocks.) This isn’t a terribly good algorithm for finding the number of primes, but for some reason it has become a popular benchmark for compiler performance. (It isn’t a good benchmark either, because it mainly tests bit operations.)

Oh well, we bow to tradition and include an implementation. This program counts all prime numbers between 2 and 2,000,000. (There are 148,933 primes, so you probably don’t want to print them all out.) Without going into too many details of this program, the key is to march through a bit set with 2 million bits. We first turn on all the bits. After that, we turn off the bits that are multiples of numbers known to be prime. The positions of the bits that remain after this process are themselves the prime numbers. Listing below illustrates this program in the Java programming language, and Listing below is the C++ code.

NOTE: Even though the sieve isn’t a good benchmark, we couldn’t resist timing the two implementations of the algorithm. Here are the timing results on a 1.66-GHz dual core ThinkPad with 2 GB of RAM, running Ubuntu 7.04.

  • C++ (g++ 4.1.2): 360 milliseconds
  • Java (Java SE 6): 105 milliseconds

We have run this test for seven editions of Core Java, and in the last three editions. Java easily beat C++. In all fairness, if one cranks up the optimization level in the C++ compiler, it beats Java with a time of 60 milliseconds. Java could only match that if the program ran long enough to trigger the Hotspot just-in-time compiler.

Sieve.java

Sieve.cpp

This completes our tour through the Java collection framework. As you have seen, the Java library offers a wide variety of collection classes for your programming needs. In the final chapter of this book, we will cover the important topic of concurrent programming.


Face Book Twitter Google Plus Instagram Youtube Linkedin Myspace Pinterest Soundcloud Wikipedia

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Core Java Topics