Bit Vector

The bit vector is also referred to as bit-array or bit-set. As the name suggests, it’s an array of bits. Every modern programming language supports primitive or basic data types like byte, integer, short etc which are inherently array of bits only. So, is bit-array different?

A byte is composed of 8-bits. Literally, byte data type is also a bit-array of 8 bits or 1 byte. Integer data type of 4 bytes is a bit-array of 32 bits and so on. This is where the similarity stops and life of bit-array begins.

To understand it further let’s take an example. Assume that you want to represent a set of integers in the range of 0 and 999 (both are inclusive). One option is- store these integers in an array of length 1000 (or a list which can grow up to 1000). Remember, it’s a set, so you are going to store only unique numbers in the range.

//Java snippet

int[] set = new int[1000];

set[i] = num

What is the memory requirement of above?

Each integer takes 4 bytes. So, total memory requirement for 1000 integers is 4KB.

can we improve?

If the requirement says that not all numbers in the range might be present in the set, we can use ArrayList instead of an array. So this will improve a bit, as the numbers which are not in the set will not occupy any memory. This helps to an extent but worst-case memory requirement is still 4KB. Also, note that we are focusing purely on space complexity for now!

can we improve?

As long as you going to store each element of the set in an integer, space overhead is going to remain the same.

Bit-Array

A bit can only take two values i.e. 0 or 1. It can be used to denote the presence or absence of an item. This means these 8 bits of a byte can be used to represent presence/absence of an item in the set. Recall that in an integer array, the index is used to get element stored at that location. Similarly, in bit-set, bit at a position can be used to represent the presence of a number.

So as shown in the above figure, we can represent a set of integers in the range of 0 and 7 by just 1 byte ( or 8 bits). If the number is present make bit at the corresponding bit as 1.

So below two operations can be performed on bit-set.

1. Setting an integer in the array
2. Testing if an integer exists in the array/set

Implementing Bit-vector

Now, let’s return to our initial problem of storing integers in the range of 0 and 999.

Number of bits required = 1000

Number of bytes required = 1000/8 = 125

So 1000 integers can be represented in 125 bytes. The difference is huge 125 byte vs 4KB!

Below is the Java implementation:

/**
 * Bit-vector to store integers
 * 
 * @author Siddheshwar
 * 
 */
public class BitArray {
 private byte[] set;
 public BitArray(int length) {
  int arraysize = length >> 3;
  // if length is not multiple of 8
  if (length % 8 != 0) {
   arraysize++;
  }
  this.set = new byte[arraysize];
 }
 /**
  * Set number in the bit-array i.e. make corresponding bit as 1
  */
 public void storeNumber(int number) {
  if (number > (set.length << 3) || number < 0) {
   throw new IllegalArgumentException("number out of range");
  }
  int arrayIndex = this.getArrayIndex(number);
  int bitIndex = this.getBitIndex(number);
  // shift 1 to the bit index
  int pos = 1 << bitIndex;
  // so bit at position needs to be made 1
  this.set[arrayIndex] = (byte) (this.set[arrayIndex] | pos);
 }
 /**
  * Return true if the corresponding bit is 1
  */
 public boolean numberExists(int number) {
  if (number > (set.length << 3) || number < 0) {
   throw new IllegalArgumentException("number out of range");
  }
  int arrayIndex = this.getArrayIndex(number);
  int bitIndex = this.getBitIndex(number);
  // shift 1 to the bit index
  int pos = 1 << bitIndex;
  // check bit at position is 0 or 1
  return (this.set[arrayIndex] & pos) > 0 ? true : false;
 }
 private int getArrayIndex(int number) {
  return number >> 3; // divide by 8
 }
 private int getBitIndex(int number) {
  return number % (1 << 3); // % 8
 }
 //test method
 public static void main(String[] args) {
  BitArray array = new BitArray(1000);
  System.out.println("length of array :" + array.set.length);
  int num1 = 17;
  array.storeNumber(num1);
  int num2 = 171;
  array.storeNumber(num2);
  int num3 = 400;
  array.storeNumber(num3);
  System.out.println("val " + num1 + " exists ? "
    + array.numberExists(num1));
  System.out.println("val " + num2 + " exists ? "
    + array.numberExists(num2));
  System.out.println("val " + num3 + " exists ? "
    + array.numberExists(num3));
  System.out.println("val " + 500 + " exists ? "
    + array.numberExists(500));
  for (int i = 0; i < 1000; i = i + 2)
   array.storeNumber(i);
  array.printSet();
 }
}

Output:

length of array :125
val 17 exists ? true
val 171 exists ? true
val 400 exists ? true
val 500 exists ? false

keep coding !!!

Thank you for reading! If you enjoyed it, please clap 👏 for it.

Originally published at http://geekrai.blogspot.com.