Bit vector implementation provide space optimization by using a re-sizable character array . This article will help you to understand implementation of bitvector in c programming.
What is bit vector ?
Bit vector is composed of two words bit and vector. We already know bit and vector , bit is smallest unit of data in computer and it has single value either 0 or 1. Here vector defining a structure which is basically a re-sizable array . So bit vector is mean to pack values into an array so that no space is wasted. Bit vectors are array of bits. When we defining an integer array which can hold 10 elements then each block in the array contain 32 bit and total size will be 320 bit but we does’nt use entire 320 bit . So remaining space will be waste. Bit vector implementation is a solution to this problem . Here we declare a character array of some size and initialize it as zero .
In my program i declare an array named bit vector and initilize as zero . To insert an element into this dynamic array some steps are there Insertion means only setting a bit as true not actual insertion .
Let we take element ‘n ‘ as ‘6’
- To insert 6 we need a block in the array and a bit position .
- To find the block were 6 belongs , dividing 6 by the block size. Here array bitvector contain array of character so the block size will be 8 bits. 6 /8 is 0 and 6 must be belongs to 0th block.
- To find bit position of 6 in the 0’th block take reminder of 6 %8 . So we get the bit position as 6
- Here no insertion of element ‘6’ only setting the bit in the corresponding bit position as 1.
- To set a bit ,left shifted 1 p times, where p is bitposition, and OR it with the value in the block
bitvector[bitpostion] |= 1 << bit position
Now we set 6’th bit in 0’th block as 1.
To check whether a number is present or not in bit array we need the block which number belongs and also bitpostion.
- Find the block as do in the insertion
- Find the bitposition also.
- If the bit in the bitposition is zero no element is there
- If the value returned by the bitwise AND with the value in the block and left shifing of 1 p times ,were p is bitposition will true then number is present in bit array.
To clear a bit without affecting the all other bit in bit array the bit must be change to 0.
- So again shift a 1 left with bitposition
- Apply unary operator ~ to reverse all bits , ~(1 <<bitposition)
- Then binary AND operator with value in the block size
These are the main steps to implement a bit vector and bit vector implement a set data structre to store individual bits . Bit vector implementation in many languages provide space optimization.
neethutv 