dcsimg
December 3, 2016
Hot Topics:

Exploring Java BitSet

  • July 13, 2016
  • By Manoj Debnath
  • Send Email »
  • More Articles »

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,

Bit1
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:

Bit2
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("2\t");

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


Tags: Java, API, class, algorithm, bit manipulation, Boolean, BitSet, bitwise




Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Enterprise Development Update

Don't miss an article. Subscribe to our newsletter below.

Sitemap | Contact Us

Thanks for your registration, follow us on our social networks to keep up-to-date
Rocket Fuel