BitArray in C
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;
}