# Exploring Java BitSet

*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

packageorg.mano.example;importjava.util.BitSet;importjava.util.Random;public classMain {public static intN_BITS= 16;public static voidmain(String[] args) { BitSet b1 =newBitSet(N_BITS); BitSet b2 =newBitSet(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..println("No. of set values in b1=" + b1.cardinality()); System.out.println("No. of set values in b2=" + b2.cardinality()); b1.or(b2);outprintBits("b1 OR b2, b1 = ", b1); b2.xor(b1);printBits("b2 XOR b1, b2 = ", b2);printBits("b1 = ", b1); System..println("indexes where bit is set in b1 " + b1.toString());outprintBits("b2 = ", b2); System..println("indexes where bit is set in b2 " + b2.toString()); }outpublic static voidsetRandomBits(BitSet b) { Random r =newRandom();for(inti = 0; i <N_BITS/ 2; i++) b.set(r.nextInt(N_BITS)); }public static voidprintBits(String prompt, BitSet b) { System..print(prompt + " ");outfor(inti = 0; i <N_BITS; i++) { System..print(b.get(i) ? "1" : "0"); } System.out.println(); } }out

## 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

**, to find out a list of prime numbers within a range using**

*Sieve of Eratosthenes**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

packageorg.mano.example;importjava.util.BitSet;importjava.util.Scanner;public classMain {public static voidmain(String[] args) { Scanner scanner =newScanner(System.); System.in.println("Enter the range. Any number greater than 2: ");outintinput = scanner.nextInt();if(input < 2) System..println("Invalid number. Program will exit");outelsegeneratePrime(input); scanner.close(); }public static voidgeneratePrime(intmax) {intcounter = 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 halfintbSize = (max - 2) / 2; // BitSet created with a specific size // with default value initialized as false BitSet bitSet =newBitSet(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 sundaramfor(inti = 1; i <= bSize; i++)for(intj = 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 2if(max > 2) System..print("2\t"); // Now print the odd prime list, with a little // formatting for eye-candy.outfor(inti = 1; i <= bSize; i++) {if(bitSet.get(i) ==false) { System..print((2 * i + 1)); System.out.print(++counter % 9 == 0 ? "\n" : "\t"); } } } }out

## 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.

*This article was originally published on July 13, 2016*