BitSet is a class defined in the java.util package. It creates an array of bits represented by boolean values. The size of the array is flexible and can grow to accommodate additional bit as needed. Because it is an array, the bit values can be accessed by non-negative integers as an index. The interesting aspect of BitSet is that it is easy to create and manipulate bit sets that basically represents a set of boolean flags. This article shall provide the necessary details on how to use this API with appropriate examples in Java.
The BitSet Class
The BitSet class provides two constructors: a no-argument constructor to create an empty BitSet object and a one-constructor with an integer argument to represent number of bits in the BitSet.
- BitSet(): Creates an empty instance of the BitSet class.
- BitSet(int noOfBits): Creates an instance of the BitSet class with an initial size of the integer argument representing the number of bits.
The default value of the BitSet is boolean false with an underlying representation as 0 (off). The bit position in the BitSet array can be set to 1 (on) as true with the help of the index of the bit represented as an argument to the set method. The index is zero-based, similar to an array. Once you call the clear method, the bit values are automatically set to false. To access a specific value in the BitSet, the get method is used with an integer argument as an index.
BitSet Methods
The class also provides methods for common bit manipulation using bitwise logical AND, bitwise logical OR, and bitwise logical exclusive OR with and, or, and xor methods, respectively. For example, assume that there are two BitSet instances, bit1 and bit2. Then the statement,
bit1.and(bit2)
will perform bitwise logical AND operation, Similarly,
bit1.or(bit2)
will perform bitwise logical OR operation and
bit1.xor(bit2)
will perform a bitwise logical XOR operation. The result will be stored in bit1. If there are more bits in bit2 than bit1, the additional bits of bit2 are ignored. As a result, the size of bit1 remains unchanged even after the result of the bitwise operation is stored. In fact, the bitwise operations are performed in a logical bit-by-bit fashion.
The size method returns the number of bits of space actually in use by the BitSet. There is another method, called length, that returns the logical size of the BitSet; that means the index of the highest set, bit + 1. Two BitSets can be compared for equality with the equals method. They are equal if and only if they are the same bit by bit.
An Example of Bit Manipulation
package org.mano.example; import java.util.BitSet; import java.util.Random; public class Main { public static int N_BITS = 16; public static void main(String[] args) { BitSet b1 = new BitSet(N_BITS); BitSet b2 = new BitSet(N_BITS); printBits("inital bit pattern of b1: ", b1); printBits("inital bit pattern of b2: ", b2); setRandomBits(b1); setRandomBits(b2); printBits("After random bit set of b1: ", b1); printBits("After random bit set of b2: ", b2); b2.and(b1); printBits("b2 AND b1, b2 = ", b2); System.out.println("No. of set values in b1=" + b1.cardinality()); System.out.println("No. of set values in b2=" + b2.cardinality()); b1.or(b2); printBits("b1 OR b2, b1 = ", b1); b2.xor(b1); printBits("b2 XOR b1, b2 = ", b2); printBits("b1 = ", b1); System.out.println("indexes where bit is set in b1 " + b1.toString()); printBits("b2 = ", b2); System.out.println("indexes where bit is set in b2 " + b2.toString()); } public static void setRandomBits(BitSet b) { Random r = new Random(); for (int i = 0; i < N_BITS / 2; i++) b.set(r.nextInt(N_BITS)); } public static void printBits(String prompt, BitSet b) { System.out.print(prompt + " "); for (int i = 0; i < N_BITS; i++) { System.out.print(b.get(i) ? "1" : "0"); } System.out.println(); } }
Output
initial bit pattern of b1: 0000000000000000 initial bit pattern of b2: 0000000000000000 After random bit set of b1: 1110001011001000 After random bit set of b2: 0110000101110000 b2 AND b1, b2 = 0110000001000000 No. of set values in b1=7 No. of set values in b2=3 b1 OR b2, b1 = 1110001011001000 b2 XOR b1, b2 = 1000001010001000 b1 = 1110001011001000 indexes where bit is set in b1 {0, 1, 2, 6, 8, 9, 12} b2 = 1000001010001000 indexes where bit is set in b2 {0, 6, 8, 12}
Using BitSet in the Algorithm “Sieve of Sundaram”
Let’s implement a simple algorithm called Sieve of Sundaram, a variation that’s more efficient than Sieve of Eratosthenes, to find out a list of prime numbers within a range using BitSet.
Quick Idea of the Algorithm
Apart from finding prime number by brute techniques, the algorithm “Sieve of Eratosthenes” is quite intriguing. But here, we shall implement a variation of that algorithm discovered by mathematician S.P. Sundaram in 1934. Hence, it is called “Sieve of Sundaram.” The idea is to cross out the numbers of the form,
Figure 1: The “Sieve of Sundaram”
from a list of integers ranging from 1 to n. The rest of the numbers are incremented by 1. Finally, we get the list containing all the odd prime numbers below 2n+2 (all except 2). The main difference between Eratosthenes’ method and Sundaram’s method is that Sundaram removes numbers that are:
Figure 2: The “Sieve of Sundaram” removes numbers from the equation
This is the key variation that led to an efficient Eratosthenes sieve algorithm. I’m skipping the details, as they is out of scope here. Interested readers may refer here:
for more details on these algorithms.
Implementing the Algorithm in Java
package org.mano.example; import java.util.BitSet; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("Enter the range. Any number greater than 2: "); int input = scanner.nextInt(); if (input < 2) System.out.println("Invalid number. Program will exit"); else generatePrime(input); scanner.close(); } public static void generatePrime(int max) { int counter = 1; // Because the number can be 2n+2 for a given n // and we want a prime number less than n, // we reduce it to half int bSize = (max - 2) / 2; // BitSet created with a specific size // with default value initialized as false BitSet bitSet = new BitSet(bSize); // set the index number of the form // (i + j + 2ij) as true such that 1<=i<=j // this is the main logic of the sieve of sundaram for (int i = 1; i <= bSize; i++) for (int j = i; (i + j + 2 * i * j) <= bSize; j++) bitSet.set(i + j + 2 * i * j); // explicitly 2 is printed because // odd prime numbers below 2n+2 excludes 2 if (max > 2) System.out.print("2t"); // Now print the odd prime list, with a little // formatting for eye-candy. for (int i = 1; i <= bSize; i++) { if (bitSet.get(i) == false) { System.out.print((2 * i + 1)); System.out.print(++counter % 9 == 0 ? "n" : "t"); } } } }
Output
Enter the range. Any number greater than 2: 500 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499
Conclusion
BitSet is convenient class for bit manipulation. Individual bits are represented by boolean true and false values arranged in an array fashion. The method set sets the specified bit to a “on” state and the clear method sets the specified bit to the “off” state. The method get returns true if the bit is on and false if the bit is off. The and, or, or xor method of BitSet performs a bit-by-bit logical AND, OR, and XOR between BitSets, respectively. The result is stored in the BitSet instance that invoked the method.