Vectorization is the key principle behind space optimization of many programs in C. More often, when we define an array say , which can hold 10 elements of type integer, the total size of the array is 10 X 32 , i.e, 320 bits. Do we actually need 320 bits? The answer is no. Say we are storing numbers 4 ,6 ,5. How many bits are needed to represent them?
3*3 = 9 bits.
But the space allocated for these three numbers, is 3 x 32 i.e, 96bits, in short 86 bits are wasted . Whew! that is one hell of a space loss !.
The easiest way is to declare a character array of some desired size and initially make the bits 0 ,i.e,by calling the calloc function and storing the return address in a variable of type char *.
The calloc function sets all the bits to 0 initially. Each block can hold 8 bits since size of character is 8 bit.
Inserting a number
If we want to add 7 to the array:
1-> Find the block to which 7 belongs How? -> divide 7 by 8 ( since each block is of 8 bit byte). The quotient is the block number . So 7 belongs to the first block.
2-> Find the bit position of 7. Taking the remainder (using the % operator) helps. 7 % 8 is 7. So the 7th bit in the first block is the position of the number 7. Please note that we are not inserting the number 7 into the array, instead we are setting ( making the bit 1 ) the corresponding bit in the corresponding block .
Setting the bit -> ORin the value in the block with 1 leftshited n times( n is the bit position)
Deleting a number
1-> Find the position of the number.
2-> Clear the corresponding bit ( Make the bit 0)
Clearing the bit -> ANDing the value in the block with the negation of 1 leftshifted n times ( n is the bit position)
Checking the presence of a number
1-> Find the block to which the number belongs
2-> Find the bit position
3-> If the corresponding bit is 0, the number is not present.
If the value returned by ANDing number in the block with 1 leftshifted n times ( n is the bit position) is 1, the number is present
The sample code can be found here
Easwer's Blog 