65.9K
CodeProject is changing. Read more.
Home

BitArray in C

starIconstarIcon
emptyStarIcon
starIcon
emptyStarIconemptyStarIcon

2.78/5 (6 votes)

Jan 20, 2010

CPOL

1 min read

viewsIcon

63717

Introduction...

Introduction Recently I got a task to implement a complex algorithm which involves lot of bitwise operation .After a bit struggle, I found a simple solution in C. BitArray Structure The easy and efficient way to store the bit information of a value is to create a structure as follows
//Structure to hold a single bit

typedef struct {
unsigned int bit : 1;
} Bit;

//BitArray structure.

typedef struct {
Bit bitValues[BIT_ARRAY_LENGTH];
} BitArray; 
nth bit of an integer Here is the algorithm to findout the nth bit of an integer nthBit of X = 1) Perform logical AND between X and 1 2) Right shift the result from step 1 n times For example to findout the 3rd (4th position) bit of 171 (10101011) tmp = 171 & (1 << 3) result = tmp >> 3 The following function shows how to do this.
//Return the requested bit value of an integer
Bit getBit(int value, int position)
{
Bit singleBit;
singleBit.bit = 0;

if(position == 0) {
singleBit.bit = value & 1;
}else {
singleBit.bit = ( value & (1 << position ) ) >> position;

}
return singleBit;
}
Integer value from the bit array We often require to convert back the bit array into the integer value. The following function does that.
//gets the value of BitArray
int getValue(BitArray bitArray)
{
int value = 0;
unsigned int bitValue = 0;

bitValue = bitArray.bitValues[0].bit;
value |= bitValue;
for(int i = 1; i < BIT_ARRAY_LENGTH; i++)
{
bitValue = bitArray.bitValues[i].bit;
bitValue <<= i;
value |= bitValue;
}

return value;

} 
Example of Usage Imagine that we have to find out a secret key from a given value and the algorithm is as follows ->3rd bit of the value = 2nd bit of value XOR 3rd bit of value ->2nd bit of the value = 3rd bit of value XOR 1st bit of value ->1st bit of the value = 4th bit of value XOR 2nd bit of value The following function shows how to do this by using our bitArray functions.
int calculateKey(int value) {
   unsigned int key = 0;
   BitArray bitArray = getBitArray(value);
   bitArray.bitValues[3].bit = bitArray.bitValues[2].bit 
                              ^ bitArray.bitValues[3].bit;
   bitArray.bitValues[2].bit = bitArray.bitValues[3].bit 
                              ^ bitArray.bitValues[1].bit;
   bitArray.bitValues[1].bit = bitArray.bitValues[4].bit 
                              ^ bitArray.bitValues[2].bit;
   
   key = getValue(bitArray);
   return key;
}